DSA Series: Array (Blind 75, Java)

Overview

• Pattern cheat-sheet
• 1. Two Sum
• 2. Best Time to Buy and Sell Stock
• 3. Contains Duplicate
• 4. Product of Array Except Self
• 5. Maximum Subarray
• 6. Maximum Product Subarray
• 7. Find Minimum in Rotated Sorted Array
• 8. Search in Rotated Sorted Array
• 9. 3Sum
• 10. Container With Most Water

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

All Java solutions in this file were compiled with javac and checked with assertions (examples, edge cases, and randomized comparison against brute force).

Pattern cheat-sheet

1. Two Sum

(Easy · LeetCode #1)

Problem statement Given an integer array nums and an integer target, return the indices of the two numbers that add up to target. Exactly one solution exists; you may not use the same element twice.

• nums = [2,7,11,15], target = 9 -> [0,1]
• nums = [3,2,4], target = 6 -> [1,2]
• Constraints: 2 <= n <= 1e4, -1e9 <= nums[i], target <= 1e9.

How the interviewer asks / follow-ups

• Disguised: "Given a list of transaction amounts for a day and a fraud-rule threshold, find two transactions whose amounts add up exactly to the threshold" or "match a refund with the original charge so that they net to a given value".
• Follow-ups: What if the array is sorted? (two pointers, O(1) space.) What if it is a stream of transactions and you must flag on arrival? (the HashMap approach is already online.) What if there are many pairs - return all, or count them? (map of value -> count; careful with x + x = target.) What if the data does not fit in memory? (external sort / partition by hash of value and complement so that matching values land in the same bucket.) Overflow: values up to 1e9, so a + b can overflow int; use target - a (safe within range here) or long. Concurrency: use ConcurrentHashMap for multi-threaded ingestion, but check-then-put is not atomic, so use compute/locking.
• Evaluating: whether you jump from O(n^2) to O(n) with a space trade-off, handling the "same element twice" case, and clean communication.

Approach 1: Brute force Check all pairs (i, j) with i < j. Time O(n^2), space O(1).

Approach 2: Hash map (one pass)

• Intuition: for each a[i] we only need to know "have I already seen target - a[i]?". A HashMap answers that in O(1). Insert the current element after checking, so an element can never pair with itself, and duplicates like [3,3] still work (the first 3 is stored before the second is checked).
• Dry run [2,7,11,15], target 9: i=0 (2): need 7, map empty -> store {2:0}. i=1 (7): need 2, found at 0 -> return [0,1].

Java code

import java.util.*;

class TwoSum {
    // Brute force: O(n^2) time, O(1) space
    static int[] twoSumBrute(int[] a, int t) {
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] + a[j] == t) return new int[]{i, j};
        return new int[0];
    }

    // Optimal: one-pass hash map
    static int[] twoSum(int[] a, int t) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int i = 0; i < a.length; i++) {
            Integer j = seen.get(t - a[i]);           // complement seen earlier?
            if (j != null) return new int[]{j, i};
            seen.put(a[i], i);                         // store AFTER the check
        }
        return new int[0];                             // problem guarantees an answer
    }
}

Complexity

• Brute force: Time O(n^2) (all pairs), Space O(1).
• Hash map: Time O(n) average (one pass, O(1) expected lookups), Space O(n) (map).
• Sorted variant: two pointers, Time O(n), Space O(1).

Edge cases / pitfalls

• Same element twice ([3], target 6 must not match); duplicates ([3,3]); negatives and zero ([0,4,0], target 0).
• Put into the map after the lookup. Return indices, not values (so sorting loses indices unless you keep them).
• HashMap worst case O(n) per op under adversarial collisions (Java 8+ treeifies buckets to O(log n)).

Pattern & related problems Complement lookup with a hash map. Related: Two Sum II (sorted, two pointers), 3Sum, 4Sum, Subarray Sum Equals K (prefix sum + map), Two Sum IV (BST), Pairs with a given difference.

2. Best Time to Buy and Sell Stock

(Easy · LeetCode #121)

Problem statement prices[i] is the price on day i. Choose one day to buy and a later day to sell to maximize profit; return 0 if no profit is possible.

• [7,1,5,3,6,4] -> 5 (buy at 1, sell at 6)
• [7,6,4,3,1] -> 0
• Constraints: 1 <= n <= 1e5, 0 <= prices[i] <= 1e4.

How the interviewer asks / follow-ups

• Disguised: "Given an intraday price series of a currency pair (or a merchant's daily FX rate), what is the maximum gain from one conversion followed by a reverse conversion?" or "max spread between an earlier and a later settlement value".
• Follow-ups: unlimited transactions (#122: sum of all positive deltas); at most 2 transactions (#123: DP with 4 states); at most k (#188); with cooldown (#309); with a transaction fee (#714). Return the buy/sell days too. Streaming prices (the one-pass algorithm is already online with O(1) state).
• Evaluating: whether you see that the sell day only needs the minimum so far, i.e. you reduce O(n^2) to a single pass, and handle the "no profit -> 0" case.

Approach 1: Brute force For every pair i < j compute prices[j] - prices[i]. Time O(n^2), space O(1).

Approach 2: One pass with running minimum

• Intuition: if you sell on day j, the best buy is the cheapest price on days before j. So keep minPrice as you scan and update best = max(best, price - minPrice).
• Dry run [7,1,5,3,6,4]: min=7,best=0 -> price 1: min=1 -> 5: best=4 -> 3: best stays 4 -> 6: best=5 -> 4: best 5. Answer 5.

Java code

class Stock {
    // Brute force: O(n^2) time, O(1) space
    static int maxProfitBrute(int[] p) {
        int best = 0;
        for (int i = 0; i < p.length; i++)
            for (int j = i + 1; j < p.length; j++)
                best = Math.max(best, p[j] - p[i]);
        return best;
    }

    // Optimal: one pass
    static int maxProfit(int[] p) {
        int minPrice = Integer.MAX_VALUE, best = 0;
        for (int x : p) {
            if (x < minPrice) minPrice = x;          // new cheapest buy candidate
            else best = Math.max(best, x - minPrice); // sell today at x
        }
        return best;
    }
}

Complexity

• Brute force: Time O(n^2), Space O(1).
• One pass: Time O(n) (each element visited once), Space O(1).

Edge cases / pitfalls

• Strictly decreasing prices -> 0 (never return a negative). Single element -> 0. Equal prices -> 0.
• Do not take global max minus global min (the max may come before the min).
• Integer.MAX_VALUE as initial min is safe because we only subtract after a smaller value replaced it.

Pattern & related problems Running min/max (one-pass greedy / simple DP). Related: #122, #123, #188, #309, #714, Maximum Subarray (differences of prices reduce this to Kadane).

3. Contains Duplicate

(Easy · LeetCode #217)

Problem statement Return true if any value appears at least twice in nums, else false.

• [1,2,3,1] -> true
• [1,2,3,4] -> false
• Constraints: 1 <= n <= 1e5, -1e9 <= nums[i] <= 1e9.

How the interviewer asks / follow-ups

• Disguised: "Given a batch of transaction IDs / idempotency keys, detect whether any ID was submitted twice (duplicate payment)."
• Follow-ups: O(1) extra space? (sort in place, O(n log n).) Duplicates within distance k (#219, sliding window HashSet)? Values within a difference t and index distance k (#220, TreeSet/bucketing)? Stream of unbounded size (Bloom filter: false positives possible, no false negatives; confirm with DB lookup)? Distributed dedup (partition by hash of ID, then check per partition; or a unique constraint / SETNX in Redis with TTL).
• Evaluating: trade-off articulation between time and space, and awareness of production idempotency.

Approach 1: Brute force Compare every pair. Time O(n^2), space O(1).

Approach 2: Sorting After sorting, duplicates are adjacent. Time O(n log n), space O(1) extra if sorting in place (we clone here to avoid mutating the input; O(n)).

Approach 3: HashSet Set.add returns false if the element already exists; the first failure means a duplicate. This stops early. Dry run [1,2,3,1]: add 1,2,3 ok, add 1 -> false -> return true.

Java code

import java.util.*;

class ContainsDuplicate {
    // Brute force: O(n^2) time, O(1) space
    static boolean containsDuplicateBrute(int[] a) {
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] == a[j]) return true;
        return false;
    }

    // Sorting: O(n log n) time (clone costs O(n) space; sort in place for O(1))
    static boolean containsDuplicateSort(int[] a) {
        int[] c = a.clone();
        Arrays.sort(c);
        for (int i = 1; i < c.length; i++)
            if (c[i] == c[i - 1]) return true;
        return false;
    }

    // Optimal for time: HashSet, O(n) average time, O(n) space
    static boolean containsDuplicate(int[] a) {
        Set<Integer> s = new HashSet<>();
        for (int x : a)
            if (!s.add(x)) return true; // add() returns false if already present
        return false;
    }
}

Complexity

• Brute force: Time O(n^2), Space O(1).
• Sorting: Time O(n log n) (dual-pivot quicksort on primitives; worst case is rarely hit), Space O(1) in place.
• HashSet: Time O(n) average, Space O(n).

Edge cases / pitfalls

• Single element -> false. Empty input (not in constraints, but say it) -> false.
• Arrays.sort(int[]) mutates the input - say so or clone.
• Boxing overhead of HashSet<Integer>; for huge inputs mention primitive-specialized sets.

Pattern & related problems Membership check with a hash set. Related: #219 Contains Duplicate II, #220 III, Valid Anagram, Find the Duplicate Number (#287, Floyd), First Missing Positive.

4. Product of Array Except Self

(Medium · LeetCode #238)

Problem statement Return answer where answer[i] is the product of all elements of nums except nums[i]. Must run in O(n) and without division. The product of any prefix/suffix fits in a 32-bit integer.

• [1,2,3,4] -> [24,12,8,6]
• [-1,1,0,-3,3] -> [0,0,9,0,0]
• Constraints: 2 <= n <= 1e5, -30 <= nums[i] <= 30.

How the interviewer asks / follow-ups

• Disguised: "For each merchant's metric, compute the combined risk multiplier of all other merchants" or "leave-one-out aggregate" (e.g. compound fee factor of all other legs in a settlement chain).
• Follow-ups: Why not division? (zeros; modular/field arithmetic where inverse may not exist; precision for floats.) How to do it with division and handle zeros (count zeros: 0 zeros -> total/a[i]; 1 zero -> only the zero's index gets the product of others; >=2 zeros -> all 0). O(1) extra space (output array excluded). Overflow with big values -> long/BigInteger/modulus. Generalize to any associative operation (prefix/suffix trick works for gcd, min, etc.).
• Evaluating: prefix/suffix thinking and the space optimization.

Approach 1: Brute force For each i, multiply all j != i. Time O(n^2), space O(1) beyond output.

Approach 2: Prefix and suffix arrays left[i] = product of everything left of i, right[i] = product of everything right of i; answer[i] = left[i] * right[i]. Time O(n), space O(n) extra.

Approach 3: Prefix in output, suffix in a running variable (final)

• Intuition: use the output array to hold prefix products, then sweep right-to-left keeping a single running suffix and multiply it in.
• Dry run [1,2,3,4]: prefix pass -> [1,1,2,6]. Backward: i=3: res=61=6, suffix=4; i=2: res=24=8, suffix=12; i=1: res=112=12, suffix=24; i=0: res=124=24. Result [24,12,8,6].

Java code

class ProductExceptSelf {
    // Brute force: O(n^2) time, O(1) extra space
    static int[] productBrute(int[] a) {
        int n = a.length;
        int[] r = new int[n];
        for (int i = 0; i < n; i++) {
            int p = 1;
            for (int j = 0; j < n; j++) if (j != i) p *= a[j];
            r[i] = p;
        }
        return r;
    }

    // Optimal: O(n) time, O(1) extra space (output array not counted)
    static int[] productExceptSelf(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++)
            res[i] = res[i - 1] * a[i - 1];   // res[i] = product of a[0..i-1]
        int suffix = 1;                        // product of a[i+1..n-1]
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= suffix;
            suffix *= a[i];
        }
        return res;
    }
}

Complexity

• Brute force: Time O(n^2), Space O(1) extra.
• Prefix/suffix arrays: Time O(n), Space O(n) extra.
• Final: Time O(n) (two linear passes), Space O(1) extra (excluding the output).

Edge cases / pitfalls

• Zeros: one zero (only its own slot is non-zero), two or more zeros (all zero) - the prefix/suffix method handles this naturally, no special-casing.
• Do not use division unless you handle zeros. n >= 2 so res[0] exists; for n = 1 the answer would be [1] (empty product) - clarify.
• Overflow is excluded by constraints; in real systems use long or modular arithmetic.

Pattern & related problems Prefix/suffix accumulation. Related: Trapping Rain Water (prefix max/suffix max), Maximum Product Subarray, Subarray Sum Equals K, Range Sum Query, Candy.

5. Maximum Subarray

(Medium · LeetCode #53)

Problem statement Find the contiguous non-empty subarray with the largest sum and return that sum.

• [-2,1,-3,4,-1,2,1,-5,4] -> 6 (subarray [4,-1,2,1])
• [1] -> 1; [5,4,-1,7,8] -> 23
• Constraints: 1 <= n <= 1e5, -1e4 <= nums[i] <= 1e4.

How the interviewer asks / follow-ups

• Disguised: "Given hourly net cash-flow (credits minus debits) for an account, find the contiguous window with the highest net inflow" or "worst drawdown window" (min subarray, negate).
• Follow-ups: return the start/end indices; circular array (#918: max(Kadane, total - min subarray)); the divide-and-conquer solution (O(n log n), parallelizable / good for distributed aggregation: each segment keeps total, best prefix, best suffix, best); at most one deletion (#1186); streaming data (Kadane is online, O(1) state); max subarray of size at least k.
• Evaluating: recognizing the DP recurrence, handling all-negative input.

Approach 1: Brute force Try every start i and extend j, keeping a running sum. Time O(n^2), space O(1). (Computing each sum from scratch is O(n^3) - avoid.)

Approach 2: Kadane's algorithm

• Intuition: let cur = best sum of a subarray ending at index i. Either extend the previous best (cur + a[i]) or start fresh at a[i] - restart if the previous sum is negative, since it only hurts. The answer is the max of cur over all i.
• Dry run [-2,1,-3,4,-1,2,1,-5,4]: cur: -2, 1, -2, 4, 3, 5, 6, 1, 5; best = 6.

Java code

class MaxSubarray {
    // Brute force: O(n^2) time, O(1) space
    static int maxSubArrayBrute(int[] a) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            int s = 0;
            for (int j = i; j < a.length; j++) {
                s += a[j];
                best = Math.max(best, s);
            }
        }
        return best;
    }

    // Kadane: O(n) time, O(1) space
    static int maxSubArray(int[] a) {
        int cur = a[0], best = a[0];            // init with a[0], NOT 0 (handles all-negative)
        for (int i = 1; i < a.length; i++) {
            cur = Math.max(a[i], cur + a[i]);   // extend or restart
            best = Math.max(best, cur);
        }
        return best;
    }
}

Complexity

• Brute force: Time O(n^2), Space O(1).
• Kadane: Time O(n) (single pass), Space O(1).
• Divide and conquer (mention): Time O(n log n), Space O(log n) recursion.

Edge cases / pitfalls

• All negatives: answer is the largest (least negative) element, so do not initialize best = 0.
• Single element. Large sums: 1e5 * 1e4 = 1e9 fits in int, but use long if constraints grow.
• Empty subarray allowed? Clarify; if yes, initialize with 0.

Pattern & related problems 1D DP / Kadane. Related: #152 Max Product Subarray, #918 Max Sum Circular Subarray, Best Time to Buy and Sell Stock, #325 Maximum Size Subarray Sum Equals k, Longest Turbulent Subarray.

6. Maximum Product Subarray

(Medium · LeetCode #152)

Problem statement Find the contiguous non-empty subarray with the largest product and return it. The answer fits in a 32-bit integer.

• [2,3,-2,4] -> 6
• [-2,0,-1] -> 0
• [-2,3,-4] -> 24
• Constraints: 1 <= n <= 2*10^4, -10 <= nums[i] <= 10.

How the interviewer asks / follow-ups

• Disguised: "Given a sequence of compounding multipliers (fee factors, FX conversions, which can be negative as reversals or zero as waivers), find the contiguous stretch with the largest compound factor."
• Follow-ups: why track the minimum too? (two negatives make a positive); return the subarray bounds; what if all values are doubles in (0,2) - use logs to turn it into Kadane; overflow handling with long/BigInteger; prefix/suffix-product alternative (answer is the max over prefix products and suffix products, resetting at zeros).
• Evaluating: seeing why Kadane breaks (a very negative running product can become the max after multiplying by a negative) and the zero-reset behaviour.

Approach 1: Brute force All start/end pairs with a running product. Time O(n^2), space O(1).

Approach 2: Track max and min ending here

• Intuition: at index i, the largest product ending here is one of a[i], max*a[i], min*a[i]. A negative a[i] swaps the roles of max and min, so swap them first. A zero resets both to 0 automatically via Math.max(x, max*x) = max(0, 0).
• Dry run [-2,3,-4]: start max=min=best=-2. x=3: max=max(3,-6)=3, min=min(3,-6)=-6, best=3. x=-4: swap -> max=-6,min=3; max=max(-4,24)=24, min=min(-4,-12)=-12; best=24.

Java code

class MaxProductSubarray {
    // Brute force: O(n^2) time, O(1) space
    static int maxProductBrute(int[] a) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            int p = 1;
            for (int j = i; j < a.length; j++) {
                p *= a[j];
                best = Math.max(best, p);
            }
        }
        return best;
    }

    // Optimal: O(n) time, O(1) space
    static int maxProduct(int[] a) {
        int max = a[0], min = a[0], best = a[0];  // max/min product of a subarray ending at i
        for (int i = 1; i < a.length; i++) {
            int x = a[i];
            if (x < 0) { int t = max; max = min; min = t; } // negative flips order
            max = Math.max(x, max * x);   // extend or restart
            min = Math.min(x, min * x);
            best = Math.max(best, max);
        }
        return best;
    }
}

Complexity

• Brute force: Time O(n^2), Space O(1).
• Optimal: Time O(n) (one pass), Space O(1).

Edge cases / pitfalls

• Single negative element ([-2] -> -2). A zero splits the array ([-2,0,-1] -> 0, not 2).
• Initialize with a[0], not 1 or 0. Intermediate products can overflow int for adversarial inputs beyond the constraints; the stated guarantee covers only the final answer, so mention long.
• Updating max before using it for min without a temp variable is a classic bug - the swap approach above avoids it.

Pattern & related problems Kadane variant with two states. Related: #53 Maximum Subarray, #238 Product Except Self, #628 Max Product of Three Numbers, #713 Subarray Product Less Than K.

7. Find Minimum in Rotated Sorted Array

(Medium · LeetCode #153)

Problem statement A sorted array of unique elements was rotated between 1 and n times. Return its minimum in O(log n).

• [3,4,5,1,2] -> 1
• [4,5,6,7,0,1,2] -> 0
• [11,13,15,17] -> 11 (rotated n times = unchanged)
• Constraints: 1 <= n <= 5000, unique values.

How the interviewer asks / follow-ups

• Disguised: "A circular log buffer of timestamped transactions has wrapped around; find the oldest entry (the write pointer) without scanning" or "a sorted shard list was rotated during rebalancing".
• Follow-ups: duplicates allowed (#154: when a[mid] == a[hi] do hi--; worst case O(n)); also return the rotation count (= index of the min); then use it to run a normal binary search.
• Evaluating: correct binary-search invariants (lo < hi, hi = mid), no off-by-one infinite loops.

Approach 1: Brute force Linear scan for the min. Time O(n), space O(1). Correct but ignores the sorted structure.

Approach 2: Binary search against the right end

• Intuition: compare a[mid] with a[hi]. If a[mid] > a[hi], the drop (pivot) is to the right of mid, so the min is in (mid, hi]: lo = mid + 1. Otherwise the right part [mid, hi] is sorted so the min is at mid or to its left: hi = mid (keep mid, it may be the answer).
• Dry run [4,5,6,7,0,1,2]: lo=0,hi=6,mid=3 (7>2) -> lo=4. mid=5 (1<=2) -> hi=5. mid=4 (0<=1) -> hi=4. lo==hi -> 0.

Java code

class FindMinRotated {
    // Brute force: O(n)
    static int findMinBrute(int[] a) {
        int m = a[0];
        for (int x : a) m = Math.min(m, x);
        return m;
    }

    // Binary search: O(log n) time, O(1) space (unique elements)
    static int findMin(int[] a) {
        int lo = 0, hi = a.length - 1;
        while (lo < hi) {                       // stops when one candidate remains
            int mid = lo + (hi - lo) / 2;       // avoids int overflow
            if (a[mid] > a[hi]) lo = mid + 1;   // min is strictly right of mid
            else hi = mid;                      // mid itself may be the min
        }
        return a[lo];
    }
}

Complexity

• Brute force: Time O(n), Space O(1).
• Binary search: Time O(log n) (search space halves each step), Space O(1).

Edge cases / pitfalls

• Not rotated ([11,13,15,17]): a[mid] <= a[hi] always, so hi shrinks to 0 -> correct.
• Size 1 and size 2 ([2,1]: mid=0, 2>1 -> lo=1 -> 1).
• Compare with a[hi], not a[lo] - comparing with a[lo] fails on the non-rotated case without extra checks.
• With duplicates the algorithm degrades to O(n) worst case (hi-- when equal).

Pattern & related problems Binary search on a "predicate" (is mid in the right/left sorted part). Related: #33 Search in Rotated Sorted Array, #81 (with duplicates), #154, #162 Find Peak Element, #34 First/Last Position.

8. Search in Rotated Sorted Array

(Medium · LeetCode #33)

Problem statement A sorted array of distinct values was rotated at an unknown pivot. Given target, return its index or -1 in O(log n).

• nums = [4,5,6,7,0,1,2], target = 0 -> 4
• nums = [4,5,6,7,0,1,2], target = 3 -> -1
• nums = [1], target = 0 -> -1
• Constraints: 1 <= n <= 5000, distinct values.

How the interviewer asks / follow-ups

• Disguised: "Look up a transaction ID in a wrapped circular buffer of sorted IDs" or "search in a sorted ledger that was rotated after a rollover".
• Follow-ups: duplicates (#81: if a[lo]==a[mid]==a[hi] shrink both ends; worst case O(n)); two-pass alternative (find pivot, then binary-search the correct half); return all occurrences; why it is still O(log n).
• Evaluating: reasoning "at least one half is always sorted", precise boundary conditions.

Approach 1: Brute force Linear scan. Time O(n), space O(1).

Approach 2: Single binary search

• Intuition: at any mid, either [lo..mid] or [mid..hi] is sorted. Identify the sorted half (a[lo] <= a[mid] means left is sorted). Check whether target lies in that sorted half's range; if yes go there, else go to the other half.
• Dry run [4,5,6,7,0,1,2], target 0: lo=0,hi=6,mid=3 (7). Left [4..7] sorted; 0 not in [4,7) -> lo=4. mid=5 (1): left [0,1] sorted (a[4]=0<=1), is 0 in [0,1)? yes -> hi=4. mid=4 -> found, return 4.

Java code

class SearchRotated {
    // Brute force: O(n)
    static int searchBrute(int[] a, int t) {
        for (int i = 0; i < a.length; i++) if (a[i] == t) return i;
        return -1;
    }

    // Binary search: O(log n) time, O(1) space (distinct elements)
    static int search(int[] a, int t) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == t) return mid;
            if (a[lo] <= a[mid]) {                    // left half [lo..mid] is sorted
                if (a[lo] <= t && t < a[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {                                  // right half [mid..hi] is sorted
                if (a[mid] < t && t <= a[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}

Complexity

• Brute force: Time O(n), Space O(1).
• Binary search: Time O(log n) (halve the range each iteration), Space O(1).

Edge cases / pitfalls

• Use <= in a[lo] <= a[mid] - with two elements lo == mid, so the left "half" is a single sorted element.
• Range checks must be inclusive on the correct side (t < a[mid] for left, t <= a[hi] for right) since mid is already ruled out.
• Target absent, size-1 array, non-rotated array ([3,1] search 1 -> 1 is a rotated size-2).
• Duplicates break the "which half is sorted" test - mention #81.

Pattern & related problems Modified binary search ("one half is always sorted"). Related: #153, #81, #1095 Mountain Array, #74 Search a 2D Matrix, #34.

9. 3Sum

(Medium · LeetCode #15)

Problem statement Return all unique triplets [a,b,c] from nums with a + b + c == 0 (distinct indices, no duplicate triplets; order of output does not matter).

• [-1,0,1,2,-1,-4] -> [[-1,-1,2],[-1,0,1]]
• [0,1,1] -> []; [0,0,0] -> [[0,0,0]]
• Constraints: 3 <= n <= 3000, -1e5 <= nums[i] <= 1e5.

How the interviewer asks / follow-ups

• Disguised: "Find all sets of three ledger entries (debits and credits) that net to zero for reconciliation" or "three transactions that sum to a threshold".
• Follow-ups: 3Sum Closest (#16); 4Sum / kSum (recursion reducing to 2Sum); a hash-set variant (no sorting, but dedupe is harder); count instead of list; do not sort the caller's array; very large n - what bounds exist (O(n^2) is essentially optimal for general 3SUM); streaming (not feasible in one pass).
• Evaluating: sort + two pointers, and the duplicate-skipping logic (the usual place to fail).

Approach 1: Brute force Three nested loops, deduplicate by sorting each triplet into a set. Time O(n^3), space O(n) for the set (plus output).

Approach 2: Sort + two pointers

• Intuition: sort. Fix a[i] as the smallest element; the remaining problem is two-sum-to -a[i] on a sorted suffix, solved with l, r pointers: sum too small -> l++, too big -> r--. Skip equal values for i, l, r to avoid duplicate triplets. If a[i] > 0 stop: all later values are positive.
• Dry run [-4,-1,-1,0,1,2]: i=0 (-4): l=1,r=5: sum -3 -> l++ ... never 0. i=1 (-1): l=2 (-1), r=5 (2): sum 0 -> add [-1,-1,2]; l=3,r=4: -1+0+1=0 -> add [-1,0,1]. i=2 is a duplicate of -1 -> skip. i=3 (0): >0? no, l=4,r=5: 0+1+2=3 -> r--, l==r stop. Result [[-1,-1,2],[-1,0,1]].

Java code

import java.util.*;

class ThreeSum {
    // Brute force: O(n^3) time
    static List<List<Integer>> threeSumBrute(int[] a) {
        Set<List<Integer>> set = new HashSet<>();
        int n = a.length;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                for (int k = j + 1; k < n; k++)
                    if (a[i] + a[j] + a[k] == 0) {
                        List<Integer> t = new ArrayList<>(Arrays.asList(a[i], a[j], a[k]));
                        Collections.sort(t);
                        set.add(t);
                    }
        return new ArrayList<>(set);
    }

    // Optimal: O(n^2) time, O(1) extra (ignoring sort internals and output)
    static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int[] a = nums.clone();                        // do not mutate caller's array
        Arrays.sort(a);
        int n = a.length;
        for (int i = 0; i < n - 2; i++) {
            if (a[i] > 0) break;                       // smallest is positive -> no zero-sum
            if (i > 0 && a[i] == a[i - 1]) continue;   // skip duplicate anchors
            int l = i + 1, r = n - 1;
            while (l < r) {
                int s = a[i] + a[l] + a[r];
                if (s < 0) l++;
                else if (s > 0) r--;
                else {
                    res.add(Arrays.asList(a[i], a[l], a[r]));
                    l++; r--;
                    while (l < r && a[l] == a[l - 1]) l++;   // skip duplicate lefts
                    while (l < r && a[r] == a[r + 1]) r--;   // skip duplicate rights
                }
            }
        }
        return res;
    }
}

Complexity

• Brute force: Time O(n^3), Space O(T) for the dedupe set, T = number of distinct triplets.
• Sort + two pointers: Time O(n^2) (O(n log n) sort + n two-pointer sweeps of O(n)), Space O(1) extra besides output and sort.

Edge cases / pitfalls

• Duplicate skipping: for i compare with the previous element (i > 0), for l/r skip after recording a match. Comparing a[i] == a[i+1] instead would wrongly drop [-1,-1,2].
• [0,0,0] and [0,0,0,0] -> exactly one triplet. All positives/negatives -> empty. Fewer than 3 elements -> empty.
• Sum overflow is not an issue with given bounds; with int extremes use long.

Pattern & related problems Sort + two pointers (reduce kSum to 2Sum). Related: #1 Two Sum, #167 Two Sum II, #16 3Sum Closest, #18 4Sum, #259 3Sum Smaller, #11 Container With Most Water.

10. Container With Most Water

(Medium · LeetCode #11)

Problem statement height[i] is a vertical line at x = i. Pick two lines that, with the x-axis, hold the most water; return the max area (min(h[i], h[j]) * (j - i)). Lines cannot be slanted.

• [1,8,6,2,5,4,8,3,7] -> 49
• [1,1] -> 1
• Constraints: 2 <= n <= 1e5, 0 <= height[i] <= 1e4.

How the interviewer asks / follow-ups

• Disguised: "Given capacity levels of servers/pipes at positions, choose two to maximize throughput = bottleneck capacity x distance" or "pick two time-slots with limits to maximize value".
• Follow-ups: prove why moving the shorter pointer is safe; Trapping Rain Water (#42, different problem); 3D version; what if lines are not vertical or can't be skipped; return the indices.
• Evaluating: greedy proof and clean two-pointer loop.

Approach 1: Brute force Check every pair. Time O(n^2), space O(1).

Approach 2: Two pointers from the ends

• Intuition: start with the widest container. Area is limited by the shorter line. Moving the taller pointer inward can only reduce width and cannot increase the min height (still capped by the shorter line), so area cannot improve. Hence move the shorter pointer, hoping for a taller line. Every discarded pair is provably no better than one already considered.
• Dry run [1,8,6,2,5,4,8,3,7]: l=0,r=8: min(1,7)*8=8, move l. l=1,r=8: min(8,7)*7=49 (best), move r (7<8). l=1,r=7: min(8,3)*6=18 ... best stays 49.

Java code

class ContainerWithMostWater {
    // Brute force: O(n^2) time, O(1) space
    static int maxAreaBrute(int[] h) {
        int best = 0;
        for (int i = 0; i < h.length; i++)
            for (int j = i + 1; j < h.length; j++)
                best = Math.max(best, Math.min(h[i], h[j]) * (j - i));
        return best;
    }

    // Optimal: O(n) time, O(1) space
    static int maxArea(int[] h) {
        int l = 0, r = h.length - 1, best = 0;
        while (l < r) {
            best = Math.max(best, Math.min(h[l], h[r]) * (r - l));
            if (h[l] < h[r]) l++;   // move the shorter side
            else r--;
        }
        return best;
    }
}

Complexity

• Brute force: Time O(n^2), Space O(1).
• Two pointers: Time O(n) (pointers move inward, at most n-1 steps), Space O(1).
• Max area 1e4 * 1e5 = 1e9 fits in int; use long if the limits grow.

Edge cases / pitfalls

• Two elements; zeros in heights (area 0); all equal heights (widest pair wins).
• Be ready to justify the greedy: "any container using the shorter line with a pointer inside the current range has smaller width and no greater height".
• Container thickness of lines is ignored; water level is the min of the two, not the average.

Pattern & related problems Two pointers with a monotone argument. Related: #42 Trapping Rain Water, #167 Two Sum II, #15 3Sum, #84 Largest Rectangle in Histogram, #881 Boats to Save People.