NESTED LOOPS IN C++

Page Content

Welcome to the page dedicated to nested loops in C++! This page provides all the key information, code examples, and practical tips for working with nested loops, which are essential for iterating through complex data structures and multidimensional data. Using the table of contents, you can quickly jump to interesting sections and find the content that interests you.

Introduction

Basic Structure of Nested Loops

Nested loops are structures where one loop is placed inside another. This concept enables iteration through multidimensional data structures, such as matrices, where the outer loop manages rows, and the inner loop manages columns.

The key elements of this structure are:

• Initialization and condition of the outer loop for iterating through rows.
• Initialization and condition of the inner loop for iterating through columns of each row.
• Processing of each element in the matrix within the body of the inner loop.

Consider the following C++ example that illustrates the basic structure of nested loops:

for (int i = 0; i < num_rows; i++) {
    for (int j = 0; j < num_col; j++) {
        // Processing the element at position [i][j]std::cout << matrix[i][j] << " ";
    }
    std::cout << std::endl;
}
    

In this example, the outer loop controls the rows of the matrix, while the inner loop iterates through the columns of each row. This approach allows for systematic processing of each element in a two-dimensional structure.

Notes:

• Ensure proper initialization and conditions for the loops to avoid infinite iterations.
• In the case of multidimensional structures, excessive depth of nested loops can reduce code readability and affect performance.
• Consider using functions or modularizing the code for more complex operations to keep the code organized.

Examples of nested loops

Example 1: Writing numbers by rows and columns​

​Example 2: Generating the Multiplication Table

Test your code in the editor!

​​Example 3: Drawing a Star Pattern

​​​Example 4: Looping through a Two-Dimensional Array

​​​​Explanation of More Complex Scenarios Using Nested Loops

​​​​​Warnings about Potential Errors with Nested Loops

Additional Nested Loop Types in C++

Nested loops are not limited to for. You can freely combine for, while, and do-while depending on the problem: counters with known bounds (often for), condition-driven iteration (while), or “run at least once” behavior (do-while).

1) while inside a for loop

Use this when the outer loop has a clear, fixed range (rows), while the inner loop depends on a condition that may vary dynamically (columns). The while loop re-checks its condition each time, which is ideal if the stop condition may change during iteration.

2) do-while inside a for loop

A do-while loop executes at least once, which is useful for patterns that always need one iteration before checking a condition (e.g., printing the first symbol in a row). The condition is evaluated at the end of each inner iteration.

3) Two nested while loops

When both bounds are condition-driven (not just simple counters), two while loops can be clearer. Always ensure each loop’s condition will eventually become false (increment/decrement or state change).

4) Mixing loop types

You can nest in any order: for inside while, while inside do-while, etc. Choose the loop that best expresses the control logic: known counts → for, condition-first → while, must-run-once → do-while.

Best Practices & Tips

• Initialize inner counters inside the outer loop; otherwise the inner loop may not reset correctly.
• Ensure termination: change the loop variables or state to avoid infinite loops.
• Choose the clearest loop for the job: readability beats cleverness.
• Avoid heavy work in inner loops where possible; move invariant calculations outside.
• Prefer size_t / std::size_t for indices when iterating containers like std::vector.

In summary, mix and match for, while, and do-while to express intent clearly and safely.

Advanced Uses of Nested Loops in C++

Nested Loops in Sorting Algorithms

Nested loops are often used in sorting algorithms, such as Bubble Sort.

#include<iostream>void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int array[] = {5, 3, 8, 4, 2};
    int n = sizeof(array) / sizeof(array[0]);
    
    bubbleSort(array, n);
    
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << array[i] << " ";
    }
    std::cout << "\n";
    
    return 0;
}
        

Finding Triplets of Numbers with a Given Sum

Nested loops are frequently used in combinatorial problems. The following example finds all triplets of numbers in an array whose sum equals a given value.

#include<iostream>void findTriplets(int arr[], int n, int target) {
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] == target) {
                    std::cout << "Triplet: " << arr[i] << ", " << arr[j] << ", " << arr[k] << "\n";
                }
            }
        }
    }
}

int main() {
    int array[] = {1, 4, 6, 8, 3, 7};
    int target = 15;
    int n = sizeof(array) / sizeof(array[0]);
    
    findTriplets(array, n, target);
    
    return 0;
}
        

Conclusion

Nested loops enable the solving of complex problems such as sorting and combinatorial tasks. The efficiency of an algorithm depends on the number of iterations, so it's important to consider optimizations when working with large datasets.

Explanation of the Code

This code searches through all possible triplet combinations from the array and checks if their sum matches the given target value.

First loop (i from 0 to n-2)

Sets the first number of the triplet.

Second loop (j from i + 1 to n-1)

Sets the second number of the triplet.

Third loop (k from j + 1 to n)

Sets the third number of the triplet.

Condition check (arr[i] + arr[j] + arr[k] == targetSum)

If the sum of the numbers equals targetSum, the triplet is printed.

Example with an array

Array: [1, 5, 3, 7, 2, 4, 6], targetSum = 12

Possible triplets that sum to 12 are:

• (1, 5, 6)
• (1, 4, 7)
• (3, 4, 5)

Relation to Combinatorics

This problem falls into combinatorial problems as it requires checking all possible combinations of three elements from a set.

Number of Possible Combinations

If we have n elements, the number of ways to choose three elements (without considering the order) can be calculated using the combinatorial coefficient:

C(n, 3) = n! / (3!(n − 3)!) = n(n − 1)(n − 2) / 6

In the Code

The triple loop goes through all possible combinations, resulting in a time complexity of O(n³).

Problem Optimization

Sorting + Two Pointers Method – O(n²)
This can be improved by first sorting the array and then using the two pointers method instead of the third loop.

Hash Map Method – O(n²)
Instead of the third loop, we can use a hash table for a faster check of targetSum - (arr[i] + arr[j]).

Conclusion

This example demonstrates how nested loops are used in combinatorial problems. Although this approach is simple, it may be inefficient for large arrays. Optimizations such as the "Two Pointers" method or using a hash table can improve performance.

In the following example of the optimized version of the code for finding triplets that sum to a given number, sorting and the two-pointer technique are used to achieve better efficiency compared to three nested loops.

Explanation of the Optimized Code:

• Sorting the array: First, we sort the array, which allows the use of two pointers.
• Skipping duplicates: If the current element is the same as the previous one, we skip it to avoid duplicates in the output.
• Two-pointer technique: After selecting the first element of the triplet, we set two pointers, one at the next element and the other at the last element. Then, we move the pointers based on the sum of the numbers in relation to the target sum.
• Time complexity: This optimization reduces the complexity from \(O(n^3)\) to \(O(n^2)\), which significantly improves efficiency for larger arrays.

This optimized version is much faster for larger arrays because it uses sorting and two pointers to reduce the number of checks.