I am going to start with the most basic Leetcode problem of all - the Hello World of Leetcoding, if you will.

Problem:

You're given an integer array nums and an integer target.
Return the indices of the two numbers that add up to the target.

Constraints: You may assume exactly one solution. Cannot use the same element twice.

Brute Force:

Check all pairs — it works, but inefficient for large arrays

for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] == target) {
            return new int[]{i, j};
        }
    }
}

Time - O(n²)

Space - O(1)

Optimized - Using Hashmap

Use map to track num → index. Check target - num before adding current num.

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int diff = target - nums[i];
    if (map.containsKey(diff))
        return new int[]{map.get(diff), i};
    map.put(nums[i], i);
}

Time: O(N)

Space: O(N)

My notes:

By looking at the problem, I initially can think of running a nested loop and adding each element with every other element in the array. If two numbers add up to the target value, return the indices i and j, which are the two indices that add up to the target. This is the brute force approach.

But for the optimized approach, we think differently. Rather than going and checking each pair, I ask myself: if I’m at a number x, what number do I need to complete the target sum? The answer is target - x — and that’s the key idea. I don’t need to check every possible pair; I just need to know whether the complement has already appeared before in the array.

This leads to using a HashMap where I store every number I’ve seen so far, along with its index. As I loop through the array, for each number, I check if its complement is already in the map. If it is, I return the pair of indices — the one stored in the map and the current one. If not, I store the current number and move on. The beauty of this approach is that I’m both checking and building the map in the same loop, which leads me to an efficient O(N) solution.

Quick Dry Run:

Let’s say the input is nums = [3, 1, 7, 2] and target = 9. Start with an empty map.

First number is 3. Need 6 to reach the target. Haven't seen it yet → store 3 at index 0.
Next is 1. Need 8. Still not in the map → store 1 at index 1.
Then comes 7. Need 2. Not there → store 7 at index 2.
Now hit 2. Need 7. This time it is in the map — stored 7 earlier at index 2.
Return [2, 3] because 7 (at index 2) + 2 (at index 3) = 9.

Two Sum