Problem-solving workflow

Restate the problem in your own words. Identify the input, the output, the constraints and anything ambiguous: are duplicates allowed, is the answer unique, what if there is no answer? Ask or decide, and write the decision down.

Most wasted time comes from solving a slightly different problem than the one asked.

Create small examples by hand, including the typical case, the smallest case and an awkward case. Work out the expected answers yourself. These become your tests and often reveal the pattern.

For two-sum with target 13: [7, 11, 2, 15, 4, 9] returns indexes of 11 and 2; [1, 2] with target 10 has no answer; [3, 3] with target 6 uses two equal values at different indexes.

Write the simplest correct solution first, whatever its speed. It proves you understand the problem, gives a correct answer for small inputs, and later serves as an oracle to test the fast solution against.

Check every pair for two-sum: obviously correct, O(n²). Watch how many pairs it examines, including the worst case where no pair works.

1public static int[] twoSum(int[] nums, int target) {
2    for (int i = 0; i < nums.length; i++) {
3        for (int j = i + 1; j < nums.length; j++) {
4            if (nums[i] + nums[j] == target) {
5                return new int[] { i, j };
6            }
7        }
8    }
9    return new int[] { -1, -1 };
10}

Ask which known pattern the problem resembles: searching a sorted range (binary search), a contiguous range (prefix sums or sliding window), pairs (two pointers or hashing), nearest larger value (monotonic stack), choices with overlap (dynamic programming), connections (graph).

In the brute force, the inner loop repeatedly asks “is there a value equal to target - nums[i] later in the array?”. A question about membership is exactly what a hash set or map answers in O(1).

Choose the structure that makes the repeated question cheap. Membership by value: hash set or map. Smallest next: heap. Order and ranges: balanced tree. Position: array.

For two-sum, a HashMap<value, index> turns the inner loop into a single lookup.

Convince yourself the idea is right before coding. A short argument is enough: state an invariant or explain why no answer is missed. For the hash map version: when we reach index i, the map holds every earlier value, so if a partner exists earlier we will find it; if the partner comes later, it will find i when it is processed.

Proving catches ideas that work on the examples but fail in general.

State time and space complexity and check them against the constraints. Hash map two-sum: one pass, O(1) expected per lookup and insert, so O(n) time and O(n) space. For n = 10⁵ this is easily fast enough, while the O(n²) baseline needs about 5 × 10⁹ pair checks.

Mention the assumption: hashing is O(1) on average; adversarial keys can degrade it.

Write the code from the design, keeping names meaningful and each step small. Implement the contract exactly, including what to return when there is no answer.

The animation shows the optimised solution: each iteration computes the partner value, looks it up, and stores the current value.

1static int[] twoSum(int[] nums, int target) {
2    Map<Integer, Integer> seen = new HashMap<>();          // value -> index
3    for (int i = 0; i < nums.length; i++) {
4        Integer j = seen.get(target - nums[i]);
5        if (j != null) return new int[] { j, i };
6        seen.put(nums[i], i);
7    }
8    return new int[] { -1, -1 };
9}

1public static int[] twoSum(int[] nums, int target) {
2    Map<Integer, Integer> seen = new HashMap<>();      // value -> index
3    for (int i = 0; i < nums.length; i++) {
4        int need = target - nums[i];
5        if (seen.containsKey(need)) {
6            return new int[] { seen.get(need), i };
7        }
8        seen.put(nums[i], i);
9    }
10    return new int[] { -1, -1 };
11}

Run your hand-made examples, then compare the fast solution with the brute force on thousands of small random inputs. Mismatches show real bugs, and the failing input is already small. Use a fixed random seed so a failure is reproducible.

Include edge cases: empty, one element, duplicates, negatives and large values.

1Random rnd = new Random(1);
2for (int t = 0; t < 10_000; t++) {
3    int[] a = rnd.ints(1 + rnd.nextInt(8), -5, 6).toArray();
4    int target = rnd.nextInt(11) - 5;
5    boolean fast = twoSum(a, target)[0] != -1;
6    boolean slow = false;
7    for (int i = 0; i < a.length; i++) for (int j = i + 1; j < a.length; j++) if (a[i] + a[j] == target) slow = true;
8    if (fast != slow) throw new AssertionError(Arrays.toString(a) + " target " + target);
9}

Optimise only after the solution is correct and you know where the time goes. First improve the algorithm (better complexity), then the constants (primitive arrays instead of boxed collections, avoiding repeated allocation).

Measure with realistic input. Optimising code that is not the bottleneck wastes effort and makes it harder to read.