To solve a problem, sometimes it is necessary to repeat a particular code statement several times (possibly doing some critical operations at each repetition) until a specific condition is satisfied. It is known as iteration, which allows us to "write code once" and "execute many times." We implement iteration using the idea of the loop in programming languages.
In programming, iteration is often referred to as ‘looping’ because instead of writing the same code, again and again, we can execute the same code a finite number of times. It provides the flexibility of code reusability and simplifies problem-solving in computer science. There are two types of loops primarily used in programming: the for loop and the while loop.
Several problem-solving approaches in data structure and algorithms are based on iteration. So a good grasp of the loop fundamental of loops is essential for mastering these approaches. Here is a list of iterative problem-solving strategies:
We use the "for" loop when we know how many times the loop will execute. In other words, the for loop help us to execute some particular code defined number of steps.
for (loop initialisation; loop condition; loop update)
{
loop body
}
In the for loop, we use a loop variable to control the flow of the loop, where the initial value of the variable decides the starting point of the loop. So, we start by initialising the loop variable to some value and checking whether the loop condition is true. If the loop condition is true, then the loop body is executed, and the loop variable gets updated. This step is repeated till the loop condition becomes false.
It is used when we want to continue until a specific condition is false. We apply this loop idea when we don’t know how many times the loop will execute.
loop initialisation
while (loop condition)
{
loop body
loop update
}
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, then the code within the loop body will be executed. This process repeats until the loop condition/expression becomes false. Thus, for better intuition, the while loop can be thought of as a repeating if statement.
Special Notes
The flow of the loop execution
We should consider these critical steps to design and check the correctness of an iterative code in data structure and algorithms:
Let's try to understand the above idea via some examples.
Example 1: finding the sum of all integers from 1 to n
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 would like to do a sum from 0 to n, so at the start, we initialize both variables to 0, i.e., sum = 0, i = 1
Post-condition: After the loop termination, the value of the sum must be equals to the sum of all integers from 1 to n.
Loop variant: The loop should terminate when we have added all integers from 1 to n,i.e, i<= n. In other words, the loop should not terminate until we have added n to the sum.
Loop invariant: Now, we need to set the loop invariant so that when the loop terminates, we will have the correct output. As discussed above, the loop invariant must be true before and after each loop iteration.
Solution Pseudocode
int findSum(int n)
{
int i = 1
int sum = 0
while (i <= n)
{
sum = sum + i
i = i + 1
}
return sum
}
Example 2: Finding the max element in an array
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 with i = 1. This pre-condition holds true when we enter the first iteration of the loop.
Post-condition: After the loop termination, the max value must store the max 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 store 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 - the variable 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
}
Infinite loops
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 the 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 the following code and ended up with an infinite loop because we did not increment the loop variable. The loop variable remains the same through each iteration, and progress is not made towards loop 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 the 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
//loop condition is "1" which is always true.
int i = 0
while(1)
{
i = i + 1
print(i)
}
But in some situations, an infinite loop can be used on purpose. For example, we use an infinite loop for the applications that continuously accept the user input and constantly generate the output until the user comes out of the application manually.
We read from input a sequence of data and stop reading from the input as soon as a particular condition becomes true. The general structure of an input loop:
read the first element
while (element is valid)
{
process the element
read the following element
}
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
}
Another popular way is:
for ( ; ; )
{
// Read request
// Process request
}
Off-By-One error in the loop
It is an error involving the boundary condition of the loop: the loop variable's initial value or the loop's end condition. This problem could arise when a programmer makes mistakes such as:
Off-By-One Example 1
int X[5]
for (int i = 0; i <= 5; i = i + 1)
print(X[i])
The above program will result in an array out of bounds exception because we will try to display the result for X[5] and the upper bound of the array is only 4. This is because the 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
In the first case, the loop will be executed (n-1) times and in the second case (n + 1) times, giving error off-by-one. The loop can be written correctly as: for (int i = 0; i < n; i = i + 1) { ... }
Loop increasing by 1
Finding the nth the Fibonacci: Bottom-up approach of DP
for(int i = 2; i <= n; i = i + 1)
Fib[i] = Fib[i - 1] + Fib[i - 2]
Kadane algorithm: 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: 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 loops
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
}
}
}
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
}
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])
Loop increasing by 2
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
}
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 Increasing or decreasing by a factor of 2
Exponential search in an unbounded array
while (i < n && X[i] <= key)
i = i*2
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
}
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: pointers moving in the opposite direction
Reverse an array
while (left < right)
{
int temp = X[left]
X[left] = X[right]
X[right] = temp
left = left + 1
right = right - 1
}
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: pointers moving in the same direction
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
}
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])
}
}
Floyd algorithm: finding loop in a linked list
while (slow && fast && fast->next)
{
slow = slow->next
fast = fast->next->next
if (slow == fast)
return 1
}
Loop with stack and queue data structure
BFS Traversal of 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 a loop, the scope of that variable ends with the end of the 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
// we can use x or w inside ()
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!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.