Top Array Coding Problems for technical interviews and Competitive Programming

Hello and welcome to the amazing data structure series of preparing for technical interviews, and competitive programming. Previous to this blog we have already studied some most popular array algorithms that you will encounter in 90 percent of array problems. In this article, we will pick some most asked coding problems where we will try to apply these algorithms in a smart way to solve the problem in a better and more optimized way.

Table of Contents

1. Find Product of Array except for self
2. Flip Bits to find Maximum count of Ones in array
3. Maximum subarray sum after K concatenation problem
4. Count Smaller or Equal Elements in an Array
5. All Pairs that sum equal to the target
6. Find the Longest consecutive subsequence in an array
7. Print the Array After K Number of operations
8. End Notes

Find Product of Array except for self

Given an array of N integers and task is to return an array of products such that product[I] is equal to the product of all the elements in the array except product[i]. It is a simple question that you can think of using a prefix-sum algorithm that we have studied in the previous blog.

Example - Let's understand the sample input and sample output. The first line contains several test cases. The first line of each test case defines N representing the size of the array and the second line contains space-separated elements of the array.

Approach to find Product array 

In the prefix sum algorithm, we create an array where prefix[I] represents the sum of all elements present before it. And same is the suffix sum algorithm where sufix[I] represents the sum of all elements present after it. So to solve this problem we will require both techniques because as we can see in the above example that we need to find the product of all the elements except the current element means the element which is present before and after the current element. So let's see the step-by-step algorithmic approach to solve this problem.

1. First, we will create a product array of N length where all the elements are initialized as 1.
2. Now To create a prefix product array we will use a single loop where the first element is as it is as one and then using one temporary variable we multiply each element and store it in the next position.
3. After prefix product, we apply another loop for suffix product in which the last element should not be changed so it is multiplied by one and coming backward we will multiply each element with array element and store it.
4. The resultant product array we have is our product array.

Now try building this without referencing the below code snippet and check using the below snippet for more clearance.

def getProductArrayExceptSelf(arr, n):
    #create product array of 1
    prod = [1 for i in range(n)]
    temp = 1
    
    #create a prefix prod array
    for i in range(n):
        prod[i] = temp #first ele has no prefix
        temp = temp * arr[i]
        
    temp = 1
    #create a suffix prod array
    for i in range(n-1, -1, -1):
        prod[i] = prod[i] * temp
        temp = temp * arr[i]
        
    return prod
    
t = int(input())
while t > 0:
    n = int(input())
    arr = list(map(int, input().split()))
    ans = getProductArrayExceptSelf(arr, n)
    print(ans)
    t = t-1

2) Flip Bits of an array to maximize the count of One

Given an array of integers of size N containing only zero and one. Your task is to find the total number of ones that can be obtained by flipping a sub-array at most once in such a way that the sub-set you choose and after flipping(0 to 1 and 1 to 0) the count of one is maximum in an array and return the total count of one.

Example ~ As usual, the first line is several test cases. and for each test case first, we have a size of the array and then array elements.

Explanation ~ Read the below snippet for sub-array clarifications.

Approach to deal with Flip Bits problem 

We have discussed in the previous blog that when we have to find a sub-array in an array with a maximum count, sum, product, etc then first think of Kadane's Algorithm that how we can apply it to solve a particular problem. So using the Kadane algorithm we can find the maximum number of zero that can be converted to one safely and add the initial count of one in an array and a resultant total is a maximum number of one in an array that can be obtained.

1. First store the initial count of one in a variable.
2. Iterate over an array and keep track of two variables as current sum and maximum sum. If the array element is zero then increase the current sum by one else decrease by one. 
3. Check if the current sum is greater than the maximum sum. If yes then store the maximum sum as a current sum. If the current sum is negative then reinitialize to zero for any new sub-array.
4. Add total count of initial ones and maximum sum and this is the final result.

I request you to dry run the algorithm and code that will make the complete approach crystal clear to you and open the door of visualization where you can think of more solutions. So please try to think about the approach and how you can implement it differently.

def flipBits(arr, n):
    #count number of ones in array
    tot_ones = arr.count(1)
    max_sum = 0
    curr_sum = 0
    #Kadane's Algorithm
    for i in range(n):
        if arr[i] == 0:
            curr_sum = curr_sum + 1
        else:
            curr_sum = curr_sum - 1
            
        if max_sum < curr_sum:
            max_sum = curr_sum
            
        if curr_sum < 0:
            curr_sum = 0
            
    #add max_sum and total ones to get result
    return tot_ones + max_sum
    
arr = [1,0,0,1,0]
n = len(arr)
print(flipBits(arr, n))

If someone asks to return the sub-array then from Kadane's algorithm you can do so by little modification in the above code that we have studied in the previous blog. So let's head over to the next question.

3) Maximum Subarray Sum after K Concatenation

Given an array of N integers(containing both positive, and negative elements). You are also given a positive integer K. Now form an array of size N*K by concatenating array K times and your task is to find the maximum sub-array sum that can be obtained from a concatenated array.

Sample Inputs and Output -

1. The first line contains a number of test cases
2. The first line of each test case contains N and K
3. Second-line contains N space-Separated array elements.
4. Output the maximum sum you can obtain by concatenating array K times.

How would you approach the solution?

You must have noticed till that problem is of the Kadane algorithm. And to approach this most of you will follow the iterative approach of the Kadane algorithm in two different ways.

👉 The first is a very basic Naive approach. You will form a concatenated array of N*K size which is single line code in Python. Then you will simply apply the Kadane algorithm to find the maximum sub-array sum. Space and time complexity, in this case, is O(N*K)

👉 Second maybe like Some will think a bit on the naive approach and instead of forming a new array simply, they will run the loop till N*K times in the Kadene algorithm to find the maximum Sum by adding Array[i%k]. So space Complexity is constant but time complexity is the same.

def maxSubSumKConcat(arr, n, k):
    maxSum = -1e9
    curSum = 0
    #Kadane algorithm
    for i in range(n*k):
        curSum += arr[i % n]
        maxSum = max(maxSum, curSum)

        if curSum < 0:
            curSum = 0
    return maxSum
    
t = int(input())
while t > 0:
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    print(maxSubSumKConcat(arr, n, k))
    t = t-1

👉 In rare cases, people do implement this because I have implemented this approach many times. Iterate in an array and maintain two-pointer like positive element count and negative elements count. Check that if both the pointer is greater than zero then use Kadane in N*K times. If the array contains all positive elements then simply return a sum of the array multiplied by K. If all elements are negative then the maximum element is only the maximum sum.

def maxSubSumKConcat(arr, n, k):
    pc = 0
    nc = 0
    for i in arr:
        if i >= 0:
            pc += 1
        if i < 0:
            nc += 1
        if pc > 0 and nc > 0:
            ans = getMaxSum(arr, n, k) #Kadane Algorithm
            return ans
            
    if pc == n:
        return sum(arr)*k
    if nc == n:
        return max(arr)

If you have at least thought over any of the above approaches then congratulations that you are practicing, enforcing your mind to think, and taking your learning forward. But we know that the above approach will not clear all the test cases and somewhere will be stuck in time complexity so let's discuss more optimized cases with Kadane's Algorithm.  

Optimize Kadane Algorithm for different cases.

We can break the problem into different cases, a little bit the same as we did in the third approach. Understanding algorithm is very important but how to apply any algorithm smartly is also important to learn. So all matters are your observation and visualization skills that you can come to know after reading the below approach.

1. Check if K is 1 then simply apply Kadane's algorithm.
2. Else find the sum of array elements. Check that sum is negative then find the maximum sum subarray for K=2. because sub-array cannot contain more than these elements and start decreasing the sum so run Kadane's for K =2 and return an answer.
3. If the sum is positive then find the maximum subarray sum for K=2 and return subarray sum plus k-2 multiply by array sum because being array sum as positive will increase the subarray sum.

Below is the implementation of this algorithm that will help clear all the test cases.

def kadane(arr, n, k):
    maxSum = -1e9
    curSum = 0
    for i in range(n*k):
        curSum += arr[i % n]
        maxSum = max(maxSum, curSum)

        if curSum < 0:
            curSum = 0
    return maxSum

def maxSubSumKConcat(arr, n, k):
    maxSubSum = -1
    if k == 1:
        maxSubSum = kadane(arr, n, k)
        return maxSubSum

    arrSum = sum(arr)

    if arrSum <= 0:
        # Finding the maximum subarray sum for k = 2 
        maxSubSum = kadane(arr, n, 2)
    else:
        # Finding the maximum subarray sum for k = 2
        maxSubSum = kadane(arr, n, 2)
        maxSubSum += (k - 2) * arrSum

    return maxSubSum

4) Count Smaller or Equal elements in an array

Given two arrays A and B of N and M size. Your task is to find how many elements in array B are small or equal to each and every element of array A and return the new array of the small or equal count.

Sample Input and Output

We have several test cases. First-line has N(number of elements in A) followed by the next line with array A elements. The third line contains B followed by the next line with elements of array B.

Naive Approach

First, everyone tries are Brute-force approach and it is good that while learning at least you are trying something. So you will apply two loops to iterate both arrays and for each element count small or equal and save the count in the newly created array.

def countSmallerOrEqual(a, b, n, m):
    result = []
    for i in range(n):
        cnt = 0
        for j in range(m):
            if b[j] <= a[i]:
                cnt += 1
        
        result.append(cnt)
    return result

Sorting Approach

It is good that if you have determined that problem lies under the sorting category or can be solved in less time using sorting then congratulations. So we will sort the array B and after that in a single iteration in array A we can find a count of small or equal elements. For every element of A, we check that if the last element is small or equal then the size of B is the required count. Else in a sorted array, we will find the correct index to place the element of array A which will be the required count. You can also find the index manually or can also use the python in-built Bisect module to do so. The bisect module has three functions defined below.

• The first is plain bisect which gives you the element index to insert in sorted.
• The second is the bisect left function that gives you an index of elements to insert in sorted order from left when duplicate elements are there in an array.
• The third is bisect right which finds a correct index to insert an element from right in sorted order. And this is a function we require in this algorithm.

Let's implement the algorithm in python.

import bisect

def countSmallerOrEqual(a, b, n, m):
    result = []
    b.sort()  #sort Array B
    
    for i in range(n):
        if a[i] >= b[m-1]:
            result.append(m)
            
        else:
            #in array b find index of a[i] element to insert from right
            idx = bisect.bisect_right(b, a[i])
            result.append(idx)
    
    return result

Now using this problem you can solve many other problems like finding the best index to insert elements in sorted order, finding the first and last position of elements when we have duplicate elements, etc.

5) Find Pairs whose sum is equal to K (Pair Sum Problem)

This is one simple question that you can implement on your own after solving these many questions but this question is very important from the interview point of view. So Given an array of N integers and a number K., Your task is to find all the pairs which sum to K.

Sample Input and Output

We are given N(number of elements in the array) and K(target sum). In the next line given space-separated array elements and return all the pairs that sum to a target sum.

Approach to solve Pair sum problem 

👉 First is the Naive approach that most of you have implemented and must implement is the brute-force approach where you use two loops and for each array, the element finds another element in an array that sums up to equal to K.

def pairSum(arr, k):
    res = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if((arr[i] + arr[j]) == k):
                pair = [arr[i], arr[j]]
                res.append(pair)
    
    return res

👉 The second is an amazing approach where we use sorting. First, sort the array, and now using single loop iteration find a difference between target sum and current array element and check that if the difference is present in remaining array element then count the occurrence of a difference in that and form so many pair.

def pairSum(arr, k):
    arr.sort()
    res = []
    for i in range(len(arr)):
        diff = k - arr[i]
        if diff in arr[i+1:]:
            cnt = arr[i+1:].count(diff)
            while cnt != 0:
                res.append([arr[i], diff])
                cnt -= 1
    return res

6) Longest Consecutive Subsequence

Given an unsorted array of N integers. Your task is to find the longest length of the consecutive sequences.  The consecutive sequence is in form of num, num+1, num+2, and so on.

Sample Input and Outputs

A first line is several test cases and for each test case, you are given the length of the array followed by array elements in the next line.

How to Approach the consecutive sequence problem

I hope that you must be thinking and trying to apply any algorithm we have studied. So we can approach the problem using sorting and Kadane both in a combined manner. 

1. first, we will sort an array.
2. Maintain the variable start, end, sub-array supporting temporary variable, maximum sub-array length. 
3. In the Kadane algorithm iterate from 1 to array length and find a difference between the current element, and the previous element.
4. If the difference is equal to 0 then simply increase the count. It is a count of elements in a sub-array(subsequence).
5. If the difference is equal to 1 then update the subsequence and check that if the maximum subsequence length is less than current then update length.
6. If the difference is greater then update the starting subsequence tracking variable.

Now let us build the algorithm using python.

def lengthOfLongestConsecutiveSequence(arr, n):
    arr.sort()
    mxl = 0 #maimum length
    start = 0
    end = 1
    s = 0 #track variable
    cnt = 0 #count of element in subsequence
    
    for i in range(1, n):
        mxend = arr[i-1]  #prev ele
        if arr[i]-mxend == 0:
            cnt += 1
        elif arr[i]-mxend == 1:
            start = s
            end = i-cnt
            #update the subsequence length
            if (end - start) > mxl:
                mxl = (end-start)
        else:
            s = i
            cnt = 0
    
    return mxl+1 #because 0-based indexing 1 ele left    

7) Print the array After K operations

Given an array of N integers and also an integer K. Your task is to return a modified array after the K operation in such a way that in each operation change each element of an array with the difference between a maximum element and current element.

Note ~

• Array follows zero-based indexing.
• After each operation, the next operation will be performed on an updated array.

Sample Input and Output

The first line contains a number of the test case. The first line of each test case contains N and K respectively. The second line of the test case contains N number of array elements.

How would you approach the problem?

Everyone who is following the article from start should be able to build a brute-force method to solve the problem. Run a loop K times and each time find a maximum element from an array and then iterate in an array and update each array element by subtracting it from a maximum element.

def printArrayAfterKOperations(arr, N, k):
   while k > 0:
    mx = max(arr)
    for i in range(N):
        arr[i] = mx - arr[i]
    k = k-1
    
   return arr

Optimized Approach

Observation skills matter a lot, and that's why I say try to solve some examples with pen and paper to get an idea of how to approach a problem. Initially, we are subtracting each element of the array from the maximum element which means that after the single operation there will be at least one zero value in an array. After the first array updation values of the array only change their position which means the array becomes stagnant. Let's understand this with an example.

1. If K is zero then an original array is only the output.
2. Now for example take arr = [20, 15, 10, 5] and K = 4
• At first step, K=1 and array is reduced to {0, 5, 10, 15}. Every element is replaced by 20-array[I].
• After first step, when k=2 array alternatively changes to {15, 10, 5, 0}. Maximum is 15
• Similarly for K=3, array becomes {0, 5, 10, 15}.
• At last when k=4, again array becomes {15, 10, 5, 0}

Now, What was your observation from the above example? We can observe that the array at the third step is the same as it was after the first step and the array after the fourth step is the same as the second step. So Instead of using the Brute-force method K times, we can simply update the array one time by checking K is even of Odd.

• If K is Odd then perform maximum - arrar[I] only one time.
• If K is Even then performing arrar[I] - minimum element will generate a resultant array.

Now let us build the algorithm. You can implement the algorithm on your own without using the below snippet.

def printArrayAfterKOperations(arr, N, k):
    min_ele = min(arr)
    max_ele = max(arr)
    n = len(arr)
    if k != 0:
        if (k % 2 == 1):
            #replace every ele with max-arr[i]
            for i in range(n):
                arr[i] = max_ele - arr[i]
               
        else:
            #replace with arr[i] - min
            for i in range(n):
                arr[i] = arr[i] - min_ele
                
    return arr

End Notes

These were the topo and most popular six array coding problems that you should know because these will help you approach many different problems. There are some more questions that I wanted to add to this article but there will be more and the article length will be too long so, I will upload one more article that will contain other top-six problems. I hope that each and every problem is clear to you and I was able to make you understand the approach easily.

If you have any kind of query or doubts then please feel free to post them in the comment section below 👇, and you can also use the contact us form for any help.

Thank you for your time! 😊