Hello and welcome back to a wonderful article series on getting prepared for Competitive programming and coding interviews. Hope you are fine and doing good. In a few of the previous blogs we have learned about Recursion, Backtracking, and have solved many questions in respective categories. In this tutorial, we will be learning about some popular Array algorithms that are most asked and used in almost all coding problems related to Arrays. The algorithms we will study will be very much helpful in learning further topics related to competitive programming. So, belt your excitement, and let's get started.
Table of Contents
Prefix-Sum Algorithm
It is one important algorithm that is used to solve many array problems whether it is a one-dimension or two-dimension array. As the name suggests that in this algorithm we compute the sum of all the elements present before a particular element. Suppose we have an array of size N such that ith element of predict sum array prefix[i] = prefix[0] + prefix[1] + .... + prefix[i].
For Example
Applications Of Prefix-Sum Algorithm
- It is used in answering a range-based sum question, Xor questions.
- Product of elements in the given range
- Also Used to find maximum sum subarray
Real-Life problem statement on Prefix-sum Algorithm
To understand its importance let's pick one simple question. So the Problem statement is We are given an array of N integers. And we have a Q number of queries and in each query given L and R (left and right index). Your task is to print the sum of elements from index L and R inclusively. The output should be in 1-Based indexing.
Naive Approach ~ Now if you approach it using the Brute-force method then for calculating the sum for each query you will apply for loop and it will increase the time complexity of code and lead to TLE because the time complexity is O(N+Q).
#code
n = int(input())
arr = list(map(int, input().split()))
Q = int(input())
while Q > 0:
l, r = map(int, input().split())
sm = 0
for i in range(l-1, r):
sm = sm + arr[i]
print(sm)
Q = Q - 1
Prefix-Sum Approach ~ Now think about how we can use the pre-computed sum to answer the sum of each query in O(1) time. So we will create a prefix sum array where each index sum of all its previous elements will be stored inclusively. So for each query we can simply do prefix[R-1] - prefix[L-1] and we will get the required sum between the range. So this code will safely run under 1 second and will clear all test cases.
n = int(input())
arr = list(map(int, input().split()))
Q = int(input())
#create a prefix array with 1 based indexing
prefix = [0]*(n+1)
prefix[1] = arr[0]
#find the prefix sum array
for i in range(2,n+1):
prefix[i] = arr[i-1] + prefix[i-1]
#find sum of each query
while Q > 0:
l, r = map(int, input().split())
ans = prefix[r] - prefix[l-1]
print(ans)
Q = Q - 1
2) Kadane's Algorithm
Another most popular and used Array algorithm to deal with problems where we are asked to find sub-array like maximum product sub-array, maximum sum sub-array, maximum length sub-array for a particular case, etc. Most people find the use of this algorithm when there are negative elements in an array but it is also used in an array of positive elements. So first let us understand the Algorithm in a general way with a practical example.
Problem statement ~ So, our problem statement is like we are given an array of N integers containing positive and negative elements. Your task is to find the sub-array with the maximum sum.
Iterative Approach ~ Now if you think of solving the problem using Brute-force then it will take O(N^2) time-complexity and all the test cases will not pass.
Kadane's Algorithm Approach ~ Now Kadane's algorithm help to solve this in linear time complexity. What it says is to iterate over an array a single time and add the one element in a variable(current sum) and check that is it greater than the maximum sub-array sum. If yes then we update the maximum sub-array sum. And due to the presence of a negative element if the current sum value becomes negative then we update it by reinitializing to zero so that if there is another contiguous sub-array present then we can find it. The implementation is shown in the below code snippet.
def kadane(arr, n):
curr_sum = 0
max_sum = -1
for i in range(n):
curr_sum = curr_sum + arr[i]
if curr_sum > max_sum:
max_sum = curr_sum
if curr_sum < 0:
curr_sum = 0
return max_sum
arr = [1, 2, 7, -4, 3, 2, -10, 9, 1]
n = len(arr)
print(kadane(arr, n))
The above snippet helps find the only maximum sub-array sum. Now if we also want to print the sub-array elements then with a little bit of modification we can do that. Whenever we get a current sum greater than the maximum sub-array sum then while updating the maximum sum we can keep two-pointer as start and end that keep track of sub-array starting index and end index. And whenever the current sum is reinitialized to zero we can update the start index to the current iterating index to get another sub-array of greater sum if possible.
def kadane(arr, n):
curr_sum = 0
max_sum = -1
track, start, end = 0,0,0
for i in range(n):
curr_sum = curr_sum + arr[i]
if curr_sum > max_sum:
max_sum = curr_sum
#save the sub-array start and end
start = track
end = i
if curr_sum < 0:
curr_sum = 0
track = i
#to print sub-array
print(arr[start:end+1])
return max_sum
arr = [1, 2, 7, -4, 3, 2, -10, 9, 1]
n = len(arr)
print(kadane(arr, n))
3) Dutch National Flag Algorithm
This is one of the interesting algorithms which is specially made to deal with only three different types of values in an array. Especially the algorithm is used to solve the problem like sorting an array of 0, 1, and 2. It is also used to implement the quick sort algorithm that I will demonstrate in the next blog. So let us understand the Algorithm using the same problem statement.
Different Approaches ~ One approach is you will use different sorting algorithms to perform simple array sorting that costs O(n*log n) time. Another approach is you use a two-pass algorithm in which you tend to count the occurrence of respective 0, 1, and 2 and in the second iteration you update the array so this makes the solution in O(N) time but we are still not able to solve in Linear time So here comes Dutch National Flag Algorithm to help us.
Dutch Algorithm Approach ~ It is a three-way partitioning algorithm that allows you to sort arrays with 0, 1, and 2 in constant space. Now what it says is to maintain the three indices as low = 0, mid = 0, high = N-1, where N is the size of an array. Now, what does this variable denote?
- The range from 0 to low in the array contains all 0's.
- The range from low to mid contains all 1s.
- The range from mid to high denotes the range containing any of 0s, 1s, 2s.
- The range from high to N-1 denotes a range containing 2s.
Now in a single array traversal till mid <= high how we will find all this range is using the below steps.
- If Arr[mid] == 0, then swap mid and low values and increase mid, and low by 1.
- If Arr[mid] == 1, then simply increase the mid by 1
- If Arr[mid] == 2, then swap high and mid pointer, and increase mid by 1, and decrease high by 1.
The complete implementation of the Algorithm is shown below. I will request you to dry-run the code for more clearance of the algorithm.
def DNF(arr, n):
low = 0
mid = 0
high = n-1
while mid <= high:
if arr[mid] == 0:
#swap mid and low index elements
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
mid += 1
elif arr[mid] == 2:
#swap high and mid
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
arr = [0, 1, 2, 2, 1, 0]
n = len(arr)
DNF(arr, n)
print(arr)
4) Searching Algorithms
We know that there are only two types of searching techniques in an array is Linear search and Binary Search. I think it's not required to put more light on searching algorithms but in short, the intuition of the algorithm is described below so please give it a read to clarify the points if anything is missing.
Linear Search ~ A simple search algorithm in a linear time to search any specific element in an array using a single traversal in an array that takes 0(N) time.
def Linear_Search(arr, n, target):
for i in range(n):
if arr[i] == target:
return i
return -1
Binary Search ~ Search is a sorted array by repeatedly dividing the array into two halves and searching for elements in any one of the halves. This reduces the time and allows to search any element in sorted array in O(log N) time. First, we divide the array into 2 halves by finding the middle index(N/2) and check the value at mid is equal to the search element or not, If yes then we have solved it in 0(1) time. If not then we check that the search element is greater than mid or smaller. If smaller then it will present in I first half so we perform this recursively in the first half Otherwise perform the same step in the second half.
def Binary_Search(arr, n, target):
low = 0
high = n-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid+1
else:
high = mid-1
return -1
5) Sorting Algorithms
Sorting means arranging the array elements in specific order whether it's ascending or descending. There are many arrays sorting algorithms like the Bubble sort, Insertion sort, selection sort, merge sort, quick sort, count sort, etc. In this tutorial, I will not cover the intuition behind any sorting algorithm because I hope that you are aware of at least 2 sorting algorithms. And If you want the article to understand the intuition behind the working of all sorting algorithms then please comment it down so soon I will publish an article on it. If not then the complete web is full of explaining this algorithm.
End Notes
Thank You! If you have followed this tutor till here then It's extremely honored to announce that now you are ready to deal with questions based on an array. So from our next tutorial, we will pick some random questions on Array based on these algorithms and try to solve them that will provide you complete guidance of how to approach and choose a best-fit algorithm to deal with different problem statements.