Nested Loops
Nested loops put one loop inside another: the outer loop picks a row, a pass, or a starting item, and the inner loop sweeps across columns or compares it with other items. It is the most direct way to check every pair or visit every cell, so interviewers use it to see whether you can get a correct brute-force answer first and then reason about its cost. Knowing when O(n^2) is acceptable, and when to replace it, is the real skill being tested.
When to use it
- The problem asks you to check every pair, or every pair that meets a condition ("find two numbers that...", "count pairs where...").
- The input is a 2D grid or matrix and you must visit, rotate, or search its rows and columns.
- You need to compare each element against the others, such as finding duplicates or the closest pair when the input is small.
- The problem talks about substrings or subarrays and asks you to try every start and every end.
- A sorting-style process repeats passes over the data (bubble sort, selection sort), where each pass shrinks the unsorted part.
See it work
- Goal: find every pair of values in [2, 7, 4, 5] that adds up to 9. Plan: the outer loop index i picks the first number, and the inner loop index j looks at each number after it. Starting j at i + 1 means each pair is checked once and no number is paired with itself.
[2, 7, 4, 5] - i = 0, j = 1: 2 + 7 = 9. That matches the target, so we record the pair (2, 7). The inner loop keeps going because other partners for 2 could exist.
[2, 7, 4, 5] - The inner loop moves j to 2 and then 3. 2 + 4 = 6 and 2 + 5 = 7, so neither matches. The inner loop is finished, so the outer loop advances i to 1.
[2, 7, 4, 5] - i = 1 (value 7): 7 + 4 = 11 and 7 + 5 = 12. No matches. Notice the inner loop restarts at i + 1 = 2 each time, so it never looks back at index 0, which was already paired with 7.
[2, 7, 4, 5] - i = 2 (value 4), j = 3 (value 5): 4 + 5 = 9. Another match, so we record (4, 5). The outer loop then moves to i = 3, where the inner loop has nothing left to do, and the algorithm ends.
[2, 7, 4, 5]
Code template
Python
# Check every pair (i, j) with i < j.
# Returns each pair of values that adds up to target.
def find_pairs(a, target):
result = []
n = len(a)
for i in range(n): # outer: pick the first item
for j in range(i + 1, n): # inner: pair it with later items
if a[i] + a[j] == target:
result.append((a[i], a[j]))
return result
# For a grid, visit every cell:
# for r in range(len(grid)):
# for c in range(len(grid[0])):
# process(grid[r][c])C
// Check every pair (i, j) with i < j in an array of n ints.
// Prints each pair that adds up to target.
void find_pairs(int a[], int n, int target) {
for (int i = 0; i < n; i++) { // outer: pick the first item
for (int j = i + 1; j < n; j++) { // inner: pair it with later items
if (a[i] + a[j] == target) {
printf("%d %d\n", a[i], a[j]);
}
}
}
}
// For a grid with rows R and cols C, visit every cell:
// for (int r = 0; r < R; r++)
// for (int c = 0; c < C; c++)
// process(grid[r][c]);Java
// Check every pair (i, j) with i < j.
// Returns each pair of values that adds up to target.
static List<int[]> findPairs(int[] a, int target) {
List<int[]> result = new ArrayList<>();
int n = a.length;
for (int i = 0; i < n; i++) { // outer: pick the first item
for (int j = i + 1; j < n; j++) { // inner: pair it with later items
if (a[i] + a[j] == target) {
result.add(new int[]{a[i], a[j]});
}
}
}
return result;
}
// For a grid, visit every cell:
// for (int r = 0; r < grid.length; r++)
// for (int c = 0; c < grid[0].length; c++)
// process(grid[r][c]);
Complexity: Two loops over n items run in O(n^2) time and O(1) extra space; a grid with R rows and C columns takes O(R * C) time.
Programs that use it
- Prime Numbers in a Range
- Multiplication Table
- Prime Factors of a Number
- Right Triangle Star Pattern
- Pyramid Star Pattern
- Number Triangle Pattern
- Floyd’s Triangle
- Inverted Triangle Star Pattern
- Selection Sort
- Matrix Multiplication
Interview problems that use it
- Pair sum (brute force): The outer loop picks the first number, the inner loop tries every later number, and you report any pair that hits the target.
- Rotate a square matrix 90 degrees: Loop over rows and columns of one half of the matrix, swapping each cell with its transposed partner, then reverse each row.
- Spiral or row-by-row matrix traversal: The outer loop moves through rows (or layers) and the inner loop walks the columns of that row, collecting values in order.
- Count subarrays with a given sum: The outer loop fixes the start index and the inner loop extends the end, keeping a running sum to test at each step.
- Bubble sort: Each outer pass lets the inner loop swap neighbours that are out of order, pushing the largest remaining value to the end.
- Check for duplicates in a small array: Compare each element with every element after it; the first equal pair proves a duplicate exists.
Common mistakes
- Starting the inner loop at 0 instead of i + 1 for pair problems. You end up pairing an item with itself and counting every pair twice, which gives wrong counts.
- Mixing up row and column bounds in a grid, for example looping c up to the number of rows. This works on square grids and then crashes or skips cells on rectangular ones.
- Using nested loops without checking the input size. O(n^2) is fine for 1,000 items but too slow for 100,000, where a hash map or two pointers usually gives O(n) or O(n log n).
Frequently asked questions
When should I use nested loops in an interview?
Use them when you must examine every pair or every cell, or when the input is small enough that O(n^2) is fine. They are also a good first step: write the brute force, confirm it is correct, then look for a faster approach.
How do I know the time complexity of nested loops?
Multiply the work of the loops when the inner loop runs fully for each outer step. Two loops over n items give O(n^2). If the inner loop starts at i + 1 the count is about n(n-1)/2, which is still O(n^2). If the inner loop only runs a fixed number of times, such as 3, the total is O(n).
How can I speed up a nested loop solution?
Ask what the inner loop is searching for. If it is looking up a value, a hash map can turn it into an O(1) lookup. If the data is sorted, two pointers or binary search can replace the inner loop. For subarray problems, prefix sums or a sliding window often remove it.