DSA interview patterns

In short

A "pattern" is a reusable shape of solution — two pointers, sliding window, prefix sums, monotonic stack, heap for top-K, binary search on the answer, and so on — that solves a whole family of problems once you recognise the signal in the question. Interviewers deliberately ask variants rather than famous problems, so pattern recognition beats memorising solutions: roughly 15-20 patterns cover the large majority of problems set in coding rounds. This is examined in company online assessments and DSA interviews (Amazon, Microsoft, Google India, Flipkart, Zomato, Swiggy, Razorpay, Atlassian, Walmart Global Tech, Adobe), in mass placement tests (TCS NQT, Infosys, Wipro NLTH, Accenture, Cognizant) and on HackerRank, HackerEarth, CodeChef and Codeforces. University "Design and Analysis of Algorithms" labs and GATE CS set the same structures under their classical names. The skill measured is not coding speed but the ability to map constraints to a complexity target, pick the pattern, state its invariant and prove the bound.

Explained

Reading the problem: constraints decide the pattern

• Read n first. The constraint is the question's biggest hint: an online judge executes roughly 10⁸ simple operations per second (varies with language and judge), so n and the time limit together fix the allowed complexity.
• Then read the value range. Values up to 10⁹ with small n means "binary search on the answer" or maths, never an O(max value) array.
• Then read what is asked: a count, a maximum, "any one valid", or "all of them". "All of them" implies exponential output, so backtracking is expected and is not a failure.
• Watch the structural adjectives: *sorted* → two pointers or binary search; *contiguous subarray* → sliding window or prefix sum; *k-th largest* → heap or quickselect; *next greater / nearest smaller* → monotonic stack; *shortest in unweighted graph* → BFS; *dependencies / ordering* → topological sort; *connected / same group* → union-find; *prefix of a word* → trie.
• State the target aloud: "n ≤ 2×10⁵, so I need O(n log n) or better." This single sentence is scored in most interview rubrics.

Linear-scan patterns: two pointers, sliding window, fast-and-slow, prefix sum

• Two pointers (opposite ends): on a *sorted* array, start l=0, r=n−1; move l right to increase the sum, r left to decrease. Used for pair-sum, 3-sum (sort, fix one, two-pointer the rest), container-with-most-water, palindrome check. O(n) after sorting.
• Two pointers (same direction, fast-slow index): in-place write pointer for remove-duplicates, move-zeroes, partitioning. The invariant is "everything before the write pointer is final".
• Sliding window, fixed size k: add the element entering at r, remove the one leaving at r−k, leaving the window l = r−k+1 … r; one pass, O(n). Used for max/min sum of k, averages, anagram check by frequency vector.
• Sliding window, variable size: expand r always; while (window invalid) shrink l. Amortised O(n) because each index enters and leaves once — at most 2n pointer moves. Used for longest substring without repeats, smallest subarray with sum ≥ S, longest substring with at most k distinct characters.
• Caution: variable-size windows need monotonicity — adding an element must only push the window in one direction. With negative numbers "longest subarray with sum ≤ S" is *not* a window problem; use prefix sums with a sorted structure.
• Fast-and-slow pointers (Floyd): slow moves 1, fast moves 2. Detects a cycle in a linked list, finds the middle node, finds the cycle's start, detects duplicate numbers treated as a functional graph, and tests happy numbers. O(n) time, O(1) space — the reason it is preferred over a hash set.
• Prefix sums / difference arrays: precompute P[i] = sum of first i elements; any range sum is a subtraction. Combined with a hash map of seen prefix sums, it counts subarrays with a given sum, or with sum divisible by k (store prefix mod k). The difference array does the reverse: apply many range updates in O(1) each, then one prefix pass to materialise.
• Kadane's scan: running best ending here = max(current element, previous best + current element); the maximum-subarray answer in one pass.

Stack, queue and monotonic structures

• Monotonic stack: keep indices with values in increasing (or decreasing) order; pop while the incoming element breaks the order. Each index is pushed and popped once → O(n). Solves next greater/smaller element, daily temperatures, stock span, largest rectangle in a histogram, maximal rectangle in a binary matrix, trapping rain water, and "sum of subarray minimums".
• Monotonic deque: sliding-window maximum in O(n) — push indices at the back, pop smaller values from the back, pop expired indices from the front.
• Plain stack patterns: balanced-brackets validation, expression evaluation and infix→postfix conversion, undo stacks, iterative tree traversal, and min-stack (store the running minimum alongside each element).
• Queue / BFS-shaped patterns: level-order traversal, "shortest number of moves" on an implicit graph (word ladder, knight's moves, rotting oranges, 0-1 matrix distance), and multi-source BFS where all sources are enqueued at level 0.

Hashing, heaps and top-K

• Frequency map: the default first move for anagrams, majority element, first non-repeating character, group-by, and "two sum" on an unsorted array in one pass.
• Hash set for membership: longest consecutive sequence (start counting only at x where x−1 is absent) turns an O(n log n) sort into O(n).
• Top-K with a heap: for the k largest, keep a min-heap of size k and pop whenever it exceeds k → O(n log k) time, O(k) space; for the k smallest use a max-heap of size k. Beats sorting when k ≪ n.
• Two heaps: a max-heap of the lower half and a min-heap of the upper half, sizes kept within one, give the running median in O(log n) per insertion and O(1) per query.
• k-way merge: a min-heap holding one element per list merges k sorted lists in O(N log k) — also solves "smallest range covering all lists" and "k-th smallest in a sorted matrix".
• Quickselect: expected O(n) k-th order statistic, worst case O(n²); mention it as the alternative to a heap when asked to beat O(n log k).

Arrays in place, intervals, and search on the answer

• Cyclic sort: when values are a permutation of 1..n (or 0..n−1), repeatedly swap each value to its own index. Finds the missing number, the duplicate, all duplicates and the first missing positive in O(n) time and O(1) extra space.
• Index-as-hash marking: negate or add n to arr[value−1] to record "seen" without extra memory; the standard "O(1) space" follow-up.
• In-place reversal: reverse a linked list by rewiring three pointers (prev, curr, next); extends to reverse-in-groups-of-k, palindrome linked list, and reorder list.
• Dutch national flag: three pointers (low, mid, high) sort an array of 0s, 1s and 2s in one pass.
• Merge intervals: sort by start, then either extend the last interval or push a new one. Solves merge, insert, erase-overlap (greedy by end time), meeting-rooms-II (min heap of end times, or a sweep over +1/−1 events).
• Binary search on the answer (parametric search): when the answer is a number and feasible(x) is monotone (false… false, true… true), binary search x and call a linear checker. Used for ship-packages-in-D-days, split-array-largest-sum, Koko-eating-bananas, allocate-minimum-pages, aggressive cows, and "minimum time to complete tasks". Complexity O(n log(range)).
• Matrix patterns: search a row- and column-sorted matrix from the top-right corner in O(m+n); spiral traversal; rotate 90° by transpose-then-reverse-rows; flood fill / island counting by DFS or BFS over 4 or 8 neighbours.

Trees, recursion-shaped and design patterns

• DFS on a tree, two flavours: *top-down* (pass information down as parameters, e.g. path sums, depth) and *bottom-up* (return a value from children and combine, e.g. height, diameter, balanced check, lowest common ancestor). Most "hard tree" questions are bottom-up with a side-effect variable.
• BST property: inorder traversal is sorted — validate a BST with bounds (low, high) rather than comparing only parent and child; k-th smallest is the k-th inorder node.
• Subsets / combinations / permutations template: choose-explore-unchoose with a start index to avoid duplicates; prune when the partial solution cannot win. The output size itself is 2ⁿ or n!, which is why n is tiny in such problems.
• Union-Find (DSU): with union by size/rank and path compression, nearly O(1) amortised per operation; the pattern for "are these in the same group", counting connected components, detecting a cycle in an undirected graph, redundant connection, and accounts-merge.
• Trie (prefix tree): children map plus an end-of-word flag; gives insert and search in O(length). The pattern behind autocomplete, spell-check, maximum XOR pair (binary trie), and word-search-II.
• Design / machine-coding patterns (common for 2+ years experience in Indian product companies): LRU cache = hash map + doubly linked list, O(1) get and put; LFU = frequency buckets; rate limiter = sliding-window log or token bucket; insert-delete-getRandom in O(1) = dynamic array + index map; median stream = two heaps.

Interview craft around the pattern

• Clarify before coding: input size, data types, duplicates allowed, negative values, empty input, is the array sorted, can it be modified, is extra space allowed, return value or index.
• Give the brute force first in one sentence with its complexity, then say what makes it wasteful and which pattern removes that waste. This is how the "problem solving" rubric is scored.
• State the invariant of your pointer/stack/window in words before writing the loop; most bugs are an unstated invariant.
• Dry-run on a 4-6 element example and an edge case (empty, single element, all equal, all negative) out loud. Do not wait for the interviewer to find the off-by-one.
• Close with complexity and a trade-off: time, space, and "if memory were tighter I would use cyclic sort instead of a hash set".
• Typical Indian pipelines: service companies use an automated round (2-3 coding questions, fixed time, hidden test cases) and value a working accepted solution; product companies run 2-3 live DSA rounds plus a low-level-design or machine-coding round where these same structures must be written as clean, testable classes.

Key points

• Pattern recognition - map a problem's wording and constraints to one of about 15-20 solution shapes rather than recalling a specific solution.
• Constraint-to-complexity - n ≤ 10⁵ means O(n log n); n ≤ 10⁷ means O(n); n ≤ 20 means 2ⁿ is fine.
• Two pointers - needs sortedness or a monotone property; O(n) after an O(n log n) sort.
• Sliding window - fixed size is add-and-remove; variable size is expand-then-shrink-while-invalid, amortised O(n).
• Window validity must be monotone - negatives usually break a window and force prefix sums instead.
• Prefix sum + hash map - converts "count subarrays with sum = k" from O(n²) to O(n).
• Difference array - many range updates in O(1) each, one final prefix pass.
• Fast-and-slow pointers - cycle detection, middle node, cycle start, in O(1) space.
• Monotonic stack - every "next/previous greater or smaller" question; amortised O(n) as each index is pushed and popped once.
• Monotonic deque - sliding-window maximum in O(n), the standard follow-up to the heap solution.
• Heap of size k - k largest with a min-heap, k smallest with a max-heap: O(n log k), O(k) space.
• Two heaps - running median; k-way merge heap - merge k sorted lists in O(N log k).
• Cyclic sort and index marking - O(1)-space answers for permutation-range arrays (missing, duplicate, first missing positive).
• Merge intervals - always sort by start; sort by *end* for the greedy "maximum non-overlapping" variant.
• Binary search on the answer - applies when feasible(x) is monotone; cost O(n log(range)).
• Union-Find - grouping and undirected cycle detection in near-constant amortised time with path compression.
• Trie - prefix queries in O(word length), independent of dictionary size.
• LRU cache - hash map plus doubly linked list is the canonical O(1) design answer.

Formulas and examples

Example 1 - fixed-size sliding window. Maximum sum of any 3 consecutive elements of [2, 1, 5, 1, 3, 2].

• Window 1 (indices 0-2): 2+1+5 = 8 → best 8.
• Slide: subtract a[0]=2, add a[3]=1 → 8 − 2 + 1 = 7.
• Slide: subtract a[1]=1, add a[4]=3 → 7 − 1 + 3 = 9 → best 9.
• Slide: subtract a[2]=5, add a[5]=2 → 9 − 5 + 2 = 6.
• Answer 9 (subarray [5,1,3]), in 8 add/subtract operations instead of 4×3 = 12 for the naive scan; O(n) versus O(nk).

Example 2 - two pointers on a sorted array. Find a pair summing to 14 in [1, 3, 4, 6, 8, 11].

• l=0, r=5: 1+11 = 12 < 14 → need bigger, l=1.
• l=1, r=5: 3+11 = 14 → found, indices (1, 5).
• Two probes instead of 15 pairs; O(n) time, O(1) space.

Example 3 - prefix sum with a hash map. Count subarrays with sum = 7 in [3, 4, 7, 2, −3, 1, 4, 2].

• Prefix sums: 3, 7, 14, 16, 13, 14, 18, 20. Map starts {0:1}, count = 0.
• p=3, need −4 → 0. p=7, need 0 → +1 (count 1). p=14, need 7 → +1 (count 2). p=16, need 9 → 0. p=13, need 6 → 0. p=14, need 7 → +1 (count 3). p=18, need 11 → 0. p=20, need 13 → +1 (count 4).
• Answer 4: [3,4], [7], [7,2,−3,1], [1,4,2]. Note the sliding window would fail here because of the −3.

Example 4 - binary search on the answer. Minimum ship capacity to carry weights [4, 8, 5, 6, 3] within D = 3 days.

• Bounds: lo = max = 8 (one package must fit), hi = sum = 26 (all in one day).
• mid = 17: days = [4+8+5], [6+3] = 2 ≤ 3 → feasible, hi = 17.
• mid = (8+17)/2 = 12: days = [4+8], [5+6], [3] = 3 ≤ 3 → feasible, hi = 12.
• mid = (8+12)/2 = 10: days = [4], [8], [5], [6+3] = 4 > 3 → infeasible, lo = 11.
• mid = 11: days = [4], [8], [5+6], [3] = 4 > 3 → infeasible, lo = 12 = hi.
• Answer 12. Cost: log₂(26−8) ≈ 5 checks × O(n) = O(n log(sum)).

Example 5 - monotonic stack. Next greater element for [2, 1, 2, 4, 3] (−1 if none), scanning right to left with a decreasing stack.

• i=4 (3): stack empty → −1; push 3. Stack [3].
• i=3 (4): pop 3 (≤4) → stack empty → −1; push 4. Stack [4].
• i=2 (2): top 4 > 2 → 4; push 2. Stack [4,2].
• i=1 (1): top 2 > 1 → 2; push 1. Stack [4,2,1].
• i=0 (2): pop 1, pop 2 (both ≤ 2) → top 4 → 4; push 2.
• Answer [4, 2, 4, −1, −1]. Total pushes 5, pops 3 → O(n).

# variable-size sliding window: longest substring with no repeated character
def longest_unique(s):
    last, best, l = {}, 0, 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= l:
            l = last[ch] + 1          # shrink past the previous occurrence
        last[ch] = r
        best = max(best, r - l + 1)   # invariant: s[l..r] has no repeats
    return best

# monotonic stack skeleton: previous smaller element
def prev_smaller(a):
    st, out = [], []
    for x in a:
        while st and st[-1] >= x:
            st.pop()
        out.append(st[-1] if st else -1)
        st.append(x)
    return out

Where it is used

• Product-company SDE hiring in India: 2-3 DSA rounds at Amazon, Microsoft, Google India, Flipkart (pair-programming round), Walmart Global Tech, Adobe, Atlassian, Zomato, Swiggy, Razorpay, PhonePe and Uber India, followed by a low-level-design or machine-coding round using the same structures.
• Mass placement assessments: TCS NQT, Infosys, Wipro NLTH, Capgemini, Cognizant and Accenture coding sections, delivered on HackerRank, HackerEarth, Mettl or AMCAT, where the window/prefix/hash-map patterns cover most questions.
• Production systems: sliding-window rate limiters in payment and UPI-facing APIs, LRU and LFU caches in CDNs and Redis-backed services, tries in e-commerce autocomplete and address search, interval merging in calendar and seat-booking systems (IRCTC-style allocation), heaps in job schedulers and nearest-driver matching.
• Data engineering and analytics roles: prefix sums and difference arrays behind rolling aggregates and window functions; k-way merge behind external sorting of files larger than RAM.
• Competitive programming and contests: CodeChef, Codeforces, ICPC regionals and Google Kick Start-style events, where these patterns are the building blocks of harder problems.
• University labs and GATE CS: the same ideas appear as stack/queue applications, order statistics, divide-and-conquer bounds and amortised analysis in Design and Analysis of Algorithms coursework.

Interview questions

• Q: How do you decide which pattern a problem needs? A: From the constraint on n (which fixes the target complexity) and the structural keywords — sorted, contiguous subarray, k-th largest, next greater, shortest path, prefix — each of which maps to a specific structure.
• Q: Why is a variable-size sliding window O(n) when the code has a nested while loop? A: The inner loop only ever advances the left pointer, and it advances at most n times in total, so the amortised cost is at most 2n pointer moves.
• Q: When does the sliding window technique fail for subarray sums? A: When the array has negative numbers, because adding an element no longer monotonically increases the sum, so shrinking the window cannot restore validity; use prefix sums with a hash map or an ordered structure instead.
• Q: Why does Floyd's cycle detection work, and where does the second phase come from? A: Fast covers twice the distance of slow, so they must meet inside the cycle; algebra then shows the distance from the head to the cycle start equals the distance from the meeting point to the cycle start, so two unit-speed pointers meet there.
• Q: For the k largest elements, which heap do you use and why? A: A min-heap of size k — the smallest of the current best k sits at the top and is cheapest to evict; this gives O(n log k) time and O(k) space instead of O(n log n).
• Q: How do you get the sliding-window maximum in O(n)? A: A monotonic deque of indices with decreasing values: pop smaller values from the back before pushing, pop expired indices from the front, and the front is always the window maximum.
• Q: What makes a problem suitable for binary search on the answer? A: The answer is a number in a known range and the predicate "is x achievable" is monotone — false up to a point, then true — so the boundary can be found in logarithmic probes.
• Q: Why is the largest-rectangle-in-histogram problem a monotonic stack problem? A: Each bar's rectangle is bounded by the nearest smaller bar on each side, and a stack of increasing heights yields both boundaries in a single pass.
• Q: How do you find a duplicate in an array of n+1 numbers from 1..n in O(1) extra space? A: Treat indices as a functional graph and run Floyd's cycle detection, or use cyclic sort/index negation if the array may be modified.
• Q: Explain the LRU cache design in one answer. A: A hash map from key to node plus a doubly linked list ordered by recency; get moves the node to the front, put inserts at the front and evicts the tail — both O(1).
• Q: Should you sort intervals by start or by end? A: By start to merge or insert overlapping intervals; by end for the greedy problem of keeping the maximum number of non-overlapping intervals.
• Q: If you have never seen a problem, what do you do in the first two minutes? A: Restate it, clarify input limits and edge cases, state the brute force with its complexity and the target complexity implied by n, then name the pattern that removes the waste.

Common mistakes

• Jumping straight into code without stating the target complexity, then producing an O(n²) solution for n = 10⁵.
• Applying a sliding window to a problem with negative values, or forgetting to shrink the window from the left until it is valid again.
• Off-by-one errors in two-pointer and binary-search loops: wrong loop condition (< versus <=), updating lo = mid instead of mid + 1, or computing the midpoint as (lo + hi)/2 and overflowing in C++/Java.
• Forgetting to seed the prefix-sum hash map with {0 : 1}, which loses every subarray that starts at index 0.
• Claiming a monotonic stack is O(n²) because of the inner while loop, or using a full sort where a size-k heap or quickselect was expected.
• Not handling the standard edge cases — empty input, single element, all elements equal, all negative, duplicates — and leaving the interviewer to find them.
• Memorising solutions to named problems instead of the invariant, so a small twist in the wording breaks the whole answer.

Related topics

Time and space complexity · Searching and binary search · Recursion and backtracking · Dynamic programming · Graph algorithms: BFS, DFS and shortest paths · Sorting algorithms