Chapter 3 Arrays

Arrays show up in almost every interview. This chapter opens with a refresher on iterating combinations and fundamental array algorithms before diving into the most popular LeetCode array problems.

3.0.1 Iterating Combinations

If we are enumerating the cartesian products over two arrays of n elements.

A = [A_1, A_2, ..., A_n]
B = [B_1, B_2, ..., B_n]
A1 X A2 = [(A_1, B_1), (A_1, B_2), ..., (A_n, B_n)]

The time complexity is O(n^2).

for(int i = 0; i < A.length; i++) {
    for(int j = 0; j < B.length; j++) {
        // process each (A_i, B_j)
    }
}

If we only need to enumerate part of the combination over two arrays while traversing both arrays simultaneously.

A = [A_1, A_2, ..., A_n]
B = [B_1, B_2, ..., B_n]
A1 X A2 = [(A_1, B_1), (A_2, B_1), (A_2, B_2), ..., (A_n, B_n)]

we could possibly reduce the complexity to O(n)

for(int i = 0, j = 0; i < A.length; j < B.length;) {
    int a = A[i];
    int b = B[j];

    if(a < b) {
        i++;
    } else if(a > b) {
        j++;
    }
}

3.0.2 N Sum Family Comparison

3.0.2.1 Two Sum Family (LeetCode 1, 167, 653)

Problem Input/Constraints Return Preferred Approach Time Space Notes
Two Sum I Unsorted array; preserve original indices Pair of indices Hash table O(n) O(n) Sorting breaks indices; hash lookup keeps order info
Two Sum II Sorted array; 1-indexed output Pair of indices Two pointers O(n) O(1) Sorted order unlocks monotonic sweep; TreeMap fallback is O(n log n)
Two Sum III Unsorted array; existence only Boolean Hash set O(n) O(n) Same complement idea, short-circuits on first match
Two Sum IV BST input Boolean DFS + HashSet (or dual iterators) O(n) O(n) or O(h) Iterator variant trades simplicity for O(h) space

Key differences and picks: Sorting status drives the strategy (hash table for unsorted, two pointers for sorted). When output is just existence, hash set with early exit wins. BST input can use dual iterators for O(h) space, but DFS + HashSet stays simplest.

3.0.2.2 Three Sum Family (LeetCode 15, 16)

Problem Input/Constraints Return Preferred Approach Time Space Notes
3Sum Unsorted array All unique triplets summing to 0 Sort + two pointers O(n^2) O(1) Duplicate skipping on outer and inner pointers is key
3Sum Closest Unsorted array Closest sum to target (value only) Sort + two pointers O(n^2) O(1) Same loop as 3Sum but tracks best distance instead of unique sets

Key differences and picks: Both require sorting to enable the inner two-pointer sweep. 3Sum needs dedup to emit unique triplets; 3Sum Closest reuses the same sweep but optimizes for distance rather than uniqueness.

3.0.2.3 Four Sum Family (LeetCode 18, 454)

Problem Input/Constraints Return Preferred Approach Time Space Notes
4Sum Unsorted array All unique quadruplets = target Sort + nested two pointers O(n^3) O(1) Fix two indices, two-pointer the rest, skip duplicates at every level
4Sum II Four arrays A,B,C,D Count of quadruples = 0 Hash map of pair sums O(n^2) O(n^2) Precompute A+B counts, probe with -(C+D)

Key differences and picks: Single-array 4Sum extends the 3Sum pattern (extra fixed index) with heavy dedup. Multi-array 4Sum II swaps to pair-sum hashing because sorting across four lc-lists is unnecessary—hashing collapses the problem to two combined arrays for O(n^2).

3.0.2.4 Scaling Patterns

  • Increasing N generally adds one outer loop and preserves two-pointer or hashing on the innermost search.
  • Sorting + pointer sweeping dominates when the input is a single array; hash-based pair-sum caching dominates multi-array counts (e.g., 4Sum II).
  • Deduping steps grow in importance as N grows to avoid exponential blow-up in output size.

3.0.3 Greedy Array Patterns

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. In array problems, greedy strategies often involve:

  1. Making the best immediate choice based on current information
  2. Never reconsidering previous decisions
  3. Proving correctness through exchange arguments or contradiction

Common greedy array patterns include:

3.0.3.1 Interval Scheduling (Non-overlapping Intervals)

When dealing with intervals, sort by end time and greedily select non-overlapping intervals:

  • Key insight: Always pick the interval that ends earliest among remaining choices
  • Why it works: Leaving maximum room for future intervals
  • Examples: Non-overlapping Intervals, scheduling meetings

3.0.3.2 Sequential Grouping (Hand of Straights)

When grouping elements into consecutive sequences:

  • Key insight: Process smallest elements first, form groups greedily
  • Why it works: Smallest element must start a new group; build from there
  • Examples: Hand of Straights

3.0.3.3 Accumulation with Reset (Gas Station, Maximum Subarray)

When finding optimal starting points or subarrays:

  • Key insight: Track running sum; reset when it becomes negative/invalid
  • Why it works: Negative prefix can only hurt future solutions
  • Examples: Gas Station, Maximum Subarray

3.0.3.4 Capture All Gains (Stock Trading)

When maximizing profit from transactions:

3.0.3.5 Urgency-Based Processing (Eliminate Maximum Monsters)

When deadlines or time constraints matter:

  • Key insight: Process most urgent items first (earliest deadline, fastest arrival)
  • Why it works: Delays compound; handle urgent cases before they expire
  • Examples: Eliminate Maximum Monsters, Max Gain

When to Use Greedy:

  • Problem exhibits optimal substructure (optimal solution contains optimal sub-solutions)
  • Greedy choice property holds (local optimum leads to global optimum)
  • Often involves sorting as preprocessing step
  • Common in scheduling, interval, and optimization problems

When NOT to Use Greedy:

  • Need to explore multiple paths (use Dynamic Programming or Backtracking)
  • Local optimum does not guarantee global optimum
  • Must prove correctness rigorously (greedy solutions are easy to implement but hard to verify)