# The Idea of Loop and Iteration

# Introduction to loop

To solve a problem, sometimes it is necessary to repeat a particular code statement several times (possibly doing some key 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.”

The idea of a loop helps us provide the flexibility of code reusability to simplifies complex problem solving, i.e., instead of writing the same code, again and again, we can execute the same code a finite number of times. Think! There are two types of loops mostly used in programming:

## for loop

We use “for” loop when we know how many times the loop will execute.

`for (loop initialisation; loop condition; loop update)`

{

loop body

}

## while loop

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

}

# Core elements in the design of a loop

**Loop initialization:**Initialization of the loop variables used before starting the first iteration of the loop execution.**Loop condition:**A boolean expression calculated at the beginning of each loop iteration to determines whether the loop body will execute or stop.**Loop body:**The core part of the 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 for the loop variable to control the repetitions of the loop.

**The flow of the loop execution**

- Loop conditions will be evaluated first.
- If the loop condition is true, then the loop body will run, the loop variable gets updated (increment/decrement operation), and the loop condition’s value is re-evaluated. The loop body will run as long as the loop condition will be true.
- As soon loop condition becomes false, we exit the loop and continue with the further code instructions.

# How to design a correct loop?

We should consider these critical steps during the design and ensure the correctness of the loop.

**Pre-condition:**must be appropriately defined and true before the loop executes.**Post-condition:**must be appropriately defined and true after the loop terminates.**Loop variant:**An exit condition that controls the loop’s execution must be appropriately defined to ensure loop termination.**Loop invariant:**A most critical aspect that is true before and after each iteration of a loop. The values of variables may change, but the loop invariant’s truth does not vary.

Let’s try to understand the above idea via examples.

## Example 1: Finding the sum of all integers from 1to 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.

- Before any ith iteration of the loop, the variable
**sum**must be equals to the sum of all integers from 1 to i-1**.** - At the ith iteration, we add the value i to the sum (
**sum = sum + i)**and increase the variable i by 1. This ensures that as we go through each iteration, the variable i would approach**n**and provide the sum of values from 1 to n after loop termination. - After the ith iteration, the variable
**sum**must be equals to the sum of all integers from 1 to i**.** - The above invariant will continue till the end of the loop.

**Solution Pseudo Code**

`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 maxi element in an array of integers

**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:

- We compare
**max**with new value X[i].**If (max < X[i])**, it means we have found a value that is greater than the max of all the values from X[0] to X[i-1]. In such a situation, we update the max value with X[i]i.e.**max = X[i].**Otherwise, we ignore it, and the value stored in**max**is still the maximum of all integers from**X[0]**to**X[i].** - We also increase
**i**by**1**through each iteration to update the maximum from**X[0]**to**X[n-1]**in the variable**max.**

**Solution Pseudo Code**

`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

}

# Common errors in writing loops

## 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.

- 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 the user manually shuts down the system.
- 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

}

- Some online games execute in an infinite loop. The game will keep accepting the user requests until the user exits from the game.
- 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

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:

- Using <=” instead of “<” while checking the expression in the loop condition.
- Fails to consider that a sequence that starts at zero rather than one.

**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**

- Case1: for (int i = 1; i < n; i = i + 1) { … }
- Case2: for (int i = 0; i <= n; i = i + 1) { … }

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) { … }

# Examples of various loops Patterns

## Increasing loop by 1

Finding the nth 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])

## Increasing loop 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 wave form

`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])

}

## Increasing loop by power of 2

Exponential search in an unbounded array

`while (i < n && X[i] <= key)`

i = i*2

## Loop decreasing by factor of 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 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 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 on a 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)

}

# Application of loop in Problem Solving

- The incremental approach using a single loop
- Nested loop to solve problems on 1D and 2D array
- Two pointers approach, Sliding window approach
- Problem-solving using a hash table
- Linked list problem solving
- Problem-solving stack, queue, and Priority queue
- Problem-solving in a tree using BFS and iterative tree traversals(stack)
- The bottom-up approach of dynamic programming
- Problem-solving using Iterative Backtracking

## Critical Ideas to think in the loop!

- Sometimes we forget to initialize and update the variable used in the condition of the loop. This is a serious programming errors.
- Although loops typically iterate over only one variable, sometimes for loops need to work with multiple variables.
- An infinite loop will execute until one of three things happens: 1) The computer or application stopped forcefully 2) The computer encounters an EXIT statement 3) An error forces the application to ‘crash’
- 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.

## Critical Ideas to explore further in Loop!

- Idea and use case of do-while Loop
- Break and Continue loop statements
- Two pointers and sliding window approach
- The idea of iterator in data structure
- Iteration vs. Recursion comparison
- Iterative problem solving approaches
- Time complexity analysis of various loops

## Basic coding problems to practice

- Convert roman to integer, Fizz Buzz Problem, Look-and-Say Sequence
- Move zeroes to an end, Merge two sorted array, max and min of an array
- Print a given matrix in spiral form, Rotate a matrix by 90 degrees

## Content References

- Algorithms by CLRS
- http://www.cs.iit.edu/~cs561/

If you have any ideas/queries/doubts/feedback, please comment below or write us at **contact@enjoyalgorithms.com**. Enjoy learning, Enjoy coding, Enjoy algorithms!

*Originally published at *www.enjoyalgorithms.com/coding-interview