Using Nested Loops for Generating Pairs

The Combinatorial Brute Force

One of the most common applications of a nested loop is generating pairs. The classic problem is the "Two Sum" problem: Find two numbers in an array that add up to a specific target.

The Naive Pair Generation

To check every possible combination of two elements, you fix one element (using an outer loop) and compare it to every other element (using an inner loop).

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

The Duplicate Work Problem

The loop above works, but it does unnecessary work.

1. It compares an element with itself (when i == j).
2. It checks pairs twice. It checks array[0] with array[1], and later it checks array[1] with array[0].

The Optimized Nested Loop

To generate unique pairs without repetition and without self-comparison, the inner loop must always start one position ahead of the outer loop.

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

By setting int j = i + 1, the inner loop only looks at the elements to the right of i.

Time Complexity

Even though the inner loop runs fewer times as i increases, the time complexity is mathematically O(N^2 / 2). In Big O notation, we drop the division, leaving us with an O(N^2) worst-case scenario.

The Takeaway

Starting the inner loop at i + 1 is a mandatory design pattern when generating unique combinations or pairs. It prevents redundant checks and prevents an element from pairing with itself.