Nested Loops

📖 Introduction

Nested loops are loops placed inside other loops. The inner loop completes all its iterations for each iteration of the outer loop. This concept is fundamental for working with multi-dimensional data structures, generating patterns, and solving complex algorithmic problems.

---

🎯 Concept Visualization

Outer Loop (i = 0 to 2)
│
├── i = 0
│   └── Inner Loop (j = 0 to 2)
│       ├── j = 0 → Process (0,0)
│       ├── j = 1 → Process (0,1)
│       └── j = 2 → Process (0,2)
│
├── i = 1
│   └── Inner Loop (j = 0 to 2)
│       ├── j = 0 → Process (1,0)
│       ├── j = 1 → Process (1,1)
│       └── j = 2 → Process (1,2)
│
└── i = 2
    └── Inner Loop (j = 0 to 2)
        ├── j = 0 → Process (2,0)
        ├── j = 1 → Process (2,1)
        └── j = 2 → Process (2,2)

Total iterations: 3 × 3 = 9

---

📐 Basic Nested Loop Structure

for-for Loop:

for (int i = 0; i < rows; i++) {           // Outer loop
    for (int j = 0; j < cols; j++) {       // Inner loop
        printf("(%d, %d) ", i, j);
    }
    printf("\n");
}

Output (3×3):

(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)

---

🔄 Flowchart

           ┌─────────────┐
           │ i = 0       │
           └──────┬──────┘
                  │
          ┌───────▼───────┐
     ┌───►│ i < rows?     │──No──► Exit
     │    └───────┬───────┘
     │            │ Yes
     │    ┌───────▼───────┐
     │    │ j = 0         │
     │    └───────┬───────┘
     │            │
     │    ┌───────▼───────┐
     │ ┌─►│ j < cols?     │──No──┐
     │ │  └───────┬───────┘      │
     │ │          │ Yes          │
     │ │  ┌───────▼───────┐      │
     │ │  │ Process (i,j) │      │
     │ │  └───────┬───────┘      │
     │ │  ┌───────▼───────┐      │
     │ │  │ j++           │      │
     │ │  └───────┬───────┘      │
     │ └──────────┘              │
     │    ┌───────▼───────┐      │
     │    │ i++           │◄─────┘
     │    └───────┬───────┘
     └────────────┘

---

🔢 Iteration Count

Formula: Total iterations = Outer iterations × Inner iterations

---

🎨 Pattern Generation

Pattern 1: Rectangle of Stars

int rows = 3, cols = 5;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        printf("* ");
    }
    printf("\n");
}

Output:

* * * * *
* * * * *
* * * * *

Pattern 2: Right Triangle

int n = 5;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        printf("* ");
    }
    printf("\n");
}

Output:

*
* *
* * *
* * * *
* * * * *

Pattern 3: Inverted Triangle

int n = 5;
for (int i = n; i >= 1; i--) {
    for (int j = 1; j <= i; j++) {
        printf("* ");
    }
    printf("\n");
}

Output:

* * * * *
* * * *
* * *
* *
*

Pattern 4: Pyramid

int n = 5;
for (int i = 1; i <= n; i++) {
    // Spaces
    for (int j = 1; j <= n - i; j++) {
        printf(" ");
    }
    // Stars
    for (int k = 1; k <= (2 * i - 1); k++) {
        printf("*");
    }
    printf("\n");
}

Output:

    *
   ***
  *****
 *******
*********

Pattern 5: Number Triangle

int n = 5;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        printf("%d ", j);
    }
    printf("\n");
}

Output:

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

---

📊 Working with 2D Arrays

Declaring and Initializing:

int matrix[3][3] = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

Traversing with Nested Loops:

int rows = 3, cols = 3;

// Print all elements
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        printf("%d ", matrix[i][j]);
    }
    printf("\n");
}

Output:

1 2 3
4 5 6
7 8 9

Sum of All Elements:

int sum = 0;
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        sum += matrix[i][j];
    }
}
printf("Sum: %d\n", sum);  // 45

---

📋 Matrix Operations

Row-wise Sum:

for (int i = 0; i < rows; i++) {
    int rowSum = 0;
    for (int j = 0; j < cols; j++) {
        rowSum += matrix[i][j];
    }
    printf("Row %d sum: %d\n", i, rowSum);
}

Column-wise Sum:

for (int j = 0; j < cols; j++) {
    int colSum = 0;
    for (int i = 0; i < rows; i++) {
        colSum += matrix[i][j];
    }
    printf("Column %d sum: %d\n", j, colSum);
}

Matrix Transpose:

int transposed[3][3];

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        transposed[j][i] = matrix[i][j];
    }
}

Diagonal Elements:

// Main diagonal (top-left to bottom-right)
printf("Main diagonal: ");
for (int i = 0; i < 3; i++) {
    printf("%d ", matrix[i][i]);
}
// Output: 1 5 9

// Anti-diagonal (top-right to bottom-left)
printf("\nAnti-diagonal: ");
for (int i = 0; i < 3; i++) {
    printf("%d ", matrix[i][2-i]);
}
// Output: 3 5 7

---

🔀 Different Loop Combinations

for-while:

for (int i = 0; i < 3; i++) {
    int j = 0;
    while (j < 3) {
        printf("(%d,%d) ", i, j);
        j++;
    }
    printf("\n");
}

while-for:

int i = 0;
while (i < 3) {
    for (int j = 0; j < 3; j++) {
        printf("(%d,%d) ", i, j);
    }
    printf("\n");
    i++;
}

while-while:

int i = 0;
while (i < 3) {
    int j = 0;
    while (j < 3) {
        printf("(%d,%d) ", i, j);
        j++;
    }
    printf("\n");
    i++;
}

---

🎯 Triple Nested Loops

For 3D data or complex operations:

// 3D array traversal
int cube[2][3][4];

for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++) {
        for (int k = 0; k < 4; k++) {
            cube[i][j][k] = i + j + k;
        }
    }
}
// Total iterations: 2 × 3 × 4 = 24

---

⚡ Performance Considerations

Time Complexity:

Optimization Tips:

1. Move invariants outside inner loop:

// Bad
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        int x = heavy_calculation();  // Computed n×m times!
        result[i][j] = x + i + j;
    }
}

// Good
int x = heavy_calculation();  // Computed once
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        result[i][j] = x + i + j;
    }
}

1. Cache-friendly access (row-major):

// Good (cache-friendly in C)
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        sum += matrix[i][j];
    }
}

// Less efficient (column-major access)
for (int j = 0; j < cols; j++) {
    for (int i = 0; i < rows; i++) {
        sum += matrix[i][j];
    }
}

---

⚠️ Common Mistakes

1. Wrong Variable in Inner Loop:

// Wrong!
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; i++) {  // BUG: i++ instead of j++
        printf("(%d,%d) ", i, j);
    }
}

// Correct
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {  // j++
        printf("(%d,%d) ", i, j);
    }
}

2. Using Same Variable:

// Wrong!
for (int i = 0; i < 3; i++) {
    for (int i = 0; i < 3; i++) {  // Shadows outer i
        // Confusing!
    }
}

// Correct - use different variables
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        // Clear and correct
    }
}

3. Off-by-One with Array Bounds:

int arr[3][3];

// Wrong - out of bounds!
for (int i = 0; i <= 3; i++) {
    for (int j = 0; j <= 3; j++) {
        arr[i][j] = 0;
    }
}

// Correct
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        arr[i][j] = 0;
    }
}

---

🎨 Advanced Pattern Examples

Diamond Pattern:

    *
   ***
  *****
 *******
*********
 *******
  *****
   ***
    *

int n = 5;
// Upper half
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - i; j++) printf(" ");
    for (int j = 1; j <= 2*i - 1; j++) printf("*");
    printf("\n");
}
// Lower half
for (int i = n - 1; i >= 1; i--) {
    for (int j = 1; j <= n - i; j++) printf(" ");
    for (int j = 1; j <= 2*i - 1; j++) printf("*");
    printf("\n");
}

Floyd's Triangle:

1
2 3
4 5 6
7 8 9 10

int num = 1;
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= i; j++) {
        printf("%d ", num++);
    }
    printf("\n");
}

---

🔑 Key Takeaways

1. Inner loop completes fully for each outer loop iteration
2. Total iterations = outer × inner
3. Use different loop variables (i, j, k)
4. Watch out for off-by-one errors with arrays
5. Consider cache-friendly access (row-major in C)
6. Be aware of time complexity (O(n²), O(n³))

---

⏭️ Next Topic

In the next module, you'll learn about Functions - how to organize code into reusable blocks.