Count Iterations of a Nested Loop
Solve this ProblemEasy10 min
Topics
BasicsComplexity
Companies
TCSInfosysWipro
For the loops
for (i = 0; i < n; i++) and, inside it, for (j = i + 1; j < n; j++), return how many times the inner body runs.
Nested loopsNested LoopsA loop placed inside another loop; the inner loop runs completely for every single pass of the outer one. multiply: the inner loop runs completely for every pass of the outer one. Here the inner loop gets shorter each time, but the total — n(n − 1)/2 — still grows with n², so this loop shape is O(n²). It is the shape of every "check all pairs" algorithm.
Test Case 1:
Input:n = 4
Output:6
Explanation:The inner loop runs 3 + 2 + 1 + 0 = 6 times — once for every pair of distinct indexes.
Test Case 2:
Input:n = 1
Output:0
Explanation:With a single index there are no pairs.
Constraints
- ◆
0 ≤ n ≤ 2000
Try the Dry Run
Approach & Solutions
Run Both Loops and CountGood
Run "for i in 0..n−1, for j in i+1..n−1" and count how often the inner body executes. For i = 0 the inner loop runs n − 1 times, for i = 1 it runs n − 2 times, and so on down to 0 — a total that grows with n².
Time
O(n²)Space
O(1)Java
class Solution {
public int nestedLoopCount(int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
count++;
}
}
return count;
}
}Sum FormulaOptimal
The inner counts are n − 1, n − 2, …, 1, 0, whose sum is the number of ways to pick two different indexes: n(n − 1) / 2. Evaluating the formula gives the count without running anything — exactly the argument you write down when analysing a nested loop.
Time
O(1)Space
O(1)Java
class Solution {
public int nestedLoopCount(int n) {
return n * (n - 1) / 2;
}
}