Problem Solving

def max_profit(prices):
    """One pass: track the lowest price so far and the best profit so far."""
    best = 0
    lowest = float("inf")
    for p in prices:
        lowest = min(lowest, p)
        best = max(best, p - lowest)
    return best

# The tests come straight from the contract and the edge cases
cases = {
    (7, 1, 5, 3, 6, 4): 5,
    (): 0,
    (5,): 0,
    (5, 4, 3): 0,
    (2, 2, 2): 0,
    (3, 1, 10): 9,
}
for prices, want in cases.items():
    got = max_profit(list(prices))
    print("ok " if got == want else "FAIL", prices, "→", got)

import time

def has_duplicate_slow(items):        # O(n²): every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_fast(items):        # O(n): one pass, a set remembers
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

data = list(range(4000))              # no duplicates → worst case for both
for fn in (has_duplicate_slow, has_duplicate_fast):
    t = time.perf_counter()
    fn(data)
    ms = (time.perf_counter() - t) * 1000
    print(f"{fn.__name__:20} {'slow (100s of ms)' if ms > 50 else 'fast (a few ms)'}")

def pair_with_sum(sorted_nums, target):
    """Two pointers on a SORTED list: O(n) instead of checking every pair."""
    lo, hi = 0, len(sorted_nums) - 1
    while lo < hi:
        s = sorted_nums[lo] + sorted_nums[hi]
        if s == target:
            return sorted_nums[lo], sorted_nums[hi]
        if s < target:
            lo += 1        # need a bigger sum
        else:
            hi -= 1        # need a smaller sum
    return None

print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))
print(pair_with_sum([1, 3, 4, 6, 8, 11], 100))

def longest_unique_substring(s):
    """Sliding window: expand right, shrink left past any repeat."""
    last_seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique_substring("abcabcbb"), longest_unique_substring("bbbb"), longest_unique_substring(""))

def max_sum_window(nums, k):
    """Fixed-size window: add the new right, drop the old left — never re-sum."""
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

print(max_sum_window([2, 1, 5, 1, 3, 2], 3))

from collections import Counter, defaultdict

def two_sum(nums, target):
    """Classic: index of the complement, one pass."""
    seen = {}                       # value → index
    for i, n in enumerate(nums):
        if target - n in seen:
            return seen[target - n], i
        seen[n] = i
    return None
print(two_sum([2, 7, 11, 15], 9), two_sum([3, 3], 6))

def group_anagrams(words):
    groups = defaultdict(list)      # missing key → new list automatically
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))

print(Counter("mississippi").most_common(2))

def balanced(expr):
    """Stack: push openers, pop on closers, must match and end empty."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
for e in ["([]{})", "([)]", "((", ""]:
    print(f"{e!r:10} {balanced(e)}")

def next_greater(nums):
    """For each element, the next element to its right that is bigger (-1 if none). O(n) with a stack of indexes."""
    result = [-1] * len(nums)
    stack = []                      # indexes whose answer is still unknown
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            result[stack.pop()] = n
        stack.append(i)
    return result
print(next_greater([2, 1, 2, 4, 3]))

def subsets(items):
    """Backtracking: choose or skip each item."""
    out = []
    def go(i, chosen):
        if i == len(items):
            out.append(chosen[:])       # copy the current partial answer
            return
        chosen.append(items[i]); go(i + 1, chosen); chosen.pop()   # take it, recurse, undo
        go(i + 1, chosen)                                           # skip it
    go(0, [])
    return out
print(subsets([1, 2, 3]))

def permutations(items):
    if len(items) <= 1:
        return [items]
    return [[x] + p for i, x in enumerate(items) for p in permutations(items[:i] + items[i + 1:])]
print(permutations(["a", "b", "c"]))

# Sorting as the first move
intervals = [(5, 8), (1, 3), (2, 4), (9, 10)]
def merge_intervals(iv):
    iv = sorted(iv)                       # by start — now overlaps are adjacent
    merged = [iv[0]]
    for start, end in iv[1:]:
        if start <= merged[-1][1]:
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))
        else:
            merged.append((start, end))
    return merged
print(merge_intervals(intervals))

people = [("ada", 36, "data"), ("bob", 28, "infra"), ("cy", 36, "infra")]
print(sorted(people, key=lambda p: (-p[1], p[0])))     # age desc, then name asc
print(sorted(people, key=lambda p: p[2])[0])           # stable: first "data" in original order

from collections import deque
from functools import lru_cache

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": []}

def bfs_shortest(graph, start, goal):
    """Queue + visited set. First time we reach goal is the shortest path."""
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(path + [nxt])
    return None
print(bfs_shortest(graph, "A", "F"))

def dfs_reachable(graph, start):
    seen, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        stack.extend(graph[node])
    return sorted(seen)
print(dfs_reachable(graph, "C"))

# Grid BFS: number of islands (connected 1s)
grid = ["11000", "11000", "00100", "00011"]
def islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = set(); count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1
                stack = [(r, c)]
                while stack:
                    y, x = stack.pop()
                    if (y, x) in seen or not (0 <= y < rows and 0 <= x < cols) or grid[y][x] != "1":
                        continue
                    seen.add((y, x))
                    stack += [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]
    return count
print(islands(grid))

# DP: memoised recursion vs the exponential original
@lru_cache(maxsize=None)
def ways_to_climb(n):          # 1 or 2 steps at a time
    return 1 if n <= 1 else ways_to_climb(n - 1) + ways_to_climb(n - 2)
print(ways_to_climb(50))

# DP: bottom-up table — coin change, fewest coins
def min_coins(coins, amount):
    best = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != float("inf") else -1
print(min_coins([1, 5, 10, 25], 63), min_coins([2], 3))

# Problem: given click events (user, timestamp) sorted by time, find users
# with 3+ clicks within any 60-second window.
#
# Contract: list of (str, int seconds) sorted by time → sorted list of users. Empty → [].
# Brute force: for each user, every pair of clicks — O(n²).
# Pattern: group by user (hashmap), then sliding window over each user's times — O(n).

from collections import defaultdict

def bursty_users(events, k=3, window=60):
    by_user = defaultdict(list)
    for user, t in events:
        by_user[user].append(t)
    out = []
    for user, times in by_user.items():
        left = 0
        for right in range(len(times)):
            while times[right] - times[left] > window:
                left += 1
            if right - left + 1 >= k:
                out.append(user)
                break
    return sorted(out)

events = [("ada", 0), ("bob", 5), ("ada", 30), ("ada", 59), ("bob", 100), ("cy", 120), ("bob", 130), ("bob", 200)]
print(bursty_users(events))          # ada: 0,30,59 within 60 → yes. bob: 100,130,200 → 100 apart → no
print(bursty_users([]))
print(bursty_users(events, k=2, window=10))

# Problem: a log has lines "level message". Return the top-2 most frequent
# messages per level, ties broken alphabetically.
#
# Contract: list[str] → dict[level, list[(message, count)]]. Unknown format → skip the line.
# Pattern: hashmap of hashmaps (Counter per level), then sort by (-count, message).

from collections import Counter, defaultdict

def top_messages(lines, n=2):
    per_level = defaultdict(Counter)
    for line in lines:
        parts = line.split(" ", 1)
        if len(parts) != 2:
            continue
        level, msg = parts
        per_level[level][msg] += 1
    return {
        level: sorted(c.items(), key=lambda kv: (-kv[1], kv[0]))[:n]
        for level, c in per_level.items()
    }

log = ["ERROR db timeout", "INFO started", "ERROR db timeout", "ERROR disk full",
       "INFO started", "INFO done", "garbage", "ERROR auth failed", "ERROR disk full"]
for level, top in top_messages(log).items():
    print(level, top)