How to Optimize a Nested Loop into a Single Loop

Flattening the Curve

To understand how to optimize a nested loop, we must look at a practical example. Let's solve the most famous interview question: Two Sum. Given an array of integers and a target sum, find if any two numbers add up to the target.

The O(N^2) Nested Loop Approach

The brute force logic checks every possible pair.

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

The inner loop's entire job is to scan the future elements searching for the complement: (target - nums[i]).

The Optimization Strategy

Instead of looking forward with an inner loop, what if we look backward using memory? As we iterate, we can store every number we see in a Hash Set. At every step, we check the Set to see if our required complement is already in there. Hash Set lookups are instant (O(1)).

The O(N) Single Loop Approach

HashSet<Integer> seen = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    
    // O(1) lookup completely replaces the inner loop!
    if (seen.contains(complement)) {
        return true;
    }
    
    // Remember this number for future iterations
    seen.add(nums[i]);
}

The Result

We completely eliminated the inner loop. The algorithm now passes through the array exactly once. We traded O(1) space for O(N) space (the Hash Set), but we improved the speed from O(N^2) to O(N).

The Takeaway

Whenever an inner loop is simply searching for a value, it can almost always be deleted and replaced with an O(1) Hash Set or Hash Map lookup.