Sometimes, we repeatedly repeat a particular code statement to solve a problem until a specific condition is satisfied. This is known as iteration, which allows us to "write code once" and "execute many times." In computer programming, iteration is often referred as ‘looping’ because instead of repeatedly writing the same code, we can execute the same code a finite number of times. Iteration provides code reusability and simplifies steps of problem-solving.
In data structure and algorithms, several problem-solving approaches are based on iteration. So a good grasp of loop fundamentals is essential for mastering these approaches. Here are some excellent examples of iterative problem-solving approaches:
Iteration is implemented using the loop in programming, where we primarily use two types of loops: "for" loop and "while" loop.
We use the for loop when we know how many times the loop will execute. In other words, the for loop helps us to run some particular code statement defined number of steps.
Inside the for loop, we use a loop variable to control the loop execution, where the initial value of variable decides the starting point. So, we start by initializing the loop variable to some value and checking whether the loop condition is true or not. If the loop condition is true, code inside the loop body will execute. After this loop, execution will move to the next iteration by incrementing or decrementing the loop variable. This step will be repeated till the loop condition becomes false.
for (loop initialisation; loop condition; loop update)
{
loop body
}
The while loop is used to execute the loop body until a specific condition is false. We mainly apply this idea when we don’t know how many times the loop will execute.
The while loop consists of a loop condition, a block of code as a loop body, and a loop update expression if required. First, the loop condition is evaluated, and if it is true, code within the loop body will be executed. This process repeats until the loop condition becomes false. For better intuition, while loop can be thought of as a repeating if statement.
loop initialisation
while (loop condition)
{
loop body
loop update
}
Special Notes
Loop initialization: We initialize loop variables before starting the first iteration of the loop.
Loop condition: This is a boolean expression calculated at the beginning of each iteration to determine whether the loop body will execute or stop.
Loop body: The core part of a loop where we perform required operations to manipulate data at each iteration. There can be more than one code statement here.
Loop update: We perform increment/decrement operations on loop variables to control repetitions of the loop.
Here is the basic flow of a loop execution: Loop conditions will be evaluated first. If loop condition is true, then loop body will run, and loop variable gets updated (increment/decrement operation). The loop body will run as long as the loop condition will be true. When loop condition becomes false, we exit the loop and continue with the further code instructions.
We should consider these critical steps to design and check the correctness of an iterative code:
Let's understand the above idea via some examples.
Pre-condition: We need to define two variables: a variable i that acts as a loop counter and a variable sum to store the sum of all integers. We want to do a sum from 1 to n, so at the start, we initialize sum = 0 and i = 1.
Post-condition: After the loop termination, the value of the sum must be equal to the sum of all integers from 1 to n.
Loop variant: The loop should terminate after the addition of all integers from 1 to n ,i.e, i <= n. In other words, loop should not terminate until we have added n to the sum.
Loop invariant: We need to set the loop invariant to ensure correct output after the loop termination. As discussed above, the loop invariant must be true before and after each iteration.
Solution Pseudocode
int findSum(int n)
{
int i = 1
int sum = 0
while (i <= n)
{
sum = sum + i
i = i + 1
}
return sum
}
Pre-condition: we need to define two variables: a loop variable i that acts as a loop counter and a variable max to store the maximum of all integers. Before starting the loop to find the max value from X[0] to X[n-1], we initialize max = X[0] and start the loop from i = 1. This pre-condition is true when we enter the first iteration of loop.
Post-condition: After loop termination, the max value must store the maximum of all values from X[0] to X[n - 1].
Loop variant: The loop must terminate after finding the max of all integers from X[0] to X[n-1]. In other words, the loop should not terminate until we have compared X[n - 1] to the max i.e. i <= n - 1 or i < n.
Loop invariant: Let's assume invariant is true after (i - 1)th iteration, i.e., max stores the maximum of all integers from X[0] to X[i-1]. We need to design instruction so that the invariant must be true after ith iterations of the loop i.e. max must be equal to the max of all integers from X[0] to X[i]. Here are the steps of the ith iteration:
Solution Pseudocode
int findMax(int X[], int n)
{
int max = X[0]
for (int i = 1; i < n; i = i + 1)
{
if (X[i] > max)
max = X[i]
}
return max
}
An infinite loop occurs when a loop condition continuously evaluates to true or not making progress towards loop termination. It appears most of the time due to the incorrect update of loop variables or some error in the loop condition. Usually, this is an error, but it's common for infinite loops to occur accidentally.
For example, we want to display the sum of all numbers from 5 to 10 via following code and end up with an infinite loop because we did not increment the loop variable. Here loop variable remains the same through each iteration, and progress is not made towards termination.
int i = 5
int sum = 0
while (i <= 10)
sum = sum + i
Here is the correct version of the code:
int i = 5
int sum = 0
while (i <= 10)
{
sum = sum + i
i = i + 1
}
Other examples of Infinite loop
Example 1: For i < 0, this goes into an infinite loop!
void infinteLoop(int i)
{
while (i != 0)
{
i = i - 1
}
}
Example 2: Here loop condition is "1" which is always true!
int i = 0
while(1)
{
i = i + 1
print(i)
}
In some situations, an infinite loop can be used on purpose. For example, we use an infinite loop for applications that continuously accept user input and constantly generate the output until user comes out of the application manually.
Example 1: An operating system is the best example of it. It runs in an infinite loop and performs tasks continuously. It only comes out of an infinite loop when user manually shuts down the system.
Example 2: Suppose we read a sequence of data from input and stop reading as soon as a particular condition becomes true. The general structure of such input loop:
read the first element
while (element is valid)
{
process the element
read the next element
}
Example 3: Some online games execute in an infinite loop. The game will keep accepting user requests until user exits from the game.
Example 4: A typical web server runs in an infinite loop as the server responds to all the client requests. It takes a request for a web page, returns a web page, and waits for the subsequent request. It will come out of an indefinite loop only when the admin shuts down the server manually.
while (true)
{
Read request
Process request
}
This is an error involving boundary condition of the loop i.e. initial or termination condition of loop variables. Such a problem can arise when programmer makes mistakes like this:
Off-By-One example 1
int X[5]
for (int i = 0; i <= 5; i = i + 1)
print(X[i])
Above program will result in array out-of-bounds exception because we are trying to display result for X[5] and the upper bound of the array is index only 4. This is because index for the array starts at 0 instead of 1 in most programming languages. The correct code is displayed below.
int X[5]
for (int i = 0; i < 5; i = i + 1)
print(X[i])
Off-By-One Example 2
Suppose we want to process n elements of an array starting from index 0. In the first case, loop will execute n - 1 time and in the second case, loop will execute n + 1 time. Both are situations of off-by-one error. The loop can be written correctly as: for (int i = 0; i < n; i = i + 1) { ... }
Finding the nth Fibonacci using bottom-up approach of DP
for(int i = 2; i <= n; i = i + 1)
Fib[i] = Fib[i - 1] + Fib[i - 2]
Kadane algorithm loop of finding maximum subarray sum
for (i = 1; i < n; i = i + 1)
{
curr_maxSum = max (curr_maxSum + X[i], X[i])
if(maxSum < curr_maxSum)
maxSum = curr_maxSum
}
Boyer–Moore voting algorithm of finding majority element in an array
for(int i = 0; i < n; i = i + 1)
{
if(count == 0)
majorityCandidate = X[i]
if(X[i] == majorityCandidate)
count = count + 1
else
count = count - 1
}
Nested loop of the Bubble sort algorithm
for(int i = 0; i < n; i = i + 1)
{
for(int j = 0; j < n - i - 1; j = j + 1)
{
if( X[j] > X[j+1])
{
temp = A[j]
X[j] = X[j+1]
X[j+1] = temp
}
}
}
Nested loop of the Insertion sort algorithm
for(int i = 1; i < n - 1; i = i + 1)
{
int key = X[i]
int j = i - 1
while (j >= 0 && X[j] > key)
{
X[j + 1] = X[j]
j = j - 1
}
X[j + 1] = key
}
Nested loop of finding transpose of a square matrix
for (int i = 0; i < n; i = i + 1)
for (int j = i + 1; j < n; j + 1)
swap(X[i][j], X[j][i])
A single loop of finding max and min in an array
while (i < n)
{
if (X[i] < X[i + 1])
{
if (X[i] < min)
min = X[i]
if (X[i + 1] > max)
max = X[i + 1]
}
else
{
if (X[i] > max)
max = X[i]
if (X[i + 1] < min)
min = X[i + 1]
}
i = i + 2
}
Single loop of sorting an array in a waveform
for (int i = 0; i < n; i = i + 2)
{
if (i > 0 && X[i - 1] > X[i])
swap(X[i], X[i - 1])
if (i < n - 1 && X[i] < X[i + 1])
swap(X[i], X[i + 1])
}
Loop of exponential search in an unbounded array
while (i < n && X[i] <= key)
i = i*2
Loop of iterative binary search
while (left <= right)
{
int mid = left + (right - left)/2
if (X[mid] == key)
return mid
if (X[mid] < key)
left = mid + 1
else
right = mid - 1
}
Loop of searching iteratively in a BST
while (root != NULL)
{
if (key < root->data)
root = root->left
else if (key > root->data)
root = root->right
else
return true
}
Two-pointers loop of reversing an array
while (left < right)
{
int temp = X[left]
X[left] = X[right]
X[right] = temp
left = left + 1
right = right - 1
}
Two pointers loop of finding pair sum in a sorted array
while (l < r)
{
if(X[l] + X[r] == k)
return 1
else if(X[l] + X[r] < k)
l = l + 1
else
r = r - 1
}
Two-pointers loop of merging algorithm in merge sort
while (i < n1 && j < n2)
{
if (X[i] <= Y[j])
{
A[k] = X[i]
i = i + 1
}
else
{
A[k] = Y[j]
j = j + 1
}
k = k + 1
}
Two-pointers loop of partition algorithm in quicksort
for (int j = left; j < right; j = j + 1)
{
if (x[j] < pivot)
{
i = i + 1
swap(X[i], X[j])
}
}
Two-pointers loop of finding loop in a linked list: Floyd algorithm
while (slow && fast && fast->next)
{
slow = slow->next
fast = fast->next->next
if (slow == fast)
return 1
}
BFS Traversal of a binary tree using queue
while (Q.empty() == false)
{
TreeNode temp = Q.dequeue()
print(temp->data)
if (temp->left != NULL)
Q.enqueue(temp->left)
if (temp->right != NULL)
Q.enqueue(temp->right)
}
Pre-order traversal in binary search using stack
while (S.empty() == false)
{
Treenode temp = S.pop()
printf(temp->data)
if (temp->right)
S.push(temp->right)
if (temp->left)
S.push(node->left)
}
When we declare a variable inside loop, the scope of that variable ends with the end of loop statement. In other words, the scope of the loop variable is inside the loop, and it can not be accessed from outside the loop.
int w
for(int x = 0; x < 5; x = x + 1)
{
int y
// we can use x, y, w here
}
int z
// we can only use w, z here;
x and y are only visible in the scope of the loop.
Enjoy learning, Enjoy coding, Enjoy algorithms!