Time and Space Complexity Analysis Questions

Direct answer: The sliding-window (two-pointer) technique transforms a naive $O(n^2)$ scan of all subarrays/substrings into $O(n)$ by maintaining a contiguous "window" with two pointers (left and right boundaries) that each move forward AT MOST $n$ times total across the whole algorithm - instead of restarting the inner scan from every possible left boundary, the window incrementally EXPANDS (advance right) or CONTRACTS (advance left) based on whether the current window satisfies some condition, reusing work already done rather than recomputing from scratch.

Structured elaboration

The naive approach to "find something about every contiguous subarray" tries every $(i, j)$ pair of boundaries explicitly - $O(n^2)$ pairs, each potentially requiring $O(n)$ work to evaluate the subarray, for as much as $O(n^3)$ naively (or $O(n^2)$ if each subarray's property can be evaluated in O(1) incrementally from the previous one). The sliding-window insight: for many such problems, as the RIGHT boundary advances, the optimal or relevant LEFT boundary only ever moves FORWARD too (never needs to backtrack) - so instead of trying every left boundary for every right boundary, you can maintain a single window and incrementally adjust its two ends. Since each pointer only ever moves forward, and each can move at most $n$ times total (not per outer iteration), the TOTAL work across the whole algorithm is $O(n)$, not $O(n^2)$.

Worked example

For "find the length of the longest substring with no repeated characters": naively, you'd check every substring for repeated characters - $O(n^2)$ substrings, each taking up to $O(n)$ to verify, giving $O(n^3)$ naively (or $O(n^2)$ with a smarter per-substring check). With sliding window: expand the right pointer one character at a time, tracking seen characters in a set; if a repeat is found, advance the LEFT pointer (removing characters from the set) until the repeat is resolved, then continue expanding right. Both pointers move only forward, together traversing at most $2n$ total steps across the whole string - $O(n)$.

Trade-offs & pitfalls

• Sliding window CANNOT be applied directly when the window's "validity" condition is not MONOTONIC as the window grows - specifically, when adding an element to the right could make a currently-invalid window valid again without needing to shrink from the left (breaking the "left pointer only moves forward" assumption). A concrete example: "find a subarray whose sum is exactly K" (not "at least K" or "at most K") when the array can contain NEGATIVE numbers - here, shrinking the window from the left doesn't monotonically increase or decrease the sum in a predictable direction, so the standard two-pointer approach's core assumption breaks, and you typically need a different technique (like a prefix-sum-plus-hash-map approach) instead.
• The window's tracked STATE (a running sum, a character-frequency map, a count of distinct elements) must be updateable in O(1) as the window's boundaries move - if maintaining that state incrementally is itself expensive, the overall O(n) bound doesn't hold.
• Recognizing WHEN a problem has the right monotonic structure for sliding window (versus superficially resembling one) is the real skill - the technique's mechanics are simple once you've correctly identified that the problem qualifies.

Direct answer: An LRU (least-recently-used) cache combines a hash map (for O(1) key lookup) with a doubly linked list (for O(1) reordering and eviction) - a hash map alone can't track recency order in O(1), and a linked list alone can't look up a key in O(1); the combination gives each structure the job it's good at.

Structured elaboration

• A hash map alone gives O(1) get/put by key, but has no notion of "which key was used least recently" without an O(n) scan - you'd need to store and update timestamps, then scan all entries to find the minimum, which is O(n) per eviction.
• A doubly linked list alone naturally tracks recency (move a node to the front on every access, evict from the back), but finding a node by KEY to move it requires an O(n) linear search through the list.
• Combined: the hash map stores key -> node pointers into the linked list. get(key): hash-map lookup finds the node in O(1), then the node is unlinked and relinked at the front of the list in O(1) (doubly-linked, so both neighbors are known without a search). put(key, value): same O(1) lookup-and-move if the key exists, or O(1) insertion at the front plus (if over capacity) O(1) removal of the tail node, whose key is then also removed from the hash map.
• The critical design detail: the hash map's VALUE isn't the cached value directly - it's a pointer/reference to the linked-list NODE, so that once you've found the node via the hash map, you can splice it within the list in O(1) without any further lookup.

Worked example

Trace put(1,'a'), put(2,'b'), get(1), put(3,'c') on a capacity-2 cache:

1. put(1,'a'): list = [1] (front=back=1), map = {1: node1}.
2. put(2,'b'): list = [2,1] (2 is now most-recent, at front), map = {1: node1, 2: node2}.
3. get(1): hash lookup finds node1 in O(1); since node1 is not already at the front, unlink it and relink at front: list = [1,2]. Returns 'a'.
4. put(3,'c'): over capacity (2 items already), so first evict the tail (2, the least-recently-used): remove node2 from the list AND delete key 2 from the map. Then insert 3 at the front: list = [3,1], map = {1: node1, 3: node3}.

Key 2 was correctly evicted because it was least-recently used relative to the get(1) access that promoted 1 - both the eviction (tail removal) and the promotion (move-to-front) happen in O(1) because the linked list's structure means every splice only touches a constant number of neighboring pointers.

Trade-offs & pitfalls

• If you used a SINGLY linked list instead of doubly linked, moving an arbitrary node to the front would require knowing its predecessor to unlink it - which means an O(n) search, defeating the purpose. The "doubly" part is not incidental; it's what makes O(1) splicing possible.
• Many candidates correctly identify "hash map + linked list" but then can't explain WHY neither alone suffices - be ready to name the specific operation (find-by-key for the list, recency-tracking for the map) that the other structure covers.
• This same hash-map-plus-doubly-linked-list pattern generalizes to any "O(1) lookup plus O(1) reordering" requirement, not just LRU - it's worth recognizing as a reusable pattern (e.g. LFU (least-frequently-used) caches use a similar idea with an extra layer for frequency buckets).

Direct answer: Separate chaining stores colliding keys in a linked list (or small array/tree) per bucket; open addressing (linear/quadratic probing, double hashing) stores every key directly in the table itself, probing to the next slot on collision. Both give average-case O(1) get/put/delete under a good hash function and bounded load factor, but an attacker who can choose (or predict) keys that all hash to the same bucket can force every operation to O(n) - a real denial-of-service vector, not just a theoretical curiosity, mitigated by randomized hash seeding at process startup and hash functions resistant to seed-independent collision construction.

Structured elaboration

• Separate chaining: each bucket holds a small collection (commonly a linked list, or - in some modern implementations like Java 8+'s HashMap - a balanced tree once a bucket grows large) of all keys hashing there. Lookup cost is O(1 + chain length); with load factor kept bounded, expected chain length is O(1).
• Open addressing: on collision, probe subsequent slots (linear: next slot; quadratic: quadratically-increasing offsets; double hashing: a second hash function determines the probe sequence) until an empty slot is found. Avoids the pointer-chasing overhead of chaining (better cache locality, since probing stays within the contiguous backing array), but degrades faster as load factor approaches 1 (must keep load factor well below 1, commonly under 0.7, whereas chaining degrades more gracefully).
• The attack: if the hash function is known (or its output is predictable, e.g. a naive non-cryptographic hash with a fixed seed) and an attacker controls input keys (e.g. HTTP form-field names, JSON keys), they can construct a large set of keys that all collide into the same bucket(s), degrading every operation from O(1) to O(n) and creating an algorithmic denial-of-service - a single request with thousands of colliding keys can pin a server's CPU.

Worked example

This is not hypothetical: this exact vulnerability class ("hash flooding") was responsibly disclosed and patched across essentially every major web-application language runtime around 2011-2012, after researchers demonstrated that a small POST request with carefully-crafted colliding form-field names could consume many CPU-seconds parsing what should have been a millisecond-scale request. The fix adopted across languages was randomizing the hash seed per-process at startup (so the attacker can't predict the collision-inducing keys ahead of time without knowing the runtime's random seed) and, in some cases, switching to collision-resistant hash functions (like SipHash) specifically designed to make seed-independent collision construction computationally infeasible even if an attacker can observe hash outputs.

Trade-offs & pitfalls

• "Average-case O(1)" is a claim about TYPICAL inputs, not a security guarantee - any system that hashes attacker-controlled keys needs the worst-case-resistant mitigations (randomized seeding, or a cryptographically-motivated hash), not just a "good enough in practice" hash function.
• Randomized per-process seeding means hash order becomes non-deterministic across process restarts - code that accidentally depends on hash-iteration order (a common latent bug) will surface intermittently once seeding is randomized.
• Open addressing's degradation is sharper (clustering effects can compound near a full table) than chaining's, so open-addressing implementations typically resize more aggressively (lower load-factor threshold) to stay safely away from the cliff.

Direct answer: Big-O gives an asymptotic upper bound (the algorithm never does worse than this), Big-Omega gives an asymptotic lower bound (it never does better), and Big-Theta gives a tight bound (both at once, up to constant factors). Most everyday usage of "O(n)" is sloppy shorthand for Theta(n) - people usually mean the tight bound even when they write O.

Structured elaboration

Formally, for functions of $n$:

$$f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 : \forall n \ge n_0,\ 0 \le f(n) \le c \cdot g(n)$$ $$f(n) = \Omega(g(n)) \iff \exists\, c > 0,\ n_0 : \forall n \ge n_0,\ 0 \le c \cdot g(n) \le f(n)$$ $$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))$$

The intuition: O is "at most this fast-growing", Omega is "at least this fast-growing", Theta is "grows at exactly this rate" (sandwiched between two constant multiples of $g(n)$).

A common confusion: Big-O does not mean "this is the worst case" - it's a growth-rate bound that can describe best-case, average-case, or worst-case behavior depending on which function you plug in as $f(n)$. "Worst-case" and "O()" are independent axes; you can (and often should) say "the worst-case time is $\Theta(n^2)$."

Worked example

Let $f(n) = 3n^2 + 5n$ and $g(n) = n^2$.

• $f(n) = O(n^2)$: pick $c = 8$, $n_0 = 1$. For $n \ge 1$, $3n^2 + 5n \le 3n^2 + 5n^2 = 8n^2$. Holds.
• $f(n) = \Omega(n^2)$: pick $c = 3$, $n_0 = 1$. For $n \ge 1$, $3n^2 + 5n \ge 3n^2$. Holds.
• Since both hold, $f(n) = \Theta(n^2)$.

Now the O-but-not-Theta example the question asks for: let $f(n) = n$ and $g(n) = n^2$. Then $f(n) = O(n^2)$ (pick $c=1, n_0=1$: $n \le n^2$ for $n \ge 1$), but $f(n) \ne \Theta(n^2)$, because there is no $c > 0$ with $n \ge c \cdot n^2$ for all large $n$ (the ratio $n / n^2 = 1/n \to 0$, so no positive constant lower-bounds it). $f$ is O(g) but grows strictly slower, so it is not Omega(g), hence not Theta(g).

Trade-offs & pitfalls

• Interviewers usually accept "O(n)" when you mean the tight bound - but if asked to be precise (as here), know the distinction and use Theta when you mean it.
• A frequent mistake: quoting O() for an average-case argument as if it were a worst-case guarantee (e.g. calling hash-table lookup "O(1)" without qualifying "average case, assuming a good hash function").
• Omega is the least commonly used in casual conversation but matters when you need to argue a lower bound is unavoidable (e.g. proving comparison sorts need $\Omega(n \log n)$ comparisons).

Direct answer: Quickselect finds the k-th smallest element in expected O(n) time by partitioning like quicksort but recursing into only the ONE side that contains the target rank (instead of both sides, as quicksort does) - its worst case is O(n^2) with a poor pivot choice, but the median-of-medians pivot-selection strategy guarantees O(n) worst-case at the cost of a larger constant factor.

Structured elaboration

• Like quicksort, pick a pivot and partition the array so elements less than the pivot come before it and elements greater come after.
• Unlike quicksort, once partitioned, you know which side contains the k-th smallest element (compare k against the pivot's final index) - recurse into ONLY that side, discarding the other entirely.
• Because each recursive call operates on roughly half the previous size (with a good pivot), the total work forms a geometric series ($n + n/2 + n/4 + \cdots$) that sums to O(n), not O(n log n) - this is the key difference from quicksort, which must recurse into BOTH halves and thus sums to O(n log n).
• Worst case: an adversarial or unlucky pivot choice (always picking the smallest or largest remaining element) means each partition only shrinks the problem by one element, giving O(n) + O(n-1) + ... = O(n^2), identical in shape to quicksort's worst case.
• Median-of-medians: guarantees a pivot that is provably within the 30th-70th percentile of the current subarray (by recursively finding the median of medians of small groups), which bounds the worst case to O(n) - but the overhead of this more careful pivot selection makes its constant factor noticeably worse than simple random-pivot quickselect for typical inputs, so it's rarely used in practice outside of guaranteeing worst-case bounds for adversarial-input-resistant systems.

Worked example

Finding the median (n=1,000,001, k=500,000) with random-pivot quickselect: expected work is O(n) with a small constant (empirically close to 2n comparisons on average across many pivot choices), while the true worst case (vanishingly unlikely with a randomized pivot, but possible with a naive fixed-first-element pivot on adversarial/sorted input) would degrade to roughly $\binom{n}{2} \approx 5 \times 10^{11}$ comparisons - the gap between expected and worst case is enormous, which is exactly why RANDOMIZED pivot selection (not median-of-medians) is the standard practical choice: it makes the O(n^2) worst case exponentially unlikely to occur by chance, without median-of-medians' extra constant-factor overhead.

Trade-offs & pitfalls

• Randomized-pivot quickselect is the default real-world choice: expected O(n), simple to implement, and the adversarial worst case requires the attacker to know your specific pivot-selection randomness, which is infeasible if properly seeded.
• Median-of-medians is the answer when you need a hard WORST-CASE guarantee regardless of adversarial input (e.g. exposed to untrusted, potentially crafted data) - know that it exists and why it works, even though it's rarely the practical default.
• Quickselect is NOT stable and mutates (partitions) the input array in place unless you copy first - both worth flagging as a caveat if the caller needs the original order/array preserved.