Level Up DSA

Problem Understanding

Return the indices of the two numbers in nums that add up to target. Exactly one solution exists, and the same element cannot be reused.

Approach

Brute force checks every pair in O(n²). We optimize to O(n) time using a HashMap: store numbers we've seen and look up target - num in O(1).

Algorithm

1. Create an empty HashMap seen (number -> index).
2. Iterate nums with index i.
3. Compute need = target - nums[i].
4. If need is in seen, return [seen.get(need), i].
5. Otherwise store (nums[i], i) and continue.

Code

class Solution {
    public 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[] {};
    }
}

Line-by-Line Explanation

• Map<Integer, Integer> seen = new HashMap<>(); — stores encountered numbers and their indices.
• int need = target - nums[i]; — computes the complement needed to reach target.
• if (seen.containsKey(need)) — checks whether the complement was seen before.
• return new int[] { seen.get(need), i }; — returns the pair of indices.
• seen.put(nums[i], i); — records the current number for future lookups.

Dry Run

Input: nums = [2, 7, 11, 15], target = 9

| Step | i | num | need | seen | Action |
| 1 | 0 | 2 | 7 | {} | store 2 -> 0 |
| 2 | 1 | 7 | 2 | {2: 0} | found 2, return [0, 1] |

Complexity

• Brute force: O(n²) time, O(1) space.
• Optimized: O(n) time, O(n) space for the map.

Edge Cases

• Negative numbers and zeroes handled naturally by subtraction and hashing.
• Duplicates: the complement check runs before the key is overwritten.
• Exactly one solution guaranteed, so the fallback return is never reached.

Optimization Summary

The HashMap trades O(n) extra space to collapse the inner scan into O(1) lookups, turning a quadratic pair-check into a single linear pass.