The sliding window algorithm solves array and string problems by tracking a contiguous range that expands or slides across the input instead of restarting a nested loop for every starting point. It turns a brute-force approach that checks every possible subarray, usually running in O(n squared) time or worse, into a single pass that runs in O(n). You reach for it whenever a problem asks for the longest, shortest, or best contiguous subarray or substring under some condition. The rest of this guide covers how to recognize the pattern from the wording of a problem, the mistakes that sink most attempts, and what to say out loud while you solve one in an interview.

## How Do You Recognize a Sliding Window Problem?

You recognize a sliding window problem by two things showing up together: the word "contiguous" (even if it's implied rather than stated, as in "substring" instead of "subsequence"), and a request for an extreme value like the longest, shortest, maximum, or minimum range that satisfies some condition. A problem that says "subsequence" instead of "subarray" or "substring" is usually not a sliding window problem, because a subsequence can skip elements and drop the contiguous requirement that makes the window trick work at all.

A few concrete signals tend to show up in the same sentence as a real sliding window problem:

- "Find the longest substring that..." or "find the shortest subarray that..."
- "At most k distinct" or "no more than k" of something, which almost always means a variable window with a shrink condition.
- "Exactly k" of something, a slightly harder variant covered later in this guide.
- A running total, count, or set that would need to be recomputed from scratch at every position in a brute-force solution.
- "Consecutive" or "in a row," describing elements that must stay adjacent in the original array.

Once you spot these signals, ask yourself one more question before committing to the pattern: does growing the window in one direction ever make the answer worse in a way you could undo just by shrinking from the other side? A yes answer confirms sliding window is the right pattern, while a problem that instead wants you to consider elements in any order, or every element independently of its neighbors, is pointing you toward a different pattern entirely, like a hash map frequency count or a heap, not a window.

## Fixed Window or Variable Window: Which One Do You Need?

You need a fixed window when the problem states an exact size upfront, such as "find the maximum sum of any k consecutive elements," and a variable window when the size depends on a condition that only becomes clear as you scan the array, such as "find the smallest subarray with a sum of at least a given target."

A fixed window is the easier of the two to implement. You slide one element in on the right and one element out on the left at every step, keeping the window size constant, and you update a running value (a sum, a count, a frequency map) incrementally rather than recalculating it. A variable window does the same incremental update, but the two pointers move independently: the right pointer always advances to grow the window, and the left pointer only advances when the current window stops satisfying whatever condition the problem cares about.

The mechanics of a variable window follow a repeatable shape once you have seen it a few times:

1. Advance the right pointer and update your running state with the new element.
2. Check whether the window still satisfies the condition. If it doesn't, advance the left pointer and remove that element from your running state, repeating until the condition holds again.
3. Once the window is valid, record or update the answer using the current window's size or contents.
4. Repeat until the right pointer reaches the end of the array.

That loop runs in O(n) total because each pointer only ever moves forward, never backward, so the combined number of steps across the whole run is bounded by twice the length of the array, not the square of it.

## How Do You Turn a Brute-Force Loop Into a Sliding Window One?

You turn a brute-force nested loop into a sliding window by replacing the inner loop's full recalculation with an incremental update tied to whichever element just entered or left the window. Take the classic example of finding the length of the longest substring without repeating characters. A brute-force solution checks every possible substring and, for each one, scans it again to check for duplicates, which costs O(n cubed) in the worst case or O(n squared) with a smarter inner check.

```python
def longest_unique_substring(s):
    left = 0
    seen = {}
    best = 0

    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        best = max(best, right - left + 1)

    return best
```

The right pointer, driven by the for loop, visits every character exactly once. The left pointer only moves forward when a duplicate forces it to, and it never resets or scans backward. The dictionary named `seen` holds the running state, in this case the last index where each character appeared, and it gets updated in place instead of recomputed from the current window every time the right pointer advances. That single incremental update is the entire trick behind why this runs in O(n) instead of O(n squared).

## What's the Time and Space Complexity of a Sliding Window Solution?

A sliding window solution runs in O(n) time because the left and right pointers each move forward across the array at most once, for a combined total of at most 2n steps regardless of how many times the inner shrink loop fires. It is tempting to look at a nested while loop inside a for loop and assume O(n squared), but the left pointer's total movement across the entire run of the algorithm is capped at n, since it can never move past where the right pointer already is. Add up every increment of both pointers across the whole execution and the total work is linear, not quadratic.

Space complexity depends entirely on what you're tracking in the window, not on the window pattern itself. A running sum or count needs O(1) extra space. A frequency map keyed by the distinct characters or values in the window needs O(k) space, where k is the number of distinct elements the window can hold, which in the worst case (like the longest-unique-substring example above) is bounded by the size of the alphabet or character set involved, not the length of the input string.

## How Is Sliding Window Different From Two Pointers?

Sliding window is a specific kind of two pointers problem where both pointers move in the same direction across one pass, tracking a contiguous range as they go. Two pointers is the broader family, and it also covers problems where the pointers start at opposite ends of a sorted array and move toward each other, such as finding a pair that sums to a target value or maximizing the area between two lines in the container-with-most-water problem.

The distinction matters because the two setups call for different running state. A sliding window problem almost always needs you to track something about the current range as a whole (a sum, a count, a set of distinct values), while an opposite-ends two pointers problem usually just compares the two boundary elements directly and decides which one to move based on that comparison, with no window contents to maintain in between. If you catch yourself reaching for a frequency map or a running sum in an opposite-ends problem, or reaching for two pointers starting from either end in a problem that clearly wants a contiguous range, that's a sign you have the wrong variant of the pattern and should reconsider the setup before you write more code.

## What Mistakes Sink a Sliding Window Answer in an Interview?

The single most common mistake is recomputing the window's state from scratch on every step instead of updating it incrementally, which quietly turns an O(n) solution back into an O(n squared) one without the interviewer necessarily noticing until they ask you to trace through the complexity. If you find yourself summing or counting the entire current window inside your main loop, stop and replace it with an update based only on the element entering or leaving.

An off-by-one error on the window boundary is the second most common failure, usually from forgetting whether the right pointer represents the last included index or the one just past it, and applying that assumption inconsistently between the growth step and the size calculation. Pick one convention at the start, state it out loud, and use it consistently through the whole solution.

A third mistake is treating "exactly k" and "at most k" as interchangeable, when they require different logic entirely. "At most k distinct characters" is a direct variable-window condition: shrink whenever the distinct count exceeds k. "Exactly k distinct characters" isn't solved by shrinking on overshoot alone, since a window with fewer than k is also invalid. The clean way to handle it's to compute atMost(k) minus atMost(k minus 1), reusing the same at-most helper twice rather than writing a separate, more fragile piece of logic for the exact case.

Finally, candidates sometimes forget to handle an input smaller than the window size, or an empty input entirely, and only discover the bug when the interviewer asks about edge cases at the end. Check those cases before you start coding, not after, and mention out loud that you checked them.

## What Should You Say Out Loud While You Solve a Sliding Window Problem?

Narrate the recognition step first: point out the word "contiguous" or its implied form ("substring" rather than "subsequence"), name the extreme value the problem wants, and say plainly that this looks like a sliding window problem before you touch the keyboard. That single sentence tells the interviewer you're pattern-matching deliberately rather than guessing.

Next, state which running value you plan to track inside the window and why, whether that's a sum, a count, or a frequency map, and confirm out loud whether you need a fixed or variable window based on whether the problem gives you an exact size. As you write the code, narrate the two pointer movements separately: say when the right pointer advances and what state update that triggers, then say when and why the left pointer advances. That separation makes it easy for an interviewer to follow your logic even before you finish typing.

Once the code is on the screen, trace through a short example by hand, including at least one edge case, and state the final complexity claim explicitly: "This runs in O(n) time because each pointer moves forward through the array at most once, and O(k) space for the frequency map." Interviewers grade sliding window answers heavily on whether you can defend that complexity claim, not just state it, so be ready for a follow-up question about why the inner shrink loop doesn't push the total past O(n).

## Which Practice Problems Actually Build the Pattern-Recognition Skill?

The problems that build real recognition skill are the ones that force you to notice the signal words before you start coding, not the ones you have already memorized the solution to. A good practice set covers a fixed window (maximum sum of a subarray of size k), a basic variable window (smallest subarray with a sum at least a target value), a frequency-map variable window (longest substring with at most k distinct characters), and the exactly-k variant (subarrays with exactly k distinct integers, solved with the at-most-k subtraction trick).

Working through those four in order, out loud, teaches you the full range of the pattern faster than grinding through fifty loosely related problems, because each one adds exactly one new piece of mechanics on top of the last. [Our curated question bank](/questions) draws from real onsite reports rather than an unfiltered public archive, so the sliding window problems you find there reflect what companies are actually asking right now rather than a static list that stopped updating years ago.

## Where Sliding Window Fits Into Your Broader Pattern Prep

Sliding window is one entry in a small set of patterns that covers most of what shows up in a real coding interview, and it's worth learning alongside the others rather than in isolation. [Our guide to spotting patterns before you code](/articles/leetcode-patterns) covers how sliding window relates to two pointers, binary search, and the rest of that core set, and walks through the signal-recognition habit this guide applies specifically to windows.

If the complexity argument in this guide felt shaky, especially the claim that a nested-looking loop still runs in O(n), [our breakdown of how to analyze time complexity](/articles/time-complexity) covers the amortized-cost reasoning behind it in more depth, including how interviewers actually probe that claim with follow-up questions. And if you want to see the same single-pattern, deep-dive treatment applied to a different technique, [our binary search guide](/articles/binary-search) walks through recognizing a monotonic search space the same way this guide walks through recognizing a contiguous window.

## Frequently Asked Questions

### What is the sliding window algorithm?

The sliding window algorithm is a technique for solving array and string problems by tracking a contiguous range that expands or moves across the input in a single pass, updating a running value incrementally instead of recalculating it from scratch at every position. It turns many brute-force O(n squared) solutions into O(n) ones.

### When should I use a fixed window instead of a variable window?

Use a fixed window when the problem states an exact size directly, such as "the maximum sum of any k consecutive elements." Use a variable window when the valid range depends on a condition that only becomes clear as you scan, such as finding the smallest subarray whose sum meets a target.

### Is the sliding window algorithm the same as the two pointers technique?

Sliding window is a specific case of two pointers where both pointers move in the same direction across a contiguous range. Two pointers also covers problems where the pointers start at opposite ends of a sorted array and move toward each other, which isn't a window at all since there is no running range to maintain.

### What is the time complexity of the sliding window algorithm?

Sliding window solutions run in O(n) time because the left and right pointers each move forward across the input at most once, for a combined total bounded by twice the input length, even when the shrink step is written as a nested loop inside the main one.

### What's a good first sliding window problem to practice?

Start with a fixed window problem, like the maximum sum of a subarray of a given size, before moving to a variable window problem like the smallest subarray with a sum at least a target value. Save the frequency-map and exactly-k variants for after those two feel automatic.

### Do I need a hash map for every sliding window problem?

Only when the window's validity depends on the distinct values or counts inside it, such as tracking distinct characters in a substring, do you actually need a hash map or frequency map. A problem that only cares about a sum or a count of elements needs just a running total, which is O(1) extra space instead of O(k).

Sliding Window Algorithm: How to Spot It Before You Code

C binary search appears in systems interviews, embedded roles, and any loop where you need explicit control over memory and indices. The logic is the same as other languages — only syntax and pointer habits differ.

For the conceptual guide (two methods, jump search, interview variants), see [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search).

## Prerequisites

- Sorted array of integers (ascending)
- Array length n passed explicitly or known from context
- O(log n) time, O(1) space for iterative code

## Worked example

Searching for 11 in the sorted array {2, 3, 7, 7, 11, 15, 25} (indices 0-6):

- lo=0, hi=6: mid=3, arr[3]=7. 7 < 11, so lo becomes 4.
- lo=4, hi=6: mid=5, arr[5]=15. 15 > 11, so hi becomes 4.
- lo=4, hi=4: mid=4, arr[4]=11. Match — return index 4.

Three comparisons instead of a seven-step linear scan. Trace this by hand before typing the loop — it confirms the invariant that the target, if present, always lies within [lo, hi], which is exactly where off-by-one bugs hide in C's pointer/index code.

## Iterative binary search

```c
int binary_search(const int *arr, int n, int x) {
    int lo = 0;
    int hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}
```

Use const int *arr when the function does not modify the array. Always compute mid as lo + (hi - lo) / 2 to avoid integer overflow.

## Recursive version

```c
int binary_search_rec(const int *arr, int x, int lo, int hi) {
    if (lo > hi) return -1;

    int mid = lo + (hi - lo) / 2;

    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binary_search_rec(arr, x, lo, mid - 1);
    return binary_search_rec(arr, x, mid + 1, hi);
}

// Call: binary_search_rec(arr, x, 0, n - 1);
```

## Complete example with main

```c
#include <stdio.h>

int binary_search(const int *arr, int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

int main(void) {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", binary_search(arr, n, 5)); // 2
    return 0;
}
```

## C-specific pitfalls

- No built-in length — pass n or track size with sizeof for static arrays only
- Unsigned pitfalls — keep lo and hi as int; mixing unsigned types breaks hi = mid - 1 when mid is 0
- Do not pointer-arithmetic past bounds — indices only
- Empty array: if n == 0, return -1 before the loop

## bsearch from stdlib

C provides bsearch in <stdlib.h>. It requires a comparator function and is less common in interviews:

```c
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

// int *found = bsearch(&key, arr, n, sizeof(int), compare);
```

Prefer writing the loop by hand in interviews.

## Complexity

- Best case: O(1) — the target is at the first mid index checked
- Average case: O(log n)
- Worst case: O(log n)
- Space: O(1) iterative, O(log n) recursive (call stack)

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — algorithm theory and interview follow-ups
- [Binary search in C++](/articles/binary-search-cpp) — STL lower_bound and upper_bound alternatives

How to Implement Binary Search in C

Python is one of the most common languages in coding interviews. If the input is sorted, binary search should be your reflex — and Python gives you both hand-rolled loops and a built-in bisect module.

For the full algorithm walkthrough (two methods, complexity, and interview variants), start with our [Binary Search Algorithm guide](/articles/binary-search).

## Prerequisites

- The array must be sorted in ascending order
- Time complexity: O(log n) per query
- Space: O(1) iterative, O(log n) recursive (call stack)

## Worked example

Searching for 11 in the sorted array [2, 3, 7, 7, 11, 15, 25] (indices 0-6):

- lo=0, hi=6: mid=3, arr[3]=7. 7 < 11, so lo becomes 4.
- lo=4, hi=6: mid=5, arr[5]=15. 15 > 11, so hi becomes 4.
- lo=4, hi=4: mid=4, arr[4]=11. Match — return index 4.

Three comparisons instead of a five-step linear scan. Trace this out loud in an interview before writing code; it confirms the loop invariant (the target, if present, always lies within [lo, hi]) and catches off-by-one mistakes before they hit the whiteboard.

## Iterative binary search

The standard interview template uses lo and hi pointers:

```python
def binary_search(arr: list[int], x: int) -> int:
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if arr[mid] == x:
            return mid
        if arr[mid] > x:
            hi = mid - 1
        else:
            lo = mid + 1

    return -1
```

Use lo + (hi - lo) // 2 instead of (lo + hi) // 2 — interviewers appreciate overflow-safe midpoint math even though Python integers do not overflow.

## Recursive version

```python
def binary_search_recursive(arr: list[int], x: int, lo: int = 0, hi: int | None = None) -> int:
    if hi is None:
        hi = len(arr) - 1

    if lo > hi:
        return -1

    mid = lo + (hi - lo) // 2

    if arr[mid] == x:
        return mid
    if arr[mid] > x:
        return binary_search_recursive(arr, x, lo, mid - 1)
    return binary_search_recursive(arr, x, mid + 1, hi)
```

Prefer iterative in timed interviews — fewer stack concerns and easier to debug on a whiteboard.

## Using bisect (production Python)

The standard library module bisect implements binary search on sorted lists:

```python
import bisect

arr = [1, 3, 5, 7, 9]
x = 5

# Index where x would be inserted (leftmost)
idx = bisect.bisect_left(arr, x)
found = idx < len(arr) and arr[idx] == x

# bisect_right — insert after existing equal elements
idx_right = bisect.bisect_right(arr, x)
```

In interviews, write the loop yourself unless the interviewer explicitly allows library calls. In production code, prefer bisect.

## Lower bound pattern

Find the first index where arr[i] >= x:

```python
def lower_bound(arr: list[int], x: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo
```

This template solves "first occurrence" and "insert position" problems. See the [main binary search guide](/articles/binary-search) for when to use lo <= hi vs lo < hi.

## Python-specific tips for interviews

- Type hints (list[int]) are optional but show clarity
- // is integer division — always use it for midpoints
- List slicing (arr[lo:hi]) creates copies — never slice in binary search; move indices instead
- Test empty list: binary_search([], 1) should return -1

## Complexity

- Best case: O(1) — the target is at the first mid index checked
- Average case: O(log n) comparisons
- Worst case: O(log n) comparisons
- Space: O(1) iterative, O(log n) recursive (call stack)

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — concepts, variants, and common mistakes
- [How to analyze time complexity](/articles/time-complexity) — why halving the range is O(log n)

How to Implement Binary Search in Python

C++ interviews often expect comfort with both raw loops and the STL algorithms library. Binary search on sorted data is O(log n) either way — know both styles.

Start with the full concept guide: [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search).

## Prerequisites

- Sorted container (vector, array, or any random-access sequence)
- O(log n) search time

## Template implementation

```cpp
#include <vector>

int binarySearch(const std::vector<int>& arr, int x) {
    int lo = 0;
    int hi = static_cast<int>(arr.size()) - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}
```

Cast arr.size() to int when mixing with signed indices, or use size_t consistently with care at boundaries.

## Generic template (interview bonus)

```cpp
template<typename T>
int binarySearch(const std::vector<T>& arr, const T& x) {
    int lo = 0, hi = static_cast<int>(arr.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}
```

## STL: lower_bound and upper_bound

The C++ standard library implements binary search in O(log n):

```cpp
#include <algorithm>
#include <vector>

std::vector<int> arr = {1, 3, 5, 5, 7, 9};
int x = 5;

// First element >= x
auto it = std::lower_bound(arr.begin(), arr.end(), x);
bool found = it != arr.end() && *it == x;
int idx = static_cast<int>(it - arr.begin());

// First element > x
auto it2 = std::upper_bound(arr.begin(), arr.end(), x);

// std::binary_search returns bool only
bool exists = std::binary_search(arr.begin(), arr.end(), x);
```

lower_bound / upper_bound are essential for "first/last occurrence" and range-count problems.

## Recursive version

```cpp
int binarySearchRec(const std::vector<int>& arr, int x, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearchRec(arr, x, lo, mid - 1);
    return binarySearchRec(arr, x, mid + 1, hi);
}
```

## Binary search on the answer space

Interviewers often ask a variant that is not "search an array" but "search a range of possible answers" — minimum capacity to ship packages in D days, smallest divisor so a sum stays under a threshold, that kind of problem. The array is gone; you binary search over the space of possible answers using a monotonic predicate (a function that is false then true as the answer increases).

```cpp
#include <vector>

// Example predicate: "can we finish with capacity mid?" — replace with your problem's check.
bool canFinish(const std::vector<int>& weights, int days, int capacity) {
    int daysNeeded = 1;
    int load = 0;
    for (int w : weights) {
        if (load + w > capacity) {
            daysNeeded++;
            load = 0;
        }
        load += w;
    }
    return daysNeeded <= days;
}

int minCapacity(const std::vector<int>& weights, int days) {
    int lo = *std::max_element(weights.begin(), weights.end());
    int hi = 0;
    for (int w : weights) hi += w;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(weights, days, mid)) {
            hi = mid;      // mid works — try smaller
        } else {
            lo = mid + 1;  // mid fails — need bigger
        }
    }
    return lo;
}
```

Note the loop condition is lo < hi, not lo <= hi — this is the "find the boundary" template, different from the classic find-exact-value template above. lo converges to the smallest value where the predicate is true. Recognize the shape: no sorted array in sight, but the answer space is monotonic, so binary search still applies in O(log(range)) time.

## C++ interview tips

- Prefer vector over raw arrays — size is tracked
- Avoid arr[mid] with unsigned mid when hi can underflow — stick to signed int indices in the classic template
- State complexity: O(log n) time, O(1) space (iterative)
- When allowed, STL calls show library fluency; when asked to implement, use the while loop

## Complexity

- Time: O(log n)
- Space: O(1) iterative, O(log n) recursive

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — core algorithm and variants
- [Binary search in C](/articles/binary-search-c) — pointer-based version without STL
- [How to analyze time complexity](/articles/time-complexity) — Big O fundamentals

How to Implement Binary Search in C++

Sorting is one of the most frequently tested topics in coding interviews. You rarely need to implement a full sort from scratch, but you must know the time and space trade-offs cold — and explain why your chosen approach fits the problem constraints.

## Why interviewers ask about sorting

- Many problems reduce to "find the k-th element" or "group similar items" — sorting is often the brute-force baseline.
- Follow-ups probe whether you know faster alternatives (heaps, counting sort, bucket sort).
- System design loops sometimes ask how databases or distributed systems sort large datasets.

## Comparison-based sorts

### Bubble Sort

O(n²) time, O(1) space. Compare adjacent pairs and swap. Simple but almost never the right answer in interviews. Mention it only to contrast with better options.

### Selection Sort

O(n²) time, O(1) space. Repeatedly pick the minimum from the unsorted portion. Still O(n²) but performs fewer swaps than bubble sort. Rarely used in practice.

### Insertion Sort

O(n) best, O(n²) average/worst, O(1) space. Builds a sorted prefix one element at a time. Excellent for nearly sorted data or small n (often n < 50). Python's Timsort uses insertion sort for small runs.

### Shell Sort

O(n log n) to O(n²) depending on gap sequence, O(1) space. A generalization of insertion sort: compare and swap elements far apart first (using a shrinking gap sequence), then narrow the gap down to 1. Moves out-of-place elements into position faster than plain insertion sort. Rarely asked to implement, but a good answer when asked "how would you speed up insertion sort without extra memory?".

### Merge Sort

O(n log n) time in all cases, O(n) space. Divide the array in half, sort each half, merge. Stable, predictable, and great when you need guaranteed O(n log n). Downside: extra memory for the merge step.

### Quick Sort

O(n log n) average, O(n²) worst, O(log n) space for recursion stack. Pick a pivot, partition, recurse. In-place and cache-friendly — the default in most standard libraries (with randomized pivot or introsort to avoid worst case). Unstable unless implemented carefully.

### Heap Sort

O(n log n) time in all cases, O(1) space. Build a max-heap, repeatedly extract the maximum. Guaranteed O(n log n) with no extra array, but slower constants than quicksort in practice. Useful when memory is tight and you need worst-case guarantees.

### Timsort

O(n log n) worst case, O(n) best case (already-sorted runs), O(n) space. A hybrid of merge sort and insertion sort: splits the input into small runs, sorts each run with insertion sort, then merges runs with merge sort's merge step. Stable, and adapts to partially-sorted real-world data. This is what Python's `sorted()` / `list.sort()` and Java's `Arrays.sort()` (for objects) use in production — worth naming if asked what a language's built-in sort actually does.

## Non-comparison sorts

### Counting Sort

O(n + k) time, O(k) space where k is the range of input values. Works when values are small integers in a known range. Stable when implemented with prefix sums.

### Radix Sort

O(d · (n + k)) time where d is the number of digits/pass. Sorts digit-by-digit using a stable sub-sort (usually counting sort). Used for fixed-width integers or strings of bounded length.

### Bucket Sort

O(n) average when inputs are uniformly distributed across buckets, O(n²) worst if all elements land in one bucket. Good for floating-point values in [0, 1).

## Quick reference

Bubble Sort — O(n²) / O(1) / stable. Selection Sort — O(n²) / O(1) / unstable. Insertion Sort — O(n²) avg, O(n) best / O(1) / stable. Shell Sort — O(n log n) to O(n²) / O(1) / unstable.

Merge Sort — O(n log n) / O(n) / stable. Quick Sort — O(n log n) avg, O(n²) worst / O(log n) stack / unstable. Heap Sort — O(n log n) / O(1) / unstable.

Timsort — O(n log n) worst, O(n) best / O(n) / stable. Counting Sort — O(n + k) / O(k) / stable. Radix Sort — O(n · d) / O(n + k) / stable. Bucket Sort — O(n) avg / O(n) / stable.

## The Ω(n log n) lower bound

Any comparison-based sort must make at least Ω(n log n) comparisons in the worst case. That is why merge sort, heap sort, and quicksort (average) are optimal for general comparison sorting — you cannot do better without exploiting structure in the input.

## When to say which in an interview

- Default answer for general arrays: quicksort or mergesort. Quicksort for in-place; mergesort when stability matters or worst-case O(n log n) is required.
- Small or nearly sorted input: insertion sort.
- Need top-k elements without full sort: use a min-heap of size k — O(n log k) instead of O(n log n).
- Integers in a small range: counting sort or bucket sort.
- Linked lists: mergesort is natural because merge is O(1) extra space per node (no random access needed).

## Common follow-up questions

### Why is quicksort O(n²) worst case?

Adversarial or sorted input with a bad pivot (first/last element) causes unbalanced partitions. Fix with random pivot or introsort (switch to heapsort when recursion depth exceeds a threshold).

### Is mergesort or quicksort better?

Quicksort wins on average for in-place array sorting due to cache locality. Mergesort wins when stability is required, data is linked, or you need predictable performance.

### Can you sort in O(n) time?

Only with non-comparison sorts when input has structure (bounded integer range, fixed digit count). Otherwise no — cite the comparison lower bound.

### What does JavaScript's Array.sort use?

V8 uses Timsort (a hybrid of mergesort and insertion sort), which adapts to partially ordered data.

## Practice tip

Before your next loop, pick three problems from our coding question bank and state aloud which sort (if any) you would use and why. Interviewers care less about memorizing every constant factor and more about matching the algorithm to constraints: stability, memory, input distribution, and whether you need the full sorted order or just the k-th element.

Sorting Algorithms: Time Complexity Cheat Sheet for Interviews

Nearly every coding interview ends with: "What's the time complexity?" You are not being asked to count CPU cycles. Interviewers want to know whether your approach scales — and whether you can spot bottlenecks before they become bugs in production.

Big O describes how runtime grows as input size grows. It ignores constants and lower-order terms, which is why O(3n + 50) is still O(n). If you can state complexity confidently and tie it back to your code structure, you signal senior-level thinking even on medium problems.

## What Big O actually means

We write O(f(n)) to say: "For large enough input, runtime grows no faster than f(n)." The variable n almost always means the primary input size — array length, string length, number of nodes. When two inputs matter (a grid with n rows and m columns), use both: O(nm).

Interview tip: always define n out loud before analyzing. "Let n be the number of users in the feed" removes ambiguity and buys you a few seconds to think.

## Reading loops

Loops are the fastest way to estimate complexity. Count how many times the innermost work runs relative to n.

Single pass — O(n). One loop over the input:

```javascript
for (let i = 0; i < nums.length; i++) {
  // constant work
}
```

Nested loops — O(n²). Every element paired with every other element:

```javascript
for (let i = 0; i < nums.length; i++) {
  for (let j = 0; j < nums.length; j++) {
    // constant work
  }
}
```

Triangle loop — still O(n²). The inner loop starts at i, not 0, but you still iterate roughly n²/2 times:

```javascript
for (let i = 0; i < nums.length; i++) {
  for (let j = i + 1; j < nums.length; j++) {
    // compare pairs
  }
}
```

Rule of thumb: k nested loops that each scale with n → O(n^k). Three nested loops over n → O(n³).

## Constants do not change Big O

These loops all look different but are all O(n):

```javascript
for (let i = 0; i < 3 * n; i++) { /* ... */ }
for (let i = 0; i < n + 100; i++) { /* ... */ }
for (let i = 0; i < n; i += 2) { /* ... */ }
```

Interviewers care about growth rate, not whether you loop 2n or 5n times. Drop constants when you speak: say O(n), not O(2n).

## Multiple passes add, but watch the max

When code runs in sequential phases, the slowest phase dominates.

```javascript
function process(nums) {
  nums.forEach(() => { /* O(n) */ });

  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      /* O(n²) */
    }
  }

  nums.sort(); // O(n log n)
}
```

Total: O(n) + O(n²) + O(n log n) = O(n²). The quadratic nested loop is the bottleneck. Mention that explicitly — it shows you know which line matters.

## Two inputs: use two variables

Grids, graphs, and string matching often depend on two dimensions:

```javascript
for (let i = 0; i < n; i++) {
  for (let j = 0; j < m; j++) {
    // visit cell (i, j)
  }
}
```

Complexity is O(nm), not O(n²), unless m and n are the same. For a square grid, say O(n²). For comparing two strings of length n and m, many DP solutions are O(nm).

## Recursion: multiply calls × work per call

Recursive runtime = (number of calls) × (work per call, excluding deeper recursion).

Linear recursion — O(n). One recursive call per level:

```javascript
function countdown(n) {
  if (n === 0) return;
  countdown(n - 1);
}
```

n calls, O(1) each → O(n).

Binary recursion — O(2^n). Two calls branch each level (think naive Fibonacci):

```javascript
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
```

The call tree doubles at each level. Total calls grow exponentially — roughly O(2^n). In interviews, name this immediately and offer memoization or bottom-up DP to bring it to O(n).

Divide and conquer — often O(n log n). Merge sort splits in half (log n levels) and does O(n) merge work per level → O(n log n). Same pattern appears in fast FFT-style problems and some tree algorithms.

## Complexity cheat sheet for interviews

Memorize the ordering. When comparing approaches, refer to where each sits on this ladder:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)

### O(1) — constant

Hash map lookup, array index access, pushing to a stack. Does not grow with input size.

### O(log n) — logarithmic

Binary search, balanced BST operations, repeatedly halving the search space. If you eliminate half the remaining data each step, think log n.

### O(n) — linear

Single scan, two pointers on a sorted array, BFS/DFS when each node is visited once. Often the best you can do if you must examine every element.

### O(n log n) — linearithmic

Efficient sorting, merge sort, heap operations over n items, divide-and-conquer with linear combine step. If your solution sorts the full input, start here.

### O(n²) — quadratic

Nested loops, brute-force pair checking, simple DP on small grids. Common in naive solutions — interviewers often ask how you'd improve it.

### O(2^n) and O(n!) — exponential / factorial

Generating all subsets or all permutations. Fine for n ≤ 20 in backtracking problems; unusable at scale. Name the pattern when you see bitmask or "try every ordering" approaches.

## What interviewers want to hear

1. State Big O for time and space after you describe the approach — not after you finish coding.
2. Tie complexity to a line of code — "The nested loop over pairs gives O(n²)."
3. Compare to alternatives — "Sorting first is O(n log n); a hash map lookup is O(n) average."
4. Call out trade-offs — O(n) extra space for O(n) time is a deliberate exchange.

You do not need formal proofs. You need a consistent method: find the hot loop, count how many times it runs, express it in terms of n, drop constants, keep the dominant term.

## When your solution might be too slow

Typical online judges and interview platforms handle roughly:

- O(n) or O(n log n) — safe for n up to 10⁶ or more
- O(n²) — fine for n ≈ 10³–10⁴
- O(2^n) — only when n ≤ 20–25

If your brute force is O(n²) and constraints say n = 10⁵, stop and rethink before coding. That constraint is a hint.

## Practice on real problems

Work through the study guide on [LRU Cache](/questions/lru-cache) — every operation is O(1) and you should explain why. Then compare with [Merge Intervals from Data Stream](/questions/merge-intervals-stream), where the heap gives O(log n) per insertion.

## Data structure operations: the Big O cheat sheet

Algorithm complexity gets the attention, but interviewers assume you already know operation costs for the data structures you reach for. Access, search, insert, and delete, per structure:

- Array (fixed size) — access O(1), search O(n), insert O(n) (shift required), delete O(n) (shift required)
- Dynamic array (vector / ArrayList) — access O(1), search O(n), insert at end O(1) amortized, insert/delete at an arbitrary index O(n)
- Singly linked list — access O(n), search O(n), insert/delete at a known node O(1), insert/delete by value O(n) (must find it first)
- Hash map / hash set — search O(1) average, O(n) worst case (hash collisions); insert and delete are the same O(1) average, O(n) worst
- Binary search tree, unbalanced — search, insert, delete O(log n) average, O(n) worst case (degenerates to a linked list on sorted input)
- Balanced BST (red-black tree, AVL) — search, insert, delete O(log n) guaranteed, no worst-case degradation
- Binary heap — find min/max O(1), insert O(log n), extract min/max O(log n), build-heap from an unsorted array O(n)
- Stack and queue (array or linked-list backed) — push, pop, enqueue, dequeue all O(1)
- Trie — search and insert O(L), where L is the length of the key, independent of how many keys are stored

Say "average case" out loud for hash maps — interviewers who ask about worst case want to hear that a bad hash function or adversarial input causes O(n) collisions, and that a good hash function makes this rare enough to ignore in practice.

## Related reading

- [Sorting algorithms: time complexity cheat sheet](/articles/sorting-algorithms-time-complexity) — where O(n log n) shows up in practice.

How to Analyze Time Complexity in Coding Interviews

LeetCode patterns are not a list to memorize. They are signals hiding in the problem statement, and the interview reward goes to whoever spots the signal fastest, not whoever has solved the most problems.

## What Are LeetCode Patterns, Really?

A pattern is a reusable strategy that solves a whole family of problems, not just one. Sliding window solves subarray and substring problems. Two pointers solves sorted-array and linked-list problems. Binary search solves anything with a monotonic search space, not just sorted arrays. Once you see the strategy behind a problem instead of the problem itself, a question you have never seen stops looking unfamiliar.

Ten to twelve patterns cover the large majority of questions asked in real coding interviews: sliding window, two pointers, modified binary search, BFS, DFS, dynamic programming, backtracking, topological sort, union-find, and a handful of heap or interval variants. Learn the signal for each one and you can approach a brand-new problem with a plan in the first thirty seconds instead of staring at it.

## Why Doesn't Memorizing a List of Patterns Work?

Most pattern lists online give you a name and three example problems, then move on. That gets you exactly one thing: the ability to recognize a problem you have already seen. It does nothing for the problem you have not seen, which is what an actual interview gives you.

The skill that transfers is recognition from the problem statement itself, before you touch the constraints or think about code. Every pattern has a small set of phrases and shapes that tip you off. Learn those signals instead of memorizing solved problems, and pattern recognition works on a question you are reading for the first time, live, with someone watching.

The rest of this guide walks through each major pattern the same way: what to look for, why that signal points to that pattern, and where it breaks down.

## How Do You Recognize the Sliding Window Pattern?

Sliding window applies when you need a contiguous subarray or substring that satisfies some condition, and shrinking or growing a window is cheaper than recomputing from scratch every time.

Signal phrases: "contiguous subarray", "substring", "at most k distinct", "longest run", "maximum sum of size k". Any time the word contiguous shows up next to subarray or substring, check window first.

```text
Example: "Find the longest substring with at most two distinct characters."
Signal: substring + a bounded count constraint = shrink the window when the
constraint breaks, grow it otherwise.
```

Where it breaks down: if the problem allows non-contiguous selection, or the answer depends on elements outside the current window, sliding window stops being a clean fit. Watch for "any subsequence" instead of "any subarray" - that single word swap usually rules the pattern out.

## How Do You Recognize the Two Pointers Pattern?

Two pointers applies when the input is sorted, or can be sorted without losing what the problem asks for, and you are looking for a pair, triplet, or partition point.

Signal phrases: "pair that sums to", "sorted array", "remove duplicates in place", "partition around a value". The sorted-array signal is the strongest one: if a problem hands you a sorted array and asks about pairs, two pointers is almost always faster than the nested loop your first instinct reaches for.

```text
Example: "Given a sorted array, find two numbers that add up to a target."
Signal: sorted input + pair search = start pointers at both ends and move
based on whether the current sum is too high or too low.
```

Where it breaks down: unsorted input with no sort step allowed, or a problem that needs every pair rather than just one, usually rules it out.

## How Do You Recognize a Binary Search Pattern?

Binary search is not only for finding a value in a sorted array. It applies to any problem where you can ask "is this answer good enough" and get a yes-or-no result that flips exactly once as you move across the search space.

Signal phrases: "minimize the maximum", "find the smallest value such that", "search a rotated sorted array". That "smallest value such that" phrasing is the giveaway for search-on-the-answer problems, a variant a lot of candidates miss because there is no literal sorted array in sight.

A full walkthrough of binary search mechanics, including five language implementations, lives in [our binary search guide](/articles/binary-search) - worth a read if this pattern feels shaky.

Where it breaks down: if the search space is not monotonic, meaning the yes/no answer can flip back and forth instead of flipping once, binary search does not apply no matter how sorted the input looks.

## How Do You Recognize BFS and DFS Problems?

Both traverse a graph or tree, and the words in the problem tell you which one to reach for.

BFS signal phrases: "shortest path", "minimum number of steps", "level by level". Anything asking for a minimum number of hops or steps in an unweighted graph wants BFS, because BFS explores in order of distance from the start.

DFS signal phrases: "all paths", "connected components", "does a path exist", "explore as far as possible". If the question wants every possibility rather than the shortest one, or just wants to know whether something is reachable, DFS (often with memoization) is the simpler tool.

```text
Example: "Find the shortest path from a start cell to an end cell in a grid,
moving only through open cells."
Signal: shortest + unweighted grid = BFS, not DFS. A DFS solution would find
a path, but not necessarily the shortest one, without extra bookkeeping.
```

Where it breaks down: a weighted graph needs Dijkstra's algorithm instead of plain BFS, and that distinction is worth naming out loud if you spot weights on the edges.

## How Do You Recognize a Dynamic Programming Problem?

Dynamic programming applies when a problem can be broken into overlapping subproblems, meaning the brute-force recursive solution recomputes the same smaller answer many times.

Signal phrases: "number of ways to", "minimum cost to reach", "longest common", "maximum profit with constraints". The phrase "number of ways" is one of the strongest DP signals in interview questions, because counting problems almost always decompose into smaller counting problems.

The fastest way to confirm a hunch: sketch the brute-force recursive solution first, even just in your head. If you can point to the same subproblem being solved twice, memoize it. That single check turns a vague "this might be DP" into a confirmed plan before you write a line of code.

Where it breaks down: if subproblems do not overlap, you have plain recursion or divide and conquer, not DP, and adding memoization would do nothing useful.

## How Do You Recognize Backtracking, Topological Sort, and Union-Find?

These three show up less often than the patterns above, but each has a distinct, easy-to-catch signal.

Backtracking signal phrases: "generate all", "all permutations", "all valid combinations". Any time a problem wants every valid arrangement rather than one optimal answer, you are building and unwinding a partial solution, which is backtracking.

```text
Example: "Generate all valid combinations of well-formed parentheses for n pairs."
Signal: generate all + a validity rule at each step = build one character at
a time, backtrack the moment a partial choice breaks the rule.
```

Topological sort signal phrases: "course prerequisites", "build order", "task scheduling with dependencies". A dependency graph where some things must happen before others, and the question asks for a valid order, is a topological sort problem almost every time.

```text
Example: "Given course prerequisites, return a valid order to take all courses."
Signal: prerequisites + a valid order requested = topological sort;
a cycle in the dependency graph means no valid order exists at all.
```

Union-find signal phrases: "connected groups", "merge accounts", "redundant connection". Anything about grouping items into connected sets, especially when the groups merge as you process more input, points to union-find over a fresh graph traversal for every query.

```text
Example: "Given pairs of accounts that share an email, merge all accounts
belonging to the same person."
Signal: pairs that merge groups over time = union-find, since re-running a
full graph traversal after every new pair would waste the work already done.
```

## How Do You Recognize Heap and Interval Problems?

Heap-based problems and interval problems get grouped together because they share a common trigger: you need the current best or current overlap out of a changing set, not the full sorted set.

Heap signal phrases: "kth largest", "top k frequent", "merge k sorted lists", "median of a stream". Any time a problem asks for the kth something, or the running best as data keeps arriving, a heap keeps that answer available in log n time without re-sorting everything on every update.

```text
Example: "Find the kth largest element in a stream of numbers."
Signal: kth + stream = maintain a heap of size k instead of re-sorting after
every new number.
```

Interval signal phrases: "merge overlapping intervals", "meeting rooms", "insert an interval", "minimum number of platforms". These almost always start with sorting the intervals by start time, then walking through once to merge or count overlaps, which turns an apparent scheduling problem into a single linear pass after the sort.

Where these break down: if the data does not need a running best, a full sort is simpler than a heap. And if intervals are not actually ordered by a meaningful axis like time, the sort-then-sweep approach for interval problems will not apply cleanly.

## How Should You Talk Through Pattern Recognition in the Interview?

Name the pattern out loud as soon as you spot the signal, before you start coding. Something as short as "the sorted input and the pair search tell me this is a two-pointer problem" does two things at once: it shows the interviewer your reasoning instead of just your syntax, and it gives them a chance to redirect you early if you have misread the problem.

Tie the pattern back to complexity while you are at it. If you already have a feel for how [time complexity works in interviews](/articles/time-complexity), say the Big O of your chosen approach before you code it, and compare it to the brute-force alternative you are skipping. "Brute force is O(n squared) with nested loops; two pointers gets this to O(n) after a single sort" is a complete, confident sentence that costs you five seconds and buys real credit.

If you guess wrong, say so and pivot. "I initially thought sliding window, but the subsequence in this problem does not need to be contiguous, so I am switching to a DP approach instead" reads as stronger signal than silently backtracking, because it shows you can catch your own mistake.

## How Do You Build Pattern Recognition Without Memorizing 500 Problems?

Depth beats breadth for pattern recognition specifically. Solve four or five problems inside one pattern before moving to the next, and spend real time after each one asking what phrase in the problem statement should have tipped you off from the start, not just whether your solution passed.

Mixing patterns matters just as much once you have the individual signals down. A block of problems that are all sliding window in a row teaches you nothing about telling sliding window apart from two pointers under pressure, because you already know which pattern to reach for before you read the question. Real interviews do not announce the pattern in advance, so your practice should not either.

A practical structure for four weeks looks like this: week one, sliding window and two pointers, five problems each, since both operate on similar array-scanning intuition and pair well for comparison. Week two, BFS and DFS, again five problems each, deliberately mixed with a few from week one so the signal has to be re-identified instead of assumed. Week three, dynamic programming alone, since it is the pattern most candidates under-practice relative to how often it appears. Week four, backtracking, topological sort, union-find, heaps, and intervals together, mixed with everything from the previous three weeks. By the end of that mix, you are reading a new problem and asking "which of these ten signals is present" instead of "have I seen this exact question before."

Curated, currently-relevant problems save real time here, since a stale or unfiltered problem list makes it harder to tell which patterns are actually showing up in interviews right now versus which ones were common five years ago. [Our question bank](/questions) is organized so you can practice one pattern in depth, then mix it back in with others once the signal feels automatic, using problems sourced from actual candidate reports rather than a static public list.

## Frequently Asked Questions

### How many LeetCode patterns do I actually need to know?

Ten to twelve core patterns cover the large majority of questions in real coding interviews: sliding window, two pointers, binary search, BFS, DFS, dynamic programming, backtracking, topological sort, union-find, and heap or interval variants. Going deep on these beats a shallow pass over fifty named patterns.

### How long does it take to learn one pattern well?

Two to three days per pattern is a reasonable pace for most candidates: one day to learn the signal and mechanics, then several problems over the following days to make the recognition automatic rather than something you have to think through each time.

### Can a problem use more than one pattern?

Yes, and interviewers often design questions this way on purpose. A problem might need a sliding window to find a candidate range, then binary search to narrow it further. Naming both patterns as you move between them shows the interviewer you are tracking the shift, not just producing code.

### Is it better to learn patterns or just solve as many problems as possible?

Learn the patterns before racking up a raw problem count. Solving problems without an organizing framework means each new question feels like starting over, while learning the signal behind ten to twelve patterns lets you transfer what you know to problems you have never seen, which is the actual skill being tested.

### What should I do if I do not recognize any pattern in a problem?

Say so, out loud, and start from what you do know: restate the problem in your own words, work a small example by hand, and look for repeated sub-steps as you do. Naming your process, even without a pattern name attached yet, is far stronger than silence while you search your memory for a label.

LeetCode Patterns: How to Spot Them Before You Code

Go's simplicity makes binary search easy to read on a whiteboard — slices, integer indices, and no hidden overflow surprises with size_t. Many backend interviews use Go; this pattern shows up constantly.

For algorithm theory and interview variants, read [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) first.

## Prerequisites

- Slice sorted in ascending order
- **O(log n)** time, **O(1)** extra space (iterative)

## Iterative binary search

```go
func binarySearch(arr []int, x int) int {
    lo, hi := 0, len(arr)-1

    for lo <= hi {
        mid := lo + (hi-lo)/2

        if arr[mid] == x {
            return mid
        }
        if arr[mid] > x {
            hi = mid - 1
        } else {
            lo = mid + 1
        }
    }

    return -1
}
```

Go integers are signed and arbitrary precision is not an issue for indices — `(lo + hi) / 2` is usually safe, but `lo + (hi-lo)/2` is still the interview-standard form.

## Recursive version

```go
func binarySearchRec(arr []int, x, lo, hi int) int {
    if lo > hi {
        return -1
    }
    mid := lo + (hi-lo)/2

    if arr[mid] == x {
        return mid
    }
    if arr[mid] > x {
        return binarySearchRec(arr, x, lo, mid-1)
    }
    return binarySearchRec(arr, x, mid+1, hi)
}

// Call: binarySearchRec(arr, x, 0, len(arr)-1)
```

## sort.Search (idiomatic Go)

The standard library uses binary search internally:

```go
import "sort"

arr := []int{1, 3, 5, 7, 9}
x := 5

// Smallest index i where arr[i] >= x
idx := sort.Search(len(arr), func(i int) bool {
    return arr[i] >= x
})

found := idx < len(arr) && arr[idx] == x
_ = found
```

`sort.Search` is the Go equivalent of lower bound. It returns `len(arr)` if no element satisfies the predicate.

## Lower bound helper

```go
func lowerBound(arr []int, x int) int {
    lo, hi := 0, len(arr)
    for lo < hi {
        mid := lo + (hi-lo)/2
        if arr[mid] < x {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}
```

Use when the problem asks for insertion point or first index where `arr[i] >= x`.

## Go-specific tips

- Check empty slice: `if len(arr) == 0 { return -1 }`
- Slices are references — no copying when passing to functions
- Naming: `lo`/`hi` or `left`/`right` — stay consistent
- Run tests with `go test` and table-driven cases in real projects

## Example test

```go
func TestBinarySearch(t *testing.T) {
    arr := []int{1, 3, 5, 7, 9}
    if got := binarySearch(arr, 5); got != 2 {
        t.Fatalf("got %d, want 2", got)
    }
    if got := binarySearch(arr, 4); got != -1 {
        t.Fatalf("got %d, want -1", got)
    }
}
```

## Complexity

- **Time:** O(log n)
- **Space:** O(1) iterative, O(log n) recursive

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — full walkthrough and common mistakes
- [How to analyze time complexity](/articles/time-complexity) — why binary search is O(log n)

How to Implement Binary Search in Go

Java remains a top language for FAANG-style interviews. Binary search on sorted arrays is a must-know pattern — and Java's integer overflow rules make midpoint calculation especially worth getting right.

Read the language-agnostic explanation first: [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search).

## Prerequisites

- Input array sorted ascending
- **O(log n)** time per search, **O(1)** space (iterative)

## Iterative implementation

```java
public static int binarySearch(int[] arr, int x) {
    int lo = 0;
    int hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}
```

**Critical in Java:** never write `int mid = (lo + hi) / 2` on large arrays — `lo + hi` can overflow. Always use `lo + (hi - lo) / 2`.

## Recursive implementation

```java
public static int binarySearchRecursive(int[] arr, int x, int lo, int hi) {
    if (lo > hi) return -1;

    int mid = lo + (hi - lo) / 2;

    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearchRecursive(arr, x, lo, mid - 1);
    return binarySearchRecursive(arr, x, mid + 1, hi);
}

// Call: binarySearchRecursive(arr, x, 0, arr.length - 1);
```

Recursive depth is O(log n) — safe for arrays up to millions of elements.

## Arrays.binarySearch

Java provides a built-in binary search:

```java
import java.util.Arrays;

int[] arr = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(arr, 5); // returns 2 if found

// If not found, returns -(insertionPoint) - 1
int missing = Arrays.binarySearch(arr, 4); // negative index
```

Decode negative results: `insertionPoint = -(result + 1)`. In interviews, implement manually unless told otherwise.

## Lower bound (first index >= x)

```java
public static int lowerBound(int[] arr, int x) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
```

Use this for "first occurrence" and sorted insertion point problems.

## Java interview tips

- Use `int[]` unless the problem requires objects — autoboxing adds noise
- Guard empty input: `if (arr.length == 0) return -1;`
- For `List<Integer>`, convert to array or use indexed `get(mid)` — avoid `subList` copies
- Mention **O(log n)** time and **O(1)** auxiliary space when done

## Complexity

- **Time:** O(log n)
- **Space:** O(1) iterative, O(log n) recursive stack

## Related reading

- [Binary Search Algorithm: A Coding Interview Guide](/articles/binary-search) — full algorithm explanation and variants
- [How to analyze time complexity](/articles/time-complexity) — Big O and loop analysis

How to Implement Binary Search in Java

Binary search is one of the highest-leverage patterns in coding interviews. Once you recognize "sorted input" or "find boundary in monotonic space," you can often drop from O(n) to O(log n) — and interviewers will expect you to.

This guide covers the core idea, two standard implementations, and the follow-ups that separate a passing answer from a strong one.

## When linear search is enough

The straightforward way to find a value in an array is a single loop:

```javascript
function linearSearch(arr, x) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === x) return i;
  }
  return -1;
}
```

Time complexity: **O(n)** — in the worst case you inspect every element. If the array is unsorted and you have no extra structure, that is optimal. There is no shortcut without additional information.

## Why sorting unlocks O(log n)

When the array is **sorted ascending**, order tells you where to look next. Compare against the middle element:

- Equal → found
- Target is smaller → search the left half only
- Target is larger → search the right half only

Each comparison eliminates half the remaining elements. That halving is what gives **O(log n)** time.

Interview tip: say this out loud before coding — "I'll maintain a search range and cut it in half each step."

## Method 1: Classic range search

Think of looking up a word in a dictionary. You keep an active range `[lo, hi]` that starts as the full array. Repeatedly inspect the midpoint and narrow to the left or right half.

```javascript
function binarySearch(arr, x) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === x) return mid;
    if (arr[mid] > x) hi = mid - 1;
    else lo = mid + 1;
  }

  return -1;
}
```

The active region shrinks by at least half each iteration, so the loop runs at most **⌈log₂(n + 1)⌉** times → **O(log n)**.

### Avoid integer overflow

In languages like Java or C++, `lo + hi` can overflow. Use `lo + (hi - lo) / 2` (shown above). In JavaScript numbers are doubles so overflow is rare, but interviewers still like hearing you know the idiom.

### Loop invariant to remember

When the loop ends with `lo > hi`, the target is not present. Some variants use `lo < hi` for "first position where…" problems — know which template you are using and stick to it.

## Method 2: Jump search with shrinking step size

A second pattern scans left to right but jumps in large steps, then halves the jump size as you hone in — like galloping across the array and slowing down near the target.

Start with jump length `b = ⌊n/2⌋`. For each jump size (n/2, n/4, n/8, … down to 1), advance the pointer while the landing spot is still safe and not past the target. After all jumps, check the final index.

```javascript
function binarySearchJump(arr, x) {
  const n = arr.length;
  let k = 0;

  for (let b = Math.floor(n / 2); b >= 1; b = Math.floor(b / 2)) {
    while (k + b < n && arr[k + b] <= x) {
      k += b;
    }
  }

  if (arr[k] === x) return k;
  return -1;
}
```

The inner `while` moves `k` forward at most once per jump level, and there are O(log n) levels — still **O(log n)** overall.

This variant is less common in live coding but useful for **lower bound** style problems (first index where value ≥ x). Many standard libraries expose this as `bisect_left` / `lower_bound`.

## Beyond "find exact value"

Interviewers rarely ask for vanilla search on a plain array. They ask variants:

- **First / last occurrence** of x in a sorted array with duplicates
- **Search in rotated sorted array**
- **Find peak / minimum in rotated array**
- **Binary search on answer** — monotonic predicate over the answer space (e.g. "minimum capacity to ship packages in D days")

The template changes slightly, but the engine is the same: maintain a range, discard half based on a comparison.

## Complexity summary

- **Linear scan** — unsorted OK, O(n) time, O(1) space
- **Binary search (Method 1)** — sorted required, O(log n) time, O(1) space
- **Jump binary (Method 2)** — sorted required, O(log n) time, O(1) space

Recursive binary search uses O(log n) call stack space — mention that if you implement it recursively instead of iteratively.

## Common mistakes in interviews

- Forgetting to handle **empty array** or single-element edge cases
- Off-by-one errors on `hi = mid - 1` vs `hi = mid` in lower-bound templates
- Using binary search on unsorted data without sorting first (adds O(n log n) preprocessing)
- Infinite loops when `lo` and `hi` do not converge — test with 2-element arrays

## How to practice

1. Implement Method 1 from memory on a whiteboard.
2. Solve "find first and last position of element" on LeetCode-style platforms.
3. Apply the [coding interview framework](/coding) — clarify sorted order, walk an example, then code.
4. State **O(log n)** time and **O(1)** extra space before you run test cases.

## Related reading

### Implementations by language

- [Binary search in Python](/articles/binary-search-python)
- [Binary search in Java](/articles/binary-search-java)
- [Binary search in C](/articles/binary-search-c)
- [Binary search in C++](/articles/binary-search-cpp)
- [Binary search in Go](/articles/binary-search-go)

### More algorithm guides

- [How to analyze time complexity](/articles/time-complexity) — why halving the search space is O(log n)
- [Sorting algorithms: time complexity cheat sheet](/articles/sorting-algorithms-time-complexity) — when you sort first, then binary search

Binary Search Algorithm: A Coding Interview Guide

Object-oriented design interviews test whether you can model real-world systems with clear abstractions.

## Clarify requirements first

Start by clarifying requirements: what entities exist, what actions users perform, and what scale constraints apply. Sketch core classes and their relationships before writing code.

## Patterns interviewers look for

- Single responsibility for each class
- Encapsulation of state
- Extensibility for new vehicle types, payment methods, or notification channels

## Next steps

Practice with our OOD question bank — Parking Lot is a great starting point.

How to Approach OOD Interviews

SQL questions in SDE interviews often focus on practical analytics rather than exotic syntax.

## Core patterns to master

- Ranking with ROW_NUMBER, DENSE_RANK, and RANK
- Aggregations with GROUP BY and HAVING
- Self-joins for comparing rows within the same table
- Window functions for running totals and Nth highest values

## Practice with real problems

Our SQL question bank includes real problems like Second Highest Salary by Department — practice the pattern, then explain your indexing strategy as a follow-up.

SQL Patterns Every SDE Should Know

System design interviews reward structured thinking over memorized architectures.

## The 45-minute timeline

1. Requirements (5 min) — functional vs non-functional, clarify scope
2. Estimation (5 min) — QPS, storage, bandwidth back-of-envelope
3. High-level design (10 min) — boxes and arrows, data flow
4. Deep dive (15 min) — database choice, caching, bottlenecks
5. Wrap-up (10 min) — trade-offs, monitoring, failure modes

## Where to practice

Browse our System Design section for questions like URL Shortener with full walkthroughs.

A 45-Minute System Design Framework

Read guides to complement your question bank practice.

Interview prep guides, strategies, and deep dives.