Array Algorithms: Understand the Thinking Behind the Code

1.1 Understand the actual task

Given an array and a target, return the indices of two different elements whose values add up to the target. We need indices, not merely the values. The input is not necessarily sorted, and there may be negative values or repeated values.

1.2 Derive it from brute force

The direct approach enumerates every pair (i, j) where i < j. For each pair, calculate nums[i] + nums[j]. In the worst case, the number of pairs is:

The expensive part is repeatedly searching all possible partners. But for a fixed value x, there is only one value that can pair with it:

That changes the question from a pair search into a lookup question: “Have I already seen this partner?” A hash map is designed for fast membership lookup.

1.3 Visual trace: remember the past

1.4 The algorithm, precisely

1. Start with an empty map seen, storing value → index.
2. At index i, calculate need = target - nums[i].
3. If need is in the map, the earlier index and current index form the answer.
4. If it is absent, store the current value and index, then continue.

1.5 Why check before inserting?

The map must represent only elements from indices before i. This guarantees the pair uses two distinct positions. Consider [3, 3] with target 6: the first 3 is stored; the second 3 finds it. If you inserted first and then searched without carefully excluding the current index, a single element could match itself.

1.6 Correctness argument

• Safety: When a complement is found, it came from an earlier index, so the returned indices are distinct and their values sum to target.
• Completeness: If a valid pair exists at indices p < q, then when the loop reaches q, the value at p has already been stored. The required complement lookup succeeds.

1.7 Java implementation

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];

        if (seen.containsKey(need)) {
            return new int[] { seen.get(need), i };
        }

        seen.put(nums[i], i);
    }
    return new int[0];
}

1.8 Edge cases to reason through

• [3, 3], target = 6 — repeated values at different indices.
• [3, 2, 4], target = 6 — answer uses 2 and 4, not the first element.
• [-3, 4, 3, 90], target = 0 — negative values work without special handling.
• One-element array — no valid pair.

2.1 Understand the constraints

You choose one buy day and one later sell day. The order matters: buying must happen before selling. The objective is to maximize prices[sell] - prices[buy]. If every later price is lower, the best profit is zero because doing no transaction is allowed.

2.2 Brute force → useful observation

Brute force tries every pair of days buy < sell, giving O(n²) time. Notice that for a fixed sell day, we do not need every earlier price. We only need the smallest earlier price. Every other earlier buying price gives an equal or smaller profit for this sell day.

2.3 Visual model

2.4 Why a running minimum is sufficient

At day i, all legal buy days are in the prefix [0, i-1]. Among them, the cheapest day is always at least as good as any more expensive day for selling today. Therefore, preserve only that minimum. The algorithm is not guessing the final buy day in advance; it evaluates the best sale possible at every day.

2.5 Invariant and correctness

After processing day i:

• minPrice equals the minimum price among days 0 through i.
• bestProfit equals the maximum legal profit from all buy/sell pairs entirely within days 0 through i, or zero if no profitable pair exists.

For each new day, any newly possible optimal transaction must sell today. The best such transaction buys at the minimum previous price. Comparing that profit with the previous best therefore preserves the invariant.

2.6 Java

int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int bestProfit = 0;

    for (int price : prices) {
        minPrice = Math.min(minPrice, price);
        bestProfit = Math.max(bestProfit, price - minPrice);
    }
    return bestProfit;
}

2.7 Complexity and variations

O(n) time and O(1) extra space. This exact one-transaction state does not directly solve “buy/sell multiple times”, “at most k transactions”, or “cooldown” variants. Those add transaction state or dynamic programming.

3.1 What information does the answer need?

The question asks whether any value occurs at least twice. It does not ask for the duplicate's index, frequency, or all duplicate values. That means a set is enough: it records which values have appeared, without storing their positions or counts.

3.2 Two ways to reason

3.3 Visual trace

3.4 Why Set.add is useful

In Java, HashSet.add(value) returns true if the set changed (the value was new), and false if it was already present. This lets one operation perform the membership test and insertion.

boolean containsDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();

    for (int value : nums) {
        if (!seen.add(value)) {
            return true;
        }
    }
    return false;
}

3.5 Correctness and edge cases

When an insertion fails, the same value was inserted earlier, so at least two occurrences exist. Conversely, if a duplicate exists, its later occurrence will fail to insert. Empty and one-element arrays return false. Negative numbers and zero need no special treatment.

Complexity: Expected O(n) time and O(n) space. Hash operations are expected constant time, not a mathematical worst-case guarantee for every hash table implementation.

4.1 Translate the output into a formula

For each index i, the answer is the product of every element except nums[i]. Split those elements into two non-overlapping groups: everything left of i and everything right of i.

4.2 Why division is the tempting but wrong shortcut

You might calculate the total product and divide by nums[i]. But the problem prohibits division, and division fails when an element is zero. Prefix/suffix products solve the actual requirement directly and naturally handle zeroes.

4.3 Visualize the two directions

4.4 Build the optimized algorithm in two passes

1. Left-to-right pass: Before visiting index i, prefix is the product of all values strictly before i. Write it to answer[i], then include nums[i] in prefix for the next index.
2. Right-to-left pass: Before visiting i, suffix is the product of all values strictly after i. Multiply it into answer[i], then include nums[i] in suffix.

4.5 Java implementation

int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];

    int prefix = 1;
    for (int i = 0; i < n; i++) {
        answer[i] = prefix;
        prefix *= nums[i];
    }

    int suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] *= suffix;
        suffix *= nums[i];
    }
    return answer;
}

4.6 Correctness proof by meaning of variables

After the first pass, answer[i] equals the product of all elements left of i. During the reverse pass, suffix equals the product of all elements right of the current i. Multiplying these two disjoint products gives exactly every array element except i.

4.7 Complexity and zero cases

O(n) time, two linear passes. O(1) auxiliary space if the output array is not counted. For [1, 2, 0, 4], the result is [0, 0, 8, 0]; for two zeroes, every output is zero. Use the integer type guaranteed by the problem constraints.

5.1 What makes a subarray special?

A subarray is contiguous: once you choose a start and end index, every element between them is included. The task is to find the contiguous range with the largest sum. This is different from a subsequence, where gaps may be skipped.

5.2 Brute force and the repeated work

Enumerating all start/end pairs gives O(n²) ranges. If you sum each range from scratch, the total work can be O(n³). Prefix sums can bring range-sum evaluation to O(1), producing an O(n²) solution. But we can do better by exploiting a local decision.

5.3 The key question: best subarray ending here

Imagine the current position is i. Any maximum-sum subarray that ends exactly at i must be one of only two forms:

There is no third useful option. If an earlier segment has a negative total, adding it to the current value makes the sum smaller than starting fresh.

5.4 Step-by-step visualization

5.5 Why all-negative arrays matter

For [-5, -2, -8], the answer is −2, not 0. The problem requires a non-empty subarray. Initialize both current and best from the first element, not from zero. This is a classic example of initialization encoding the problem's constraints.

5.6 Java

int maxSubArray(int[] nums) {
    int current = nums[0];
    int best = nums[0];

    for (int i = 1; i < nums.length; i++) {
        current = Math.max(nums[i], current + nums[i]);
        best = Math.max(best, current);
    }
    return best;
}

5.7 Invariant and proof idea

After processing index i, current is the maximum sum of any non-empty subarray that ends exactly at i. Any such subarray either starts at i or extends a subarray ending at i−1; choosing the larger option is therefore optimal. best is the maximum of these ending-at-each-index values seen so far, so it is the global maximum subarray sum.

Complexity: O(n) time and O(1) space.

6.1 Why the Maximum Subarray recurrence breaks

For sums, a negative running sum never helps a future extension. For products, the sign changes the story: a very negative product can become a very large positive product when multiplied by another negative number. Throwing away the minimum product would lose useful information.

6.2 Define two states

• maxEnding: maximum product of a non-empty subarray that ends at the current index.
• minEnding: minimum product of a non-empty subarray that ends at the current index.

For current value x, the new subarray can be just x, or extend either previous extreme:

6.3 Visual sign reasoning

6.4 Java

int maxProduct(int[] nums) {
    int maxEnding = nums[0];
    int minEnding = nums[0];
    int answer = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];

        int fromMax = x * maxEnding;
        int fromMin = x * minEnding;

        int nextMax = Math.max(x, Math.max(fromMax, fromMin));
        int nextMin = Math.min(x, Math.min(fromMax, fromMin));

        maxEnding = nextMax;
        minEnding = nextMin;
        answer = Math.max(answer, maxEnding);
    }
    return answer;
}

6.5 Why use temporary variables?

Both new states must be computed from the previous index's states. If you overwrite maxEnding first and then calculate minEnding using that updated maximum, you mix two different time steps. Store nextMax and nextMin first, then assign both.

6.6 Correctness and complexity

Every subarray ending at i is either the single element x or an earlier subarray ending at i−1 extended by x. To find the largest or smallest resulting product, only the earlier maximum and minimum can matter because multiplication by x is monotonic when x is positive and reverses order when x is negative. Thus the two states are sufficient. O(n) time, O(1) space.

7.1 Understand what rotation preserves

A sorted array such as [0,1,2,4,5,6,7] can be rotated to [4,5,6,7,0,1,2]. The entire array is no longer sorted, but it is made of two individually sorted runs. The smallest value is the first value in the right run — the rotation pivot.

7.2 Why binary search is possible

We cannot compare the middle with a global target, but we can compare it with the rightmost value. With distinct elements:

• If nums[mid] > nums[right], mid lies in the larger left sorted run. The pivot/minimum must be strictly to its right.
• If nums[mid] <= nums[right], mid lies in the smaller right sorted run, or the interval is already sorted. The minimum is at mid or to its left.

7.3 Interactive interval narrowing

7.4 Java

int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

7.5 Why is the update different from ordinary binary search?

When the minimum may be at mid, we must keep mid by setting right = mid, not mid - 1. When mid is known to be larger than the minimum, we can safely discard it and everything left of it with left = mid + 1. The interval always contains the minimum.

Termination: The loop stops at left == right. Since the interval invariant says the minimum is inside the interval, the single remaining index must be the answer.

Complexity: O(log n) time, O(1) space. This version assumes distinct elements. Duplicates require handling ambiguous comparisons and can degrade worst-case time to O(n).

8.1 The central observation

In a rotated sorted array with distinct values, at least one of the two halves around mid is sorted. The other half may contain the rotation point. We can use the sorted half's value range to decide whether the target can be inside it.

8.2 Decision tree

1. If nums[mid] == target, return mid.
2. Check whether the left half is sorted using nums[left] <= nums[mid].
3. If left is sorted, target belongs there only if nums[left] <= target < nums[mid].
4. Otherwise, the right half is sorted. Target belongs there only if nums[mid] < target <= nums[right].
5. Discard the half that cannot contain the target.

8.3 Java

int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) return mid;

        if (nums[left] <= nums[mid]) {
            // Left half is sorted.
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted.
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

8.4 Why the inequalities look asymmetric

We already checked whether nums[mid] equals target, so mid itself is excluded from both remaining ranges. The left sorted range includes nums[left] but excludes nums[mid]. The right sorted range excludes nums[mid] but includes nums[right]. These strict/non-strict boundaries prevent retaining an index that was already checked.

8.5 Correctness invariant

If the target exists, it remains inside the active interval [left, right]. Each iteration identifies a sorted half. If the target is outside that half's inclusive value range, it cannot be there, so discarding it is safe. The interval shrinks until the target is found or no candidate remains.

Complexity: O(log n) time, O(1) space for distinct values.

9.1 Reduce a three-number problem to a two-number problem

We need three values whose sum is zero. If we fix one value a, the remaining two must sum to -a. That is a Two Sum problem on the remaining suffix. Sorting lets us solve that pair problem with two pointers rather than another hash map.

9.2 Why sorting changes everything

After sorting, values increase from left to right. For a fixed first value:

• If the sum is too small, moving the left pointer right increases or preserves the pair sum.
• If the sum is too large, moving the right pointer left decreases or preserves the pair sum.
• If the sum is zero, record the triplet and move both pointers to search for another distinct pair.

9.3 Visual example

9.4 Duplicate handling is part of the algorithm

The output asks for unique triplets, not unique index combinations. Sorting groups equal values together, which makes duplicates easy to skip:

• Skip index i when nums[i] == nums[i-1] (for i > 0), because the same fixed value was already fully explored.
• After finding a valid triplet, move both pointers and skip repeated left and right values.

9.5 Java implementation

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        if (nums[i] > 0) break;

        int left = i + 1;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                result.add(Arrays.asList(
                    nums[i], nums[left], nums[right]
                ));
                left++;
                right--;

                while (left < right &&
                       nums[left] == nums[left - 1]) left++;
                while (left < right &&
                       nums[right] == nums[right + 1]) right--;
            }
        }
    }
    return result;
}

9.6 Why can we break when nums[i] > 0?

The array is sorted. If the fixed value is positive, every value to its right is also positive. Three positive values cannot sum to zero. The same monotonic ordering that supports pointer movement supports this early termination.

9.7 Complexity

Sorting costs O(n log n). The outer loop runs O(n) times, and each two-pointer scan is O(n), so total time is O(n²). Output storage is not counted as auxiliary working space; the result can contain O(n²) triplets in the general bound.

10.1 Translate the picture into a formula

Choose two vertical lines. They form a container whose width is the distance between their indices. Water height is limited by the shorter line; water cannot rise above the shorter wall.

10.2 Why brute force is expensive

Every pair of lines is a possible container. There are O(n²) pairs. The optimized algorithm begins with the widest pair — the two endpoints — then removes one candidate boundary at a time using a proof.

10.3 The crucial elimination proof

Suppose the left wall is shorter. The current area is limited by that left height. If we keep the same left wall and move the right wall inward:

• The width becomes smaller.
• The limiting height cannot exceed the unchanged short left wall.
• Therefore, the new area cannot be larger than the current area.

So every pair that keeps this short left wall and chooses a closer right wall is already ruled out. We can safely move the left pointer. The symmetric argument applies when the right wall is shorter.

10.4 Interactive pointer visualization

10.5 Java

int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int best = 0;

    while (left < right) {
        int width = right - left;
        int limitingHeight =
            Math.min(height[left], height[right]);
        int area = width * limitingHeight;

        best = Math.max(best, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return best;
}

10.6 Correctness and complexity

At each step, the current pair is evaluated. Then the shorter boundary is moved. The elimination proof shows that no unevaluated pair using that same shorter boundary and a narrower width can improve the current area. Thus no potentially optimal pair is discarded. Each pointer moves inward at most n−1 times: O(n) time and O(1) space.

10.7 Edge cases

• Two heights only — the only possible container.
• All equal heights — moving either side is valid; area is evaluated at each step.
• One tall wall and many short walls — the short wall remains the bottleneck until it moves.