Category Archives: Arrays

Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s?

For example consider the array

A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the sub-array A[0:4]

This problem can be solved using sliding window algorithm. Take two indexes front and back which defines a window. We keep expanding the window by incrementing the back index as long as the window contains less than or equal to K zeros. That means, at any time, the window contains at most K 0’s. If it exceeds K, we increment the front index to reduce the number of zeros to K. Continue this procedure until the back index reaches the end of the array. We also keep track of the largest window during this process.

This algorithm takes O(n) time.

Here is the C++ code.

Problem Source: SPOJ REPROAD

Maximum elements of array

Given an array A of size N, We want to perform several iterations as described below.

Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right
Similarly move right, and fill each element which is one greater than it’s left.

For example consider an array of length 5, and we choose the index 3, the array would be

A = [2, 1, 0, 1, 2]

If we perform several iterations by choosing different indexes each time,
we have to output the maximum number, each element can get during all the iterations.

Consider that we repeat the procedure for the above array with Index 2
A = [1, 0, 1, 2, 3]

So after two iterations at indexes 2, and 3, maximum elements would be
MAX_A = [2, 1, 1, 2, 3]

To find MAX_A, at first, it looks like we need to repeat the procedure m times for m indexes,
which leads to O(m*n) complexity solution.

What will be the maximum number an element can get? N-1
How? Lets consider the same array as above, choose index 1, the array would be
A = [0, 1, 2, 3, 4]
Choose index 5, the array would be
A = [4, 3, 2, 1, 0]

So it is enough to perform the iteration with the left most and right most indexes,
the maximum element at each index i would be max( abs(i-left), abs(i-right))

So the time complexity will be O(n).

Here is the C++ code for the same.

Problem Source: The Army – Codechef

Partial sum queries

Given an array of numbers, we need to answer many queries of the form Sum(A[i]...A[j]),

For example, let the array be [15, 6, 1, 12, 7, 4, 10]

Sum(A[1:3]) = 15+6+1 = 22
Sum(A[4:6]) = 12+7+4 = 23
...

The simplest solution is to iterate through the elements from i to j and return the sum.
However this will be good enough if we have a small number of queries. What if we need to run many queries?
In worst case this is takes O(n2) time.

How can we reduce the time complexity?
If we pre-process the array by calculating the prefix array, we can answer each query in O(1) time.

For the above example calculate the prefix array by using the formula Prefix[i] = Prefix[i-1]+A[i]

Prefix = [15, 21, 22, 34, 41, 45, 55]

Now the partial sums can be calculated as follows

Sum(A[i:j]) = Prefix[j] - Prefix[i-1] if i > 1
= Prefix[j] if i=1

Here is the Java function which implements the above

long partialSum(int []prefixArr, int start, int end) {
long sum = arr[end];
if( start > 0)
sum -= arr[start-1];
return sum;
}

Searching for an element in array of adjacent numbers

Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number?

For example consider the array {1, 2, 1, 2, 3, 2, 3, 4, 5, 6}, and we want to search for the number 5.

The simplest solution is to check if the number is present or not using linear search. This algorithm takes O(n) time in the worst case.
But we are not utilizing the fact that the adjacent numbers differ by 1.

How do we utilize this property to improve the performance?

Let us assume we are searching for a number x+3 in an array.
Let us start with a number x at index 0. Here are the some of the possible patterns of numbers that the array can have

x, x+1, x+2, x+3, ...
x, x+1, x, x+1, ...
x, x-1, x, x+1, ...
x, x-1, x-2, x-1, ...
x, x+1, x+2, x+1, ...
etc...

We can safely jump to index 3 and check if the number is present. Why? Because in any pattern there is no chance of having x+3 before the index 3.
If the number is present, that is fine. Otherwise repeat the same procedure until we find the element or reach the end of the array.

The time complexity of the above procedure is still O(n), because in the worst case, we make n/2 jumps. But this is an improvement over the linear search (n comparisons in the worst case).

Example, search for number 6 in the array {4, 5, 4, 5, 4, 5, 4, 5, 4, 5}, we have to make 5 jumps to conclude that 6 is not present.

Here is the C++ implementation of the same.

Check if array can be divided into two parts with same XOR

Given an array of numbers, how do we check if it can be divided into two parts such that XOR values of both are same.

For example consider an array A = [1, 2, 3], it can be divided into [1, 2], and [3] because 0001 ^ 0010 = 0011

Similarly, [8, 3, 12, 7], can be divided into [8,7] and [3, 12] as 1000 ^ 0111 = 0011 ^ 1100 = 1111

This is a tricky question, where you need not actually try to divide the numbers into two sets. If any two parts of the array have the same XOR value, the XOR of all the elements will be Zero.

So we just need to check if the XOR value of all the elements is zero or not.

Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one.
How do you find the different number?

For example consider the array [1, 2, 3, 5, 9], 2 is the different number.
Similarly in the array [10, 6, 7, 24, 36], 7 is the different number.

This problem was originally appeared on Codeforces.

This is a simple implementation problem, which can be solved in one iteration.
When we are reading numbers, just keep track of the following information.

  • first even index
  • first odd index
  • even number count

At the end, check if the even number count is 1, If it is, then print first even index, otherwise print first odd index.
Here is the C++ code for this.

Maximum increasing sub array

Given an array of numbers, how to find the maximum length of increasing (non-decreasing) continuous sub-sequence?

For example consider the array [7, 9, 1, 3, 5, 8, 2], the maximum length is 4. Similarly for [23, 10, 18, 18, 6], it is 3.

This is a straight forward implementation problem (appeared on Codeforces). Following is an implementation of O(n) algorithm.

How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple. 
  • Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
  • Do the following until we reach the end of any sequence.
  • If both the elements are same, increment both indices.
  • Otherwise increment j only.

At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.

Finding the pivot element

Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it.

For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.

The array [6, 9, 1, 2, 4] does not contain any pivot element.

Simple brute force solution:

For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it’s index, otherwise we return -1.
But this solution takes O(n2) time.

Is there any better approach? Can we do it in O(n) time probably using extra space?

Yes, it can be done using two extra arrays.
  • One array stores the maximum element seen so far from the left.
  • Second array stores minimum element seen so far from the right

For example for the array [6, 9, 1, 2, 4]
Prefix maximum: [6, 9, 9, 9, 9]
Suffix minimum: [1, 1, 1, 2, 4] 

We first calculate the above two arrays. In the next iteration, For each element in the array, we check if the maximum element in the left is lesser, and the minimum element in the right is greater than it. If this condition is satisfied we are done. Since checking for maximum element in the left and minimum element in the right takes constant time (O(1)), the overall time complexity of this solution is O(n) and space complexity is O(1).

Below is the C++ implementation of the above. 

Duplicate elements in array at given distance

Given an array of numbers A, which might contain duplicate elements, 

How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k?

Look at the following examples.
1. A = [9, 5, 6, 9, 3, 0, 1], K =3
The answer is “Yes” because 9 is present at index 0, and 3

2. A = [10, 0, 10, 20, 30], K = 1
The answer is “No” because there are no duplicate elements at a distance less than or equal to 1

A simple and straight forward algorithm is to have two loops, the outer loop fixing one element, and the inner loop checks if that element exists within a distance of K. This algorithm runs in O(n2) in worst case.

Let us look at an efficient algorithm using the map data structure. The map stores the element as the key and it’s most recent index as it’s value. Here are the steps.

  • For each element in the array
    • Store the element and it’s index in the map if does not exist already.
    • If already exists, 
      • Check if the difference between the recent index and current index is less than K. 
      • If so return true.
      • Otherwise update the map with recent index

This algorithm runs in O(n log n) time, and take O(n) extra space for the map. Here is the C++ code given below. For the Python implementation checkout this link. For Java implementation check this link.