Category Archives: Arrays

Longest sub array with zero sum

Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum?

For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements. 

The straight forward approach is to check the sum of all possible arrays and find out the maximum length sub array. This will run in O(n3) time.

Can we do better than this?

Yes, by using dynamic programming we can do that. Take an array which is of same size. We can find this in n iterations.
 

In the first iteration, we find the length of longest sub sequence with zero sum beginning with the first element.
 

In the second iteration, we find the length of longest sub sequence with zero sum beginning with second element and so on.

Let us calculate this array for the above example
 

Iteration 1:
Cumulative Sum = 5 5 4 7 5 9
Max Length     = 0 0 0 0 0 0

Iteration 2:
Cumulative Sum = _ 0 -1 2 0 4
Max Length     = 0 1  0 0 4 0

Iteration 3:
Cumulative Sum = _ _ -1 2 0 4
Max Length     = 0 1  0 0 4 0

and so on.

At the end of all this, maximum of this array contains the result.

Here is the C++ code.

Programming puzzle – calculating product array

Given an array of numbers A[1:N], we have to generate a product array P[1:N] such that P[i] contains the product A[1]*…A[i-1]*A[i+1]…A[N]

That means each entry in the product array should contain product off all the elements except the one at that particular index.

For example let us consider the array [4, 2, 10, 5], the output should be {100, 200, 40, 80}.

The restriction here is that we have to device an algorithm without using division operation. Had it been allowed, we would have simply calculated the product of all the elements and fill the product array by dividing this with the current element.

Here is the solution approach.

We do this using two iterations one forward and the other backward.

  • In the forward iteration, we fill the product array by filling each entry with product of all the elements before it.
  • In the backward iteration, we multiply each element with product of all the elements to the right of it.

Here is the C++ implementation for this. The time complexity is O(n).

Standing Ovation: Google codejam 2015 Qualification round problem

Every year Google conducts a competition called Codejam for programming enthusiasts. The qualification round for the year 2015 got finished yesterday. In this post, I am going to explain the solution approach for the first problem.

You can read the problem from this link. I will try to give the abridged problem statement below.

There are a group of N people in a stadium with their shyness levels represented by a String S of digits(0-9). The digit at each index represents the number of persons with shyness level equal to the index.

For example S[0] represents the number persons with shyness ‘0’.
S[1] represent the number of persons with shyness ‘1’ and so on.

Persons with shyness level ‘L’ will not standup and clap until ‘L’ other people standup and clap before them. For example, in order for a person with shyness level 3 to standup and clap, 3 other people must do that before him. 

Now the problem is to find whether the all the people in the given group gives a standing ovation on its own? or What is the minimum number of people to add to the group to ensure that they give a standing ovation.

Let us consider a couple of simple examples.

  1. [1, 1, 2]: There is one person with shyness level 0 who will clap first. After seeing him, the second person with shyness 1 will also clap. Then the last two people with shyness 2 will also clap. So there is no need to add any people to give a standing ovation.
  2. [1, 0, 1]: In this case, we need one person with shyness 0 or 1 to be added to the group because the last person will not standup until 2 other people clap.

A simple greedy approach will solve the problem. Here is the algorithm.

Start at the first person and count the number of people stood up before him. If this count is not enough for the current person to standup, count the difference needed.  Accordingly increment the people currently standing.

Here is the C++ implementation of the above approach. This runs in O(n) time.


Searching for an element in array with successive elements atmost 1 distance apart

Given an array of integers where each element has a difference of atmost 1 with it’s neighbors, we need to find the given element.

For example, consider the array [1, 2, 2, 1, 2, 3, 2, 1], and the element to be searched is 3, we need to return the index 5.

This is just an implementation problem with a trick. Here is the approach.

  • Start with first element, check if the current element matches, if so return it.
  • Otherwise increment the index by the absolute difference between current element and target element.
  • Repeat the above step until we find the element or reach the end of the array.
This algorithm runs in O(1) in best case. Example of the base cases
Searching for 10 in [1,2,3,4,5,6,7,8,9,10] or
Searching for 1 in [10,9,8,7,6,5,4,3,2,1]

Within One jump we reach the target element.

However this takes O(n) time in the worst case like the following
Searching for 2 in [1,1,1,1,1,1,1,1,2]

Here is the C++ implementation.

Maximum number of 1s in any row of a boolean matrix

Given a matrix consisting of only 0,1s, with each of it’s row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row.

For example consider the following matrix.

0 0 1 1
0 0 0 1
0 1 1 1
0 0 0 0

The maximum number of 1s in any row is three which appear in the third row.

The general approach is to find the number of 1s in each row and update the maximum.


There are two ways to find the number of 1s.
  • One simple approach is to linearly search for first 1 and find the count of 1s. This will take O(n) time in worst case. So the overall time complexity would be O(n2).
  • Another faster method is to search for first 1 using binary search since each row is sorted. This will take only O(log n) time and the overall complexity would be O(n log n).

Even more efficient approach can be as follows.

  • Start with the right most element in the first row, keep counting the number of 1s until we reach zero. 
  • Move to the next row and start checking the elements from previous column
    • If the element is zero, just move on to the next row
    • Otherwise count the ones until we reach zero or the first column
  • Repeat the above step for all the rows. At the end, we get the maximum number 1s.

This approach just runs in O(n+m) where n, m are the number of rows and columns respectively.

    Here is the C++ implementation of the above. I have used the lower_bound() method from the standard library to find the left most occurrence of a 1. Look at my previous post to understand how this method works.

    Finding the maximum element in a bitonic array

    Given an array in which the elements are increasing up to a point and then decreases (this is also called a bitonic array), how do we efficiently find the maximum element?

    For example, the input arrays can look like {1, 3, 5, 4, 2} ,  {11, 17, 25, 36, 24, 6}.

    Basically we need to find the point at which the elements start decreasing. It can be anywhere in the array.

    The obvious linear search for maximum takes O(n) time. But we can utilize the sorted property of two parts of the arrays to solve it in O(log n).

    Here is how the algorithm works.

    • Go to the middle element and check if it is greater than both the left and right elements. If it is, then we found the maximum element. 
      • Eg: {1, 3, 5, 4, 2}
    • If the left element is greater than the middle element, we can ignore the right half and search only in left half. 
      • Eg: {1, 5, 4, 3, 2}
    • If the right element is greater than the middle element, we can ignore the left half and search only in right half.
      • Eg: {1, 5, 7, 9, 3}

    We need to handle the cases where the middle element falls on the boundaries of the array. This happens when the entire array is sorted either in ascending order or descending order. Eg: {1, 2, 3, 4, 5} or {5, 4, 3, 2, 1}

    • If the right part is empty, and the middle element is greater than left element, we can eliminate the left part.
    • Similarly if the left part is empty, and the middle element is greater than right element, we can eliminate the right part.

    Test cases:

    1. {1, 3, 5, 4, 2}
    2. {1, 2, 3, 4, 5}
    3. {5, 4, 3, 2, 1}
    4. {1}
    5. {1, 2, 2, 4, 5, 3}
    6. {10, 20}

     Here is the iterative C++ implementation of the above algorithm.

    Minimum number of chages to make equal groups

    Given an array of numbers, how do we find the minimum number of changes(additions/subtractions) to the elements so that each number in the array is same or equal.

    For example given the array {1, 2, 3, 4}, the minimum number of changes are 3. i.e we can choose any of the four elements and make the other three elements equal to the chosen element.

    Similarly given the array {56, 29, 112, 29}, the minimum number of changes to make is 2. We can choose 29 as the common element and change the other two elements.

    This problem is from recently concluded Codechef contest. Click on this link to read the complete problem statement.

    The solution is evident from the second example. This is the problem of finding the number of occurrences of a most frequently appearing number (mode) and subtracting it from the total number of elements.

    There are at least two different approaches to implement the solution. 
    One is to sort the array (takes O(n log n) time) first and find the maximum frequency in O(n) time.
    The other is a map based approach to store the frequencies of elements while iterating through all the elements and find the maximum among them. This will take O(n) time bust consumes O(n) extra space.

    Below is the C++ implementation of the first strategy. Read my previous post for the implementation of map based method.

    Maximum length of subarray with non-zero elements

    Given an array of of size N, How do we find the longest sub-array with all non-zero elements?

    For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}.

    This problem is from Codechef. Follow this link to solve this problem in your own.

    The solution is simple. The array contains non zero segments of numbers separated by one or more zeros. While traversing the elements, use two variables current_len, and max_len to track the length of the current segment and maximum segment length seen so far.

    Here is the Python implementation of the above. This runs in O(n) time.

    Finding a sub list with least max-min difference – Codeforces puzzle

    This is a problem from Codeforces. Please follow this link to solve this problem on your own.

    The abridged problem statement is as follows.

    You are given an list of numbers, and sub-list size as input. The challenge is to find a sub-list such that the difference between the maximum and minimum numbers in that sub-list is minimized.

    For example consider the numbers {36, 6, 12, 42, 24, 50}, and we have to find a sub-list of size 4. By choosing {36, 42, 24, 50}, we can have a least difference of 26 i.e 50-24.

    The solution is to first sort the numbers in ascending order, and move a sliding window of sub-list size from begin to end while keeping track of the minimum difference between first and last numbers of the sub-list.

    Tracing with the above example, after sorting the list becomes {6, 12, 24, 36, 42, 50}
    We start with 6, 36, the difference is 30
    move on to 12, 42, the difference is 30
    move on to 24, 50, the difference is 26
    So the minimum difference is 26.

    This algorithm runs in O(n*log n) time because we have to sort the list. the actual algorithm takes O(n), linear time.

    Here is the C++ code for the same.

    Joining an array of numbers to form the biggest number

    Given an array numbers, we have to join them in such a way that it forms the biggest number.

    For example consider the simple three element array [10,3,2], they can be joined in following ways
    1032, 1023, 2103, 2310, 3102, 3210. Among these numbers 3210 is the biggest number.

    To solve this problem we definitely have to sort the given numbers using some criteria to form the biggest number. 
    Considering the above example, if we simply sort them in descending order, the array becomes [10,3,2] which does not form the biggest number.

    Similarly we can also sort numbers by comparing the numbers string comparison. This does not work in cases like [1,10]. Since “10” > “1” the array in sorted as [10,1], but 110 is the biggest number.

    We should think of a custom comparison function which guarantees us the biggest number when joined. Let us join the two numbers to be compared in two ways and compare them.

    Considering the above example, they become 110 (“1″+”10”), 101( “10”+”1″). Since 110 is higher we place 1 first in sorting order before 10.

    Here is the simple python implementation of the above algorithm. Also see my post on geeksforgeeks for C++ implementation of the same algorithm.