Algorithms

Big-O is the asymptotic upper bound on how an algorithm's running time or space GROWS as input n grows, ignoring constants and lower-order terms. It compares scalability, not absolute seconds on any single input.

Binary search halves a SORTED array: compare the middle to the target, discard the half that cannot contain it, repeat — O(log n). The data must be sorted first, or the discarded half may hold the target.

Linear search scans elements one by one until it finds the target or exhausts the collection — O(n). It needs no ordering and works on any sequence, but is slow for large inputs since it may touch every element.

Use a dict from value to index: for each n, if target - n is already seen, return both indices; otherwise store n -> i. One pass, O(n) time and O(n) space — versus the O(n²) brute-force double loop. enumerate gives the index cleanly.

The median is the value not equal to both the max and the min. A clean trick: a + b + c - max(a, b, c) - min(a, b, c). With comparisons, the median is the one that lies between the other two, e.g. if (a <= b <= c) or (c <= b <= a): return b, and so on. Equal values are handled because <= keeps ties valid.

Pick a pivot, partition the array into elements less than it and greater than it, then recursively quicksort each partition; the base case is 0 or 1 element. Average and best case are O(n log n), and it sorts in place.

BFS explores a graph level by level using a queue, visiting all neighbors before going deeper — O(V + E). It tells whether a path exists and finds the SHORTEST path in an UNWEIGHTED graph.

Dynamic programming optimizes problems with optimal substructure and overlapping subproblems: solve each subproblem once and store its result in a table or memo to reuse, avoiding recomputation. Knapsack and LCS are classics.

Iterate with a tuple-swap: a, b = 0, 1; for _ in range(n): a, b = b, a + b; return a — O(n) time, O(1) space, no exponential recursion. The generator yields lazily: while True: yield a; a, b = b, a + b. Python ints are arbitrary-precision, so there is no overflow.

A greedy algorithm builds a solution by always taking the locally optimal choice at each step, hoping to reach a global optimum. Fast and simple, it is a good approximation when an exact solution is too slow — but is not always optimal.

Use two pointers, left at the start and right at the end. Advance each past any non-letter, then compare s[left].lower() to s[right].lower(); on mismatch return False, otherwise move both inward. Stop when they cross. This is O(n) time and O(1) space — no new filtered string. Initializing right to len(s)-1 (not -1) avoids an off-by-one.

Binary-search for the pivot. Compare nums[mid] to nums[high]: if nums[mid] > nums[high] the peak is in the right half (low = mid + 1), else it is at mid or to its left (high = mid). The max is the element just before the rotation point — nums[low - 1] once low lands on the minimum, or simply track the larger side. O(log n); a sorted, un-rotated array returns its last element.

Convert seen_ids to a set once, then iterate recom_ids keeping items whose id is not in that set. The set gives O(1) membership, so the whole pass is O(n); a list-based in check would make each test O(m) and the total O(n*m). Iterating recom_ids directly preserves order.

Loop i from 0 to n-1, summing m[i][i] for the main diagonal and m[i][n-1-i] for the anti-diagonal, then return abs(main - anti). The key index is n-1-i for the anti-diagonal — off-by-one here (using n-i or counting bottom-up) is the classic bug. A single pass is O(n).

The cleanest order-preserving way is list(dict.fromkeys(items)) — dict keys are unique and, since 3.7, keep insertion order. Equivalently, iterate once and append items whose value is not yet in a seen set, giving O(n). Plain set(items) deduplicates but loses order, so it does not satisfy the requirement.

Dijkstra finds the lowest-total-weight path from a source in a WEIGHTED graph — directed or undirected, cyclic or not — as long as edge weights are NON-NEGATIVE. For negative weights use Bellman-Ford instead.

For classification or regression, kNN finds the k training points closest to a query by a distance metric like Euclidean or cosine, then predicts — majority class or averaged value. It is lazy with no training.

Worst case O(n^2) happens with poor pivots — e.g. always picking the first or last element on sorted or reverse-sorted input, yielding maximally unbalanced partitions. Mitigate it with randomized or median-of-three pivots.

Sort goods once, then for each need binary-search its insertion point with bisect_left and compare the neighbour just below and just above, taking the smaller abs distance. Summing those gives the answer in O((n+m) log n). Brute force — scanning all goods per buyer — is O(n*m). The candidates around the insertion index are the only two that can be nearest.

Because the value range is bounded (256 byte values), use counting sort: stream the file in chunks, tally each byte's frequency in a 256-slot array, then write each value repeated by its count. This is O(n) time and O(1) extra memory (a fixed 256-entry table). The general unbounded case would need external merge sort: split into sorted runs on disk, then k-way merge them.

Signs: it slows dramatically as input grows, has no known polynomial-time exact solution, seems to need checking all combinations, and reframes as a known NP-complete problem like set cover. For these, fall back to an approximation.