Median of two sorted arrays

Before we find the median of two sorted arrays, let’s understand what is the median?

Median is the middle value in a list of numbers.

For example,

Input:
A = [2,4,5,6,7,8,9].
Output:
6

To find the median, the input should be sorted. If it is not sorted, then first sort it and return the middle of that list. The question arises is what if the number of elements in the list is even? In that case, the median is the average of two middle elements.

Median of two sorted arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

median of two sorted arrays

Before going into the post, find a pen and paper and try to work out an example. And as I tell in our posts, come up with a method to solve this considering, you have all the time and resources to solve this problem. I mean think of most brute force solutions.

Let’s simplify the question first and then work it upwards. If question was to find the median of one sorted array, how would you solve it?
If array has odd number of elements in it, return A[mid], where mid = (start + end)/2; if array has even number of elements, return average of A[mid] + A[mid+1].
For example for array A = [1,5,9,12,15], median is 9.
Complexity of this operation is O(1).

Focus back on 2 sorted arrays. To find a median of 2 sorted arrays in no more simple and definitely not O(1) operation. For example,

A = [ 1,5,9,12,15] and B = [ 3,5,7,10,17], median is 8.

How about merging these two sorted arrays into one, the problem is reduced to find the median of one array.

Although to find median in a sorted array is O(1), merge step takes O(n) operations. Hence, overall complexity would be O(n).
Reuse the merge part of Merge sort algorithm to merge two sorted arrays.

Start from the beginning of two arrays and advance the pointer of the array whose current element is smaller than the current element of the other. This smaller element is put on to output array which is sorted merged array. Merge will use an additional space to store N elements (Note that N is here sum of the size of both sorted arrays). The best part of this method is that it does not consider if the size of the two arrays is the same or different.

This can be optimized, by counting number of elements n, in two arrays in advance. Then we need to merge only n/2 + 1 elements if n is even and n/2 if n is odd. This saves us O(n/2) space.

There is another optimization: do not store all n/2 or n/2 + 1 elements while merging, keep track of last two elements in sorted array, and count how many elements are sorted. When n/2 + 1 elements are sorted return average of last two elements if n is even, else return n/2 element as the median. With these optimizations, time complexity remains O(n), however, space complexity reduces to O(1).

Impementation with merge function

package com.company;

/**
 * Created by sangar on 18.4.18.
 */
public class Median {

    public static double findMedian(int[] A, int[] B){
        int[] temp = new int[A.length + B.length];

        int i = 0;
        int j = 0;
        int k = 0;
        int lenA = A.length;
        int lenB = B.length;

        while(i<lenA && j<lenB){
            if(A[i] <= B[j]){
                temp[k++] = A[i++];
            }else{
                temp[k++] = B[j++];
            }
        }
        while(i<lenA){
            temp[k++] = A[i++];
        }
        while(j<lenB){
            temp[k++] = B[j++];
        }

        int lenTemp = temp.length;

        if((lenTemp)%2 == 0){
            return ( temp[lenTemp/2-1] + temp[lenTemp/2] )/2.0;
        }
        return temp[lenTemp/2];
    }

    public static void main(String[] args){
        int[] a = {1,3,5,6,7,8,9,11};
        int[] b = {1,4,6,8,12,14,15,17};

        double median = findMedian(a,b);
        System.out.println("Median is " + median);
    }
}

Optimized version to median of 2 sorted arrays

package com.company;

/**
 * Created by sangar on 18.4.18.
 */
public class Median {

    public  static int findMedianOptimized(int[] A, int[] B){
        int i = 0;
        int j = 0;
        int k = 0;
        int lenA = A.length;
        int lenB = B.length;

        int mid = (lenA + lenB)/2;
        int midElement = -1;
        int midMinusOneElement = -1;

        while(i<lenA && j<lenB){
            if(A[i] <= B[j]){
                if(k == mid-1){
                    midMinusOneElement = A[i];
                }
                if(k == mid){
                    midElement = A[i];
                    break;
                }
                k++;
                i++;
            }else{
                if(k == mid-1){
                    midMinusOneElement = B[j];
                }
                if(k == mid){
                    midElement = B[j];
                    break;
                }
                k++;
                j++;
            }
        }
        while(i<lenA){
            if(k == mid-1){
                midMinusOneElement = A[i];
            }
            if(k == mid){
                midElement = A[i];
                break;
            }
            k++;
            i++;
        }
        while(j<lenB){
            if(k == mid-1){
                midMinusOneElement = B[j];
            }
            if(k == mid){
                midElement = B[j];
                break;
            }
            k++;
            j++;
        }

        if((lenA+lenB)%2 == 0){
            return (midElement + midMinusOneElement)/2;
        }
        return midElement;
    }

    public static void main(String[] args){
        int[] a = {1,3,5,6,7,8,9,11};
        int[] b = {1,4,6,8,12,14,15,17};

        double median = findMedianOptimized(a,b);
        System.out.println("Median is " + median);
    }
}

Binary search approach

One of the properties which lead us to think about binary search is that two arrays are sorted. Before going deep into how binary search algorithm can solve this problem, first find out mathematical conditions which should hold true for a median of two sorted arrays.

As explained above, median divides input into two equal parts, so first condition median index m satisfy is a[start..m] and a[m+1..end] are equal size. We have two arrays A and B, let’s split them into two. The first array A is of size m, and it can be split into m+1 ways at 0 to m.

If we split at i, len(Aleft) – iand len(Aright) = m-i.
When i=0, len(Aleft) = 0 and when i=m, len(Aright) = 0.

median of two sorted arrays

Similarly, for array B, we can split it into n+1 way, j being from 0 to n.

find median of sorted arrays

After splitting at specific indices i and j, how can we derive the condition for the median: left part of the array should be equal to the right part of the array?

If len(Aleft) + len(Bleft) == len(Aright) + len(Bleft) , it satisfies our condition. As we already know these values for split at i and j, equation becomes

i+j = m-i + n-j

median of two sorted array

But is this the only condition to satisfy for the median? As we know, the median is middle of the sorted list, we have to guarantee that all elements on the left array should be less than elements in the right array.

It is must that max of left part is less than min of right part. What is max of left part? It can be either A[i-1] or B[j-1]. What can be min of right part? It can be either A[i] or B[j].

We already know that, A[i-1] < A[i] and B[j-1] < B[j] as arrays A and B are sorted. All we need to check if A[i-1] <= B[j] and B[j-1] <= A[i], if index i and j satisfy this conditions, then median will be average of max of left part and min of right part if n+m is even and max(A[i-1], B[j-1]) if n+m is odd.

Let’s make an assumption that n>=m, then j = (n+m+1)/2 -i, it will always lead to j as a positive integer for possible values of i (o ~m) and avoid array out of bound errors and automatically makes the first condition true.

Now, problem reduces to find index i such that A[i-1] <= B[j] and B[j-1]<=A[i] is true.

This is where binary search comes into the picture. We can start as mid of array A, j = (n+m+1)/2-i, and see if this i satisfies the condition. There can be three possible outcomes for the condition.
1. A[i-1] <= B[j] and B[j-1]<=A[i] is true, we return the index i.
2. If B[j-1] > A[i], in this case, A[i] is too small. How can we increase it? by moving towards right. If i is increased, value A[i] is bound to increase, and also it will decrease j. In this case, B[j-1] will decrease and A[i] will increase which will make B[j-1]<=A[i] true. So, limit search space for i to mid+1 to mand go to step 1.
3. A[i-1] > B[j], means A[i-1] is too big. And we must decrease i to get A[i-1]<=B[j]. Limit search space for i to 0 mid-1 and go to step 1

Let’s take an example and see how this works. Out initial two arrays as follows.

median of two sorted arrays leetcode

The index i is mid of array A and corresponding j will as shown

median of two sorted arrays leetcode solution

Since condition B[j-1] <= A[i] is not met, we discard left of A and right of B and find new i and j based on remaining array elements.

get median of two sorted arrays

Finally, our condition that A[i-1]<= B[j] and B[j-1] <=A[i] is satisfied, find the max of left and min of right and based on even or odd length of two arrays, return average of the max of left and min of right or return a max of left.

This algorithm has dangerous implementation caveat, what if i or j is 0, in that case, i-1 and j-1 will be invalid indices. When can j be zero, when i==m. Till i<m, no need to worry about j being zero. So be sure to check i<m and i>0, when we are checking j-1 and i-1 respectively.

Implementation

package com.company;

/**
 * Created by sangar on 18.4.18.
 */
public class Median {

    public static double findMedianWithBinarySearch(int[] A, int[] B){

        int[] temp;

        int lenA = A.length;
        int lenB = B.length;

        /*We want array A to be always smaller than B
          so that j is always greater than zero
         */
        if(lenA > lenB){
            temp = A;
            A = B;
            B = temp;
        }

        int iMin = 0;
        int iMax = A.length;
        int midLength =  ( A.length + B.length + 1 )/2;

        int i = 0;
        int j = 0;

        while (iMin <= iMax) {
            i = (iMin + iMax) / 2;
            j = midLength - i;
            if (i < A.length && B[j - 1] > A[i]) {
                // i is too small, must increase it
                iMin = i + 1;
            } else if (i > 0 && A[i - 1] > B[j]) {
                // i is too big, must decrease it
                iMax = i - 1;
            } else {
                // i is perfect
                int maxLeft = 0;
                //If there we are at the first element on array A
                if (i == 0) maxLeft = B[j - 1];
                //If we are at te first element of array B
                else if (j == 0) maxLeft = A[i - 1];
                //We are in middle somewhere, we have to find max
                else maxLeft = Integer.max(A[i - 1], B[j - 1]);

                //If length of two arrays is odd, return max of left
                if ((A.length + B.length) % 2 == 1)
                    return maxLeft;

                int minRight = 0;
                if (i == A.length) minRight = B[j];
                else if (j == B.length) minRight = A[i];
                else minRight = Integer.min(A[i], B[j]);

                return (maxLeft + minRight) / 2.0;
            }
        }
        return -1;
    }

    public static void main(String[] args){
        int[] a = {1,3,5,6,7,8,9,11};
        int[] b = {1,4,6,8,12,14,15,17};

        double median = findMedian(a,b);
        System.out.println("Median is " + median);
    }
}

The complexity of this algorithm to find the median of two sorted arrays is log(max(m,n)) where m and n are the size of two arrays.

Please share your views and suggestions.

Leaders in array

Leaders in array

In last post, we discussed inversions in array. One more problem on similar lines, given an array of integers, find all leaders in array. First of all, let’s understand what is a leader. Leader is an element in array which is greater than all element on right side of it. For example:
In array below element 8, 5 and 4 are leaders. Note that element at index 6 is leader by not at index 1.

leaders in array

Another example, in this there are only two leaders which is 10 and 9.

inversions in array

Clarifying question which becomes evident in example is that if last element is considered as leader? Based on answer from interviewer, function should print or not last element.

Leaders in array : thought process

What is brute force approach? Scan through all elements in array one by one and check if there is any greater element on right side. If there is no such element, number is leader in array.

package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 7.4.18.
 */
public class Leaders {

    public static ArrayList<Integer> findLeaders(int[] a){
        ArrayList<Integer> leaders = new ArrayList<>();

        for(int i=0; i<a.length; i++){
            int j = 0;
            for(j=i+1; j<a.length; j++){
                if(a[i] < a[j]){
                    break;
                }
            }
            if(j==a.length) leaders.add(a[i]);
        }

        return  leaders;

    }

    public static void main(String[] args) {
        int a[] = new int[]{90, 20, 30, 40, 50};
        ArrayList<Integer> inversions = findLeadersWithoutExtraSpace(a);
        System.out.print("Leaders : " + inversions);
    }
}

Complexity of brute force solution to find leaders in array is O(n2).

Let’s go to basics of question: All elements on right side of an element should be less than it for that element to be leader. Starting from index 0, we can assume that A[0] is leader and move forward. Remove A[0] if A[1] > A[0] as A[0] is not leader anymore. Now, if A[2] > A[1], then A[1] cannot be leader.
What if A[3] < A[2], then A[2] may still be leader and A[3] may also be.
What if A[4] > A[3], then A[3] cannot be leader. Can A[2] be leader? Depends if A[4] is less or more than A[2]. For each element, we are going back to all previous candidate leaders in reverse way and drop all candidates which are less than current element. Does it ring bell?Well, data structure which supports this kind of operation Last In First Out, is stack.
Stack supports two operations : push and pop. Question is when to push and pop and elements from stack for our problem.

Push element if it less than top of stack. If top of stack is less than current element, pop elements from stack till an element which is greater than current element. When entire array is scanned, stack will contain all leaders.

    • Start with empty stack. Push first element of array on to it.
    • For each element in array
    • Till current element is greater than top, pop element.
    • Push current element on to stack.
    •  At the end of processing, stack will contain all leaders.

Leaders in array : Implementation using stack

package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 7.4.18.
 */
public class Leaders {

    public static ArrayList<Integer> findLeadersUsingStack(int[] a){
        ArrayList<Integer> leaders =new ArrayList<>();

        Stack<Integer> s = new Stack();
        s.push(a[0]);

        for(int i=1; i<a.length; i++){
            while(s.peek() < a[i]){
                s.pop();
            }
            s.push(a[i]);
        }

        while (!s.empty()){
            leaders.add(s.pop());
        }
        return leaders;
    }
    public static void main(String[] args) {
        int a[] = new int[]{90, 20, 30, 40, 50};
        ArrayList<Integer> inversions = findLeadersWithoutExtraSpace(a);
        System.out.print("Leaders : " + inversions);
    }
}

Complexity of algorithm using stack to find leaders in array is O(n) with extra O(n) space complexity.

Scanning array in reverse
How can we avoid the additional space used by stack? When we are scanning forward, there are chances that some element going forward will be current candidate leader. That is why we keep track of all candidate leaders. How about scanning array from end, in reverse order. Start with last index and keep track of maximum we saw till current index. Check if element at current index is greater than current max, save it as leader and change current max to current element.

Algorithm to find leaders without extra space
  • Set current max as last element of array.
  • For i = n-1 to 0 index of array
    • if a[i] greater than current max
    • add a[i] to leaders.
    • Change current max to a[i]

Leaders in array implementation without extra space

package com.company;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by sangar on 7.4.18.
 */
public class Leaders {

    public  static ArrayList<Integer> findLeadersWithoutExtraSpace(int[] a){
        ArrayList<Integer> leaders =new ArrayList<>();

        int currentMax = Integer.MIN_VALUE;
        for(int i=a.length-1; i>=0; i--){
            if(a[i] > currentMax ){
                currentMax = a[i];
                leaders.add(a[i]);
            }
        }

        return leaders;
    }
    public static void main(String[] args) {
        int a[] = new int[]{90, 20, 30, 40, 50};
        ArrayList<Integer> inversions = findLeadersWithoutExtraSpace(a);
        System.out.print("Leaders : " + inversions);
    }
}

Complexity of reverse array algorithm to find leaders in array is O(n) with no added space complexity.

Please share you views,suggestion, queries or if you find something wrong. If you want t contribute to algorithms and me, please reach out to us on [email protected]

2 Sum problem

2 sum problem goes like: given an array a[] and a number X, find two elements or pair with given sum X in the array. For example:

Given array : [3,4,5,1,2,6,8] X = 10
The answer could be (4,6) or (2,8).

Before looking at the post below, we strongly recommend to have a pen and paper and git it a try to solve it.

Thought process

Ask some basic questions about the problem, it’s a good way to dig more into the problem and gain more confidence. Remember interviewers are not trained interrogators, they slip hint or two around solution when you ask relevant questions.

  • Is it a sorted array? If not, think additional complexity you would be adding to sort it
  • If duplicates present in array?
  • Whether returning first pair is enough or should we return all such pairs with a sum equal to X?
  • If there can be negative numbers in array?

Watch out the video here:

This problem is used regularly in interviews because it tests so many things about your programming knowledge.
It validates that if you can traverse array properly, with both lower and higher bounds. It also checks your optimizing ability once you got a working solution. Can you work with additional constraints? Are you able to work with more than one data structure like an array and hash together to solve a problem?

2 sum problem using sorting

Let’s go with an assumption that input is sorted array and if not, we will sort it? If you want to know how to sort an array efficiently,refer Quick sort or Merge sort
With sorted array, we can apply below algorithm to find a pair with given sum.

1. Initialize two variable left = 0 and right = array.length-1
2. While left and right do not cross each other,
3. Get sum of elements at index left and right, i.e A[left] + A[right]
4. If sum > K, move towards left from end i.e decrease right by 1
5. Else if sum < K,then move towards right from start, i.e increment left
6. At last, if sum is equal to K, then return (left, right) as pair.

Let’s see how this works with an example and then we will implement it. Given an array as shown and sum = 17, find all pairs which sum as 17.

2 sum problem

Initialization step, left = 0 and right = array.length – 1

find two number with sum k

A[left] + A[right] = 20 which is greater than sum (17), move right towards left by 1.

pair with given sum

Again, A[left] + A[right] = 18 which is greater than sum (17), move right towards left by 1.

two numbers with given sum

At this point, A[left] + A[right] is less than sum(17), hence move left by 1

2 sum problem

Now, A[left] + A[right]  is equal to the sum and so add this pair in the result array. Also, decrease right by 1, why?

At this point, A[left] + A[right] is less than sum(17), hence move left by 1

sum of two numbers equal to a number

Again, A[left] + A[right] is less than sum(17), hence move left by 1

two elements add to a given number

A[left] + A[right]  is equal to the sum and so add this pair in the result array. Also, decrease right by 1.

Since left and right point to the same element now, there cannot be a pair anymore, hence return.

Show me the implementation

package com.company;

import javafx.util.Pair;

import java.util.ArrayList;

/**
 * Created by sangar on 5.4.18.
 */
public class PairWithGivenSum {
    public static ArrayList<Pair<Integer, Integer>> pairWithGivenSum(int[] a, int sum){
        int left = 0;
        int right = a.length - 1;

        ArrayList<Pair<Integer, Integer>> resultList = new ArrayList<>();

        while(left < right){
            /*If sum of two elements is greater than
              sum required, move towards left */
            if(a[left] + a[right] > sum) right--;
            /*
              If sum of two elements is less than
              sum required, move towards right
            */
            if(a[left] + a[right] < sum) left++;
            if(a[left] + a[right] == sum){
                resultList.add(new Pair(left, right));
                right--;
            }
        }
        return resultList;
    }
    public static void main(String[] args) {
        int a[] = new int[] {10, 20, 30, 40, 50};

        ArrayList<Pair<Integer, Integer>> result = pairWithGivenSum(a,50);
        for (Pair<Integer, Integer> pair : result ) {
            System.out.println("("+ pair.getKey() + "," + pair.getValue()  + ")");
        }
    }
}

Complexity of this algorithm to find two numbers in array with sum K is dependent on sorting algorithm used. If it is merge sort, complexity is O(n log n) with added space complexity of O(n). If quick sort is used, worst case complexity is O(n2) and no added space complexity.

Solution with hashmap

In first method,  array is modified, when it is not already sorted. Also, Preprocessing step (sorting) dominates the complexity of algorithm. Can we do better than O(nlogn) or in other words, can we avoid sorting?

An additional constraint put on the problem is that you cannot modify original input.  Use basic mathematics, if A + B = C, then A = C-B.  Consider B is each element for which we are looking for A. Idea is to scan the entire array and find all A’s required for each element. Scan array again and check there was B which required the current element as A.
To keep track of required A values, we will create a hash, this will make second step O(1).
We can optimize further by scanning array only once for both steps.

1. Create an hash
2. Check element at each index of array
    2.a If element at current index  is already in hash. return pair of current index and value in hash
    2.b If not, then subtract element from sum and store (sum-A[index], index) key value pair in hash.

This algorithm scans the array only once and does not change input. Worst-case time complexity is O(n), hash brings additional space complexity. How big should be the hash? Since all values between the sum-max value of the array and sum-min value of array will be candidate A’s hence hash will be of difference between these two values.

This solution does not work in C if there are negative numbers in an array. It will work in languages that have HashMaps in-built. For C, we have to do some preprocessing like adding absolute of smallest negative number to all elements. That’s where our fourth question above helps us to decide.

2 sum problem hash based implementation

package com.company;

import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Created by sangar on 5.4.18.
 */
public class PairWithGivenSum {
    public static ArrayList<Pair<Integer, Integer>> pairsWithGivenSum2(int[] a, int sum){
        int index = 0;
        ArrayList<Pair<Integer, Integer>> resultList = new ArrayList<>();

        HashMap<Integer, Integer> pairMap = new HashMap<>();
        for(int i=0; i< a.length; i++){
            if(pairMap.containsKey(a[i])){
                resultList.add(new Pair(pairMap.get(a[i]), i));
            }
            pairMap.put(sum-a[i], i);
        }
        return resultList;
    }
    public static void main(String[] args) {
        int a[] = new int[] {10, 20, 30, 40, 50};

        ArrayList<Pair<Integer, Integer>> result = pairsWithGivenSum2(a,50);
        for (Pair<Integer, Integer> pair : result ) {
            System.out.println("("+ pair.getKey() + "," + pair.getValue()  + ")");
        }
    }
}

Please share if there is some error or suggestion to improve. We would love to hear what you have to say. If you want to contribute to the learning process of others by sharing your knowledge, please write to us at [email protected]

Minimum in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array.

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array.

To understand the problem, let’s understand what is a sorted array, and then what is sorted rotated array?

An array is called sorted where for all i and j such that i < j, A[i] <= A[j].
A rotation happens when the last element of an array is pushed at the start and all elements of array move right by one position. This is called as rotation by 1. If the new last element is also pushed to start again, all elements are moved to the right, it’s a rotation by 2, and so on.

minimum in rotated sorted array

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

Minimum in sorted rotated array and binary search algorithm

As always, first, come up with a brute force solution without worrying about any optimizations as of now. The simplest way would be to scan through the array and keep track of the minimum. The complexity of this method is O(n).

In the brute force solution, we did not use the fact that the array is sorted and then rotated. Let’s forget about rotation and concentrate only on the sorted part.

What is the minimum element in a sorted array? Obviously, it is the first element of the array. We see that all the elements on the right side of the minimum elements are greater than the minimum.

What will happen if start rotating array now, is the condition that all the elements on the right of the minimum element are greater than it still holds? Yes, it does. Either there will be no element on the right side of minimum or the will be definitely greater than it. So it is obvious, that the first element in the sorted part of the array is a candidate for the minimum element in a sorted rotated array, rest all can be discard.

What if we start with the middle element. How do I know that if array on the right side of it is sorted or not? What information comparison between the middle and end gives us?

If middle element is less than the last element, the array is sorted from index mid to end, in this case, we have to look for minimum on the left part including the mid
minimum in sorted rotated array

If the middle element will be greater than the last element, array on the right side is not sorted, there must be someplace in this right part, where the sorted array start, hence minimum element should be in the right part of the array.

find minimum in rotated array

When should we stop? Well, what is the minimum of an array with only one element? The element itself. We will also stop when there is only 1 element left.

Algorithm to find minimum in sorted rotated array

  1. Find mid = start + (end- start) /2
  2. See if mid is part of sorted array or not, check A[mid] < A[end]
  3. If yes, minimum should be on the left part
  4. If no, minimum should be on the right part

Minimum in sorted rotated array implementation

class Solution {
    public int findMin(int[] nums) {
        
        int start = 0;
        int end = nums.length-1; //O(1)
        int mid;
        
        while(start < end){
            mid = start + ((end - start)/2);
        
            if(nums[mid]<nums[end]){
                end = mid;
            }
            else{
                start = mid+1;
            }
        }
        
        return nums[start];
    }
}

The complexity of the algorithm to find minimum in a sorted rotated array is O(logn) because of binary search algorithm.

This problem is asked in many variations like find pivot in a sorted rotated array or find the number of rotations.

Interview coming up? Check out our full coding interview prep course. There’s a get-the-job-or-your-money-back guarantee, so it only costs money if it actually works.

As always, shoot me an email if there’s anything I can help with.

Find element in sorted rotated array

Find element in sorted rotated array

To understand how to find element in sorted rotated array, we must understand first, what is a sorted rotated array? An array is called sorted where for all i and j such that i < j, A[i] <= A[j]. A rotation happens when last element of array is push at the start and all elements on array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again all elements are moved to right again, it’s rotation by 2 and so on.

Find element in sorted rotated array
Sorted array
Sorted rotated array

Question which is very commonly asked in Amazon and Microsoft initial hacker round interviews or telephonic interviews : Given a sorted rotated array, find position of an element in that array. For example:

A = [2,3,4,1] Key = 4, Returns 2 which is position of 4 in array

A = [4,5,6,1,2,3] Key = 4 returns 0

Find element in sorted rotated array : Thought process

Before starting with any solution, it’s good to ask some standard questions about an array problem, for example, if duplicate elements are allowed or if negative numbers are allowed in array? It may or may not change the solution, however, it gives an impression that you are concerned about input range and type.

First thing to do in interview is come up with brute force solution, why? There are two reasons : first, it gives you confidence that you have something solved, it may not be optimal way but still you have something. Second, now that you have something written, you can start looking where it takes most of time or space and attack the problem there. It also, helps to identify what properties you are not using which are part of the problem and help your solution.

First thing first, what will be the brute force solution? Simple solution will be to scan through the array and find the key. This algorithm will have O(N) time complexity.

There is no fun in finding an element in sorted array in O(N) 🙂 It would have been the same even if array was not sorted. However, we already know that our array is sorted. It’s also rotated, but let’s forget about that for now. What do we do when we have to find an element in sorted array? Correct, we use binary search.

We split the array in middle and check if element at middle index is the key we are looking for? If yes, bingo! we are done.

If not, if A[mid] is less that or greater than key. If it is less, search in right subarray, and it is greater, search in left subarray. Any which way, our input array is reduced to half. Complexity of binary search algorithm is log (N). We are getting somewhere 🙂

Sorted rotated array

However, our input array in not a plain sorted array, it is rotated too. How does things change with that. First, comparing just middle index and discarding one half of array will not work. Still let’s split the array at middle and see what extra conditions come up?
If A[mid] is equal to key, return middle index.
There are two broad possibilities of rotation of array, either it is rotated more than half of elements or less than half of elements. Can you come up with examples and see how array looks like in both the cases?

If array is rotated by more than half of elements of array, elements from start to mid index will be a sorted.

If array is rotated by less than half of elements of array, elements from mid to end will be sorted.

Next question, how do you identify the case, where array is rotated by more or less than half of elements? Look at examples you come up with and see if there is some condition?

Yes, the condition is that if A[start] < A[mid], array is rotated more than half and if A[start] > A[mid], it is rotated by less than half elements.

Now, that we know, which part of array is sorted and which is not. Can we use that to our advantage?

Case 1 : When array from start to mid is sorted. We will check if key > A[start] and key < A[mid]. If that’s the case, search for key in A[start..mid]. Since, A[start..mid] is sorted, problem reduces to plain binary search. What if key is outside of start and middle bounds, then discard A[start..mid] and look for element in right subarray. Since, A[mid+1..right] is still a sorted rotated array, we follow the same process as we did for the original array.

Case 2 : When array from mid to end is sorted. We will check if key >A[mid] and key < A[end]. If that’s the case, search for key in A[mid+1..end]. Since, A[mid+1..end] is sorted, problem reduces to plain binary search. What if key is outside of mid and end bounds, then discard A[mid..end] and search for element in left subarray. Since, A[start..mid-1] is still a sorted rotated array, we follow the same process as we did for the original array.

Let’s take an example and go through the entire flow and then write concrete algorithm to find element in sorted rotated array.

Below is sorted rotated array given and key to be searched is 6.

We know, A[start] > A[mid], hence check if searched key fall under range A[mid+1..end]. In this case, it does. Hence, we discard A[start..mid].

At this point, we have to options:  either fallback to traditional binary search algorithm or continue with same approach of discarding based on whether key falls in range of sorted array. Both methods work. Let’s continue with same method.

Again find middle of array from middle +1 to end.

A[mid] is still not equal to key. However, A[start] < A[mid]; hence, array from A[start] to A[middle] is sorted. See if our key falls between A[start] and A[mid]? Yes, hence, we discard the right sub array A[mid..End]

Find the middle of remaining array, which is from start to old middle – 1.

Is A[mid] equal to key? No. Since, A[start] is not less than A[mid], see if key falls under A[mid+1..end], it does, hence discard the left subarray.

Now, new middle is equal to key are searching for. Hence return the index.

Similarly, we can find 11 in this array. Can you draw the execution flow that search?

Algorithm to find element in sorted rotated array

  1. Find mid =  (start + end)/ 2
  2. If A[mid] == key; return mid
  3. Else, if A[start] < A[end]
    • We know, left subarray is already sorted.
    • If A[start] < key and A[mid] > key :
      • discard A[mid..end]
      • Continue with new subarray with start and end = mid – 1
    • Else:
      • discard A[start..mid]
      • Continue with new subarray with start = mid + 1 and end
  4. Else
    • We know, right subarray is sorted.
    • If A[mid] < key and A[end] > key :
      • discard A[start..mid]
      • Continue with new subarray with start  = mid + 1 and end
    • Else:
      • discard A[start..mid]
      • Continue with new subarray with start and end = mid – 1

Find element in sorted rotated array : Implementation

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

    public static int findElementRecursive(int[] input, int start, int end, int key){

        if(start <= end){
            int mid = start + (end - start) / 2;

            if(input[mid] == key) return mid;

            else if(input[start] <= input[mid]){
                /*Left sub array is sorted, check if
                key is with A[start] and A[mid] */
                if(input[start] <= key && input[mid] > key){
                    /*
                      Key lies with left sorted part of array
                     */
                    return findElementRecursive(input, start, mid - 1, key);
                }else{
                    /*
                    Key lies in right subarray
                     */
                    return findElementRecursive(input, mid + 1, end, key);
                }
            }else {
                /*
                 In this case, right subarray is already sorted and
                 check if key falls in range A[mid+1] and A[end]
                 */
                if(input[mid+1] <= key && input[end] > key){
                    /*
                      Key lies with right sorted part of array
                     */
                    return findElementRecursive(input, mid + 1 , end, key);
                }else{
                    /*
                    Key lies in left subarray
                     */
                    return findElementRecursive(input, start, mid - 1, key);
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] input = {10,11,15,17,3,5,6,7,8,9};

        int index = findElementRecursive(input,0, input.length-1, 6);
        System.out.print(index == -1 ? 
              "Element not found" : "Element found at : " + index);

    }
}

Iterative implementation

package com.company;

/**
 * Created by sangar on 22.3.18.
 */
public class SortedRotatedArray {

    public static int findElementIteratve(int[] input, int start, int end, int key) {

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (input[mid] == key) return mid;

            else if (input[start] <= input[mid]) {
                /*Left sub array is sorted, check if
                key is with A[start] and A[mid] */
                if (input[start] <= key && input[mid] > key) {
                    /*
                      Key lies with left sorted part of array
                     */
                    end = mid - 1;
                } else {
                    /*
                    Key lies in right subarray
                     */
                    start  = mid + 1;
                }
            } else {
                /*
                 In this case, right subarray is already sorted and
                 check if key falls in range A[mid+1] and A[end]
                 */
                if (input[mid + 1] <= key && input[end] > key) {
                    /*
                      Key lies with right sorted part of array
                     */
                    start = mid + 1;
                } else {
                    /*
                    Key lies in left subarray
                     */
                    end  = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] input = {10,11,15,17,3,5,6,7,8,9};

        int index = findElementIteratve(input,0, input.length-1, 6);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);

    }
}

Complexity of above recursive and iterative algorithm to find an element in a rotated sorted array is O(log n). Recursive implementation has implicit space complexity of O(log n)

What did we learn today? We learned that it’s always better to come up with non-optimized solution first and then try to improve it. Also helps to correlate problem with similar and simpler problem like we understood first what is best way to find an element in sorted array and then extrapolated the solution with additional conditions for our problem.

I hope that this post helped you with this problem and many more similar problems you will see in interviews.

Please share if you have some questions or suggestions. Also, if you want to contribute on this learning process of others, please contact us.

Binary Indexed Trees

Binary Indexed Trees (Fenwick Tree)

Why Binary Indexed Tree?Consider an array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}, you have to find the sum of a range say (1,5). One way of doing this can be by keeping the sum of elements from index 0 to index i, where 0 <= i<= n. So the array with all the cumulative sum is "sum" :{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136} and to calculate sum from 1 to 5 we can simply do sum[5] – sum[1]. This will take O(n) precomputing time and O(q) with q queries with O(1) complexity per query

Let us modify the question now, Suppose we have another query that modifies value at some index i,  this will make us calculate the sum from index ‘i’ to ‘n’ again. Now the complexity will be O(q*n) if there are ‘q’ queries. Segment trees can be used to solve this in O(q*log(n)). (Refer to this post for segment trees).
Coding for segment trees can be a very lengthy and Hectic process, Segment Trees require a very large memory space, Debugging a code of segment tree is very difficult. Another approach to solve the above problem is to use Binary Indexed Tree data structure, which also has O(q*log(n))
complexity but BIT (Binary Indexed Trees) are much easier to code and require very less memory space than segment trees. Binary Indexed trees are also called Fenwick Trees.

Representation of Binary Indexed Tree

Consider an input array A : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}. Binary Indexed Tree or Fenwick tree is represented using an array of size n, where n is the length of the input array. Let’s call the binary indexed tree of this array “tree[n]”. tree[idx] (where idx is some index of BIT) will store the sum of values of the given input array from index (idx – 2^r +1)  to index idx. 
Here, r is the position of the last set bit (from left to right) in binary representation of the index idx. 
So, for example idx = 6, binary representation of 6 is 0110, Therefore the last set bit from left to right is the 1st bit (considering 0 based index) which makes r = 1. Therefore tree[6] stores the sum from index 5 to index 6.

The diagram below shows value of r for every index from 1 to 16. The color of rth index is changed for better understanding.


Binary Indexed Tree

Therefore, tree[12] = A[9] + A[10] + A[11] + A[12]. To calculate “tree[idx]”, we can store the cumulative sum from index “0” to index “idx”  where (0 <= idx < n) in an array and then subtract "sum[idx – 2^r + 1]" from "sum[idx]". This will find value of tree[idx] in O(1).
So, tree[idx] = sum[idx] – sum[idx – 2^r + 1]. 

How to Find the value of the last set bit?

Let num be an integer whose last set bit we want to isolate. Note that num can be represented in the form a1b, where a represents the series of bits before last set bit and b represents all the zeros after the last set bit.
Integer (-num) can be found out using 2’s complement of num, which is done by adding 1 to the inverse of num. the expression for finding twos complement is as follows,
(a1b)¯ + 1 = a¯0b¯ + 1

Since b consists of all zeroes, so b¯  consists all ones.Therefore, finally we have -num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b. 
Now, we can easily isolate the last digit, using bitwise operator AND with num and -num a 1 b &   a¯1 b       ——————–     = (0…0)1(0…0)
So, to calculate the value of (idx – 2^r + 1) we just have to do the following operation

idx = idx – (idx & -idx);

Construction of Binary Indexed Tree 

For every index “idx”, tree[idx] is calculated in O(1) complexity using the expression tree[idx] = sum[idx] – sum[idx – 2^r + 1], where “sum[idx]” stores the cumulative sum from index “0” to index “idx”.

The code is shown below.

int* construct_bit(int sum[], int length)
{
    int *tree = new int[length];
    tree[0] = 0;
    
    for(int idx = 1; idx < length; idx++)
    {
	int left, right;
	
	left = idx - (idx & (-idx));
	right = idx;

	tree[idx] = sum[right] - sum[left]; 
    }

    return tree;
}

Sum Between Two Indices :
To calculate sum between two given indices l and r. we will have to calculate sum from index ‘0’ to index ‘r’, then the same thing from index ‘0’ to index ‘l’ and then calculate the difference between of the results obtained.
Let us consider an example of index 13, to calculate sum from index 0 to index 13, array tree will play a major role here, we know that tree[13] will store sum of 13th index only, tree[12] stores sum from 9th index to 12th index and tree[8] stores sum from  index 0 to index 8. So, adding tree[8] + tree[12] + tree[13] will give us cumulative sum from index 0 to index 13.
tree[13] = tree[13] + tree[12] + tree[8]
tree[1101] = tree[1101] + tree[1100] + tree[1000]
(Binary representation)

Note that, complexity of our algorithm to calculate sum from index 0 to index idx will be O(log(idx)). The diagram below illustrate this.


Binary Indexed Tree

The Code to find sum from index 0 to index idx is shown below

int read_sum(int tree[], int index)
{
	int sum = 0;
	while(index > 0)
	{
		sum += tree[index];
		index -= (index & -index);
	}
	return sum;
}

Update Value at some position and update BIT : 
If a value at some index idx is added by some value say val, then we will have to update the tree at all those places which are affected by this index. For example, if value at 9 is changed, then tree[10], tree[12], tree[16] …so on, will be changed because
tree[10] = tree[9] + tree[10]; tree[12] = tree[9] + tree[10] + tree[11] + tree[12]; while we were reading the sum, we were removing last set bit from index until it became zero. Now, while updating the tree we should add one set bit to the index idx until it becomes greater than or equal to length.
Below is the code to do that.

void update_tree(int idx, int val, int tree[])
{
	int length = sizeof(tree)/sizeof(int);
	idx++;
	while(idx <= length)
	{
		tree[idx] += val;
		idx += idx & (-idx);
	}
}

Binary Indexed Trees easy to code, the code length is very short and should be used wherever possible.
The Links of some practice problems are given below : 
http://www.spoj.com/problems/UPDATEIT/


http://www.spoj.com/problems/CTRICK/

Kth smallest element in two sorted arrays

We have already solved a problem to find kth smallest element in an array using quicksort modification and min-heap. Today, our problem is to find Kth smallest element in two sorted arrays.
For example if A = [10, 20, 40, 60] and B =[15, 35, 50, 70, 100] and K = 4 then solution should be 35 because union of above arrays will be C = [10,15,20,35,40,50,60,70,100] and fourth smallest element is 35.

Kth smallest element in two sorted arrays

As I always insist on doing: what will be the most brute force solution for this problem. Simple, merge two sorted arrays into one and find the kth smallest element in the array. There are different ways to merge two sorted arrays, merge part of merge sort will be most efficient when two parts are already sorted. The time complexity of merge is O(n+m) and additional space complexity of O(m+n) where m and m are sizes of two sorted arrays.

If you are preparing for an interview, you can signup for a free session to find a coach to help you with your preparation.

Now that we already know brute force solution, can we do better than this? The k-th smallest element can be present in any one of the two arrays. How many elements can we include from first array A, with size m, it can be max(k-1, m).

Let’s suppose we took i elements from the first array, how many maximum numbers of elements we can take from array B? Since, we have zero-based indexing of array,

i+j = k-1

kth smallest element in two sorted arrays

Now, we need to find combination of i and j such that all elements from 0 to i are less than B[j] and all elements from 0 to j should be smaller than A[i], and min(A[i], B[j]) will be the kth smallest element in the combined array.

k-th smallest element in two sorted array

For A[i], all elements from index 0 to i-1 are smaller, all we need to check is that all elements in array B from index 0 to index j-1 are smaller too. Therefor A[i] >= B[j-1]

Similarly for B[j], it must satisfy the condition B[j] >= A[i-1].

kth smallest element in array

In order to be kth smallest element, index i and j have to satisfy two conditions:

  1. A[i] >= B[j-1] and B[j] >= A[i-1]
  2. i+j  =  k-1 or j = k-1-i

What if A[i] < B[j-1]  as we saw in the first picture?  That means i is too small, we need to increase i and when we increase i and A[i], j and B[j] is decreased automatically, which makes it possible to satisfy A[i] >= B[j-1].

In the same vain when B[j] < A[i-1],  i is too big and it’s a good choice to decrease it.

This is where binary search comes into the picture. We can start i as mid of array A, j = k-i, and see if this i satisfies the condition. There can be three possible outcomes for the condition.

1. A[i-1] >= B[j] and B[j-1] <=A[i] is true, we return the index min(A[i], B[j])
2. IfB[j-1] > A[i], in this case, A[i] is too small. How can we increase it? by moving towards right. If i is increased, value A[i] is bound to increase, and also it will decrease j. In this case, B[j-1] will decrease and A[i] will increase which will make B[j-1] >=A[i] is true. So, limit search space for i to  mid+1 to min(k, m)
3. A[i-1] > B[j], means A[i-1] is too big. And we must decrease i to get A[i-1] >=B[j]. Limit search space for i from 0 to i-1.

Since, i is bound by 0 to min(k-1,m), j will never go below 0. When i or j is 0, return min(A[i], B[j]).

Let’s take an example and see how it works. Below are the two sorted arrays and K = 7.

The first thing to notice is that k is greater than m, size of array A. Hence the range of i will be 0 to m i.e. 5. Find mid, i = 2 and j = k – 2-1 = 4

Now, A[i] < B[j-1], it is evident that we chose i too small. Search space is now from i+1 to m.

Again we find mid which is index 4 of array A. Index j = 2. At this point condition A[i-1] <= B[j] is false. This means we chose i too big and hence we decrease range till i-1 which now 3.

New i and j are shown below. Condition A[i-1] <= B[j] and B[j-1] <= A[j] is true. Return min(A[i], B[j]) as kth smallest element which is 6.

Implemmentation to find kth smallest element

package com.company;

/**
 * Created by sangar on 19.4.18.
 */
public class KthSmallestElement {

    public static double findKthSmallestElement(int[] A, int[] B, int k){

        int[] temp;

        int lenA = A.length;
        int lenB = B.length;

        if(lenA + lenB < k) return -1;

        int iMin = 0;
        int iMax = Integer.min(A.length, k-1);

        int i = 0;
        int j = 0;

        while (iMin <= iMax) {
            i = (iMin + iMax) / 2;
            j = k - 1 - i; // because of zero based index
            if (B[j - 1] > A[i]) {
                // i is too small, must increase it
                iMin = i + 1;
            } else if (i > 0 && A[i - 1] > B[j]) {
                // i is too big, must decrease it
                iMax = i - 1;
            } else {
                // i is perfect
               return Integer.min(A[i], B[j]);
            }
        }
        return -1;
    }

    public static void main(String[] args){
        int[] a = {1,3,5,6,7,8,9,11};
        int[] b = {1,4,6,8,12,14,15,17};

        double smallest = findKthSmallestElement(a,b, 9);
        System.out.println("Kth smallest element is : " + smallest);
    }
}

Complexity of algorithm to find Kth smallest element two sorted arrays is O(log(N+M)).

Please share if there is something wrong or missing. we would be glad to hear from you. If you are preparing for an interview and want to understand how to approach it, please book a free coaching session.

Subarrays with sum zero

Given an array of positive and negative integers, find number of subarrays with sum zero in that array. For example, in the array given below, there are two subarrays whose elements sum to zero.

Input:
A = [1,3,2,-1,5,4,-8,4,3,-7]
Output:
4
Explanation:
Sybarrays [-1,5,4,-8], [4,-8,4], [-1,5,4,-8,4,3,-7] and [4,3,-7] are subarrays with zero sum.

Brute force method solve this problem will be to find all subarrays of the given array and then add them individually to see if any subarray adds up to zero. There can be n * (n-1) subarrays for a given array of size n, so the complexity of brute force solution is O(n2).

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSumBrute(int[] a){
        int len = a.length;
        int count = 0;
        for(int i=0; i<len; i++){
            int  sum  = 0;
            for(int j=i; j<len; j++){
                sum += a[j];
                if(sum == 0){
                    count++;
                }
            }
        }
        return count;
    }
}

Thought proces

A subarray is a contiguous part of an array. Let’s say we find the sum of subarray starting at 0 and ending at any index i. So, T[i] represents the sum of subarray A[0..i].

What if we have two indices i and j; such that i< j and T[i] = T[j]. In this case, all the elements which are from index i+1 and index j add up to zero and that is our subarray with sum zero. Length of subarray with sum zero will be j-i+1.

Show me implementation

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSum(int[] a){

        int len = a.length;
        int [] T = new int[len];

        T[0] = a[0];
        for(int i=1; i<len; i++){
            T[i] = T[i-1] + a[i];
        }

        //Complexity of below code is O(n^2)
        int count = 0;
        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                if(T[i]== T[j]){
                    count++;
                }
            }
        }
        return count;
    }
}

The complexity of the implementation is O(n2) with an additional space complexity of O(n) to store sum till index i.

We can optimize it further by creating a hash of all the sums which we see while adding. When we add the index i to already calculated sum till index i-1, we check if the new sum is zero? If yes, then subarray from 0 to index i add up to zero. If there is already a sum present which is equal to the current sum then there is subarray with sum zero between index when we saw the sum last and current index.

Implementation with hashmap

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {

    public int [] findSubarrayWithZeroSumOptimized(int[] a){

        int len = a.length;
        HashMap<Integer, Integer> T = new HashMap<Integer, Integer>();
        T.put(0, 1);

        int sum  = 0 ;
        int count = 0;
        for(int i=0; i<len; i++){
            sum  += a[i];
            if(T.containsKey(sum)){
                count += T.get(sum);
                T.put(sum, count);
            }else{
                T.put(sum, 1);
            }
        }
        return count;
    }
}

The complexity of this method is O(n) with additional space of O(n) in worst case.

If you want to solve an advance version of the problem, read it here: subarrays with sum k.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free interview kit.

Minimum jumps to reach at end

Minimum jumps to reach end of array

Given an array of integers, find minimum jumps to reach end of the array. Condition is that you can maximum jump a[i] indices from index i.

For example, in following array, minimum jumps required are 2.

Original array

At index 1, we can either jump 0, 1 or 2 indices ahead. If we jump 2 indices, we would require two more jumps (at 1 and 1) to reach at 4. So total number of jumps would be 3.

You jump maximum at start, but at the end, more number of jumps required.

However if we jump only 1 index ahead, next A[i] will allow us to jump 3 indices ahead, doing so we will reach at the end of the array. So minimum number of jumps to reach at the end of array is 2.

minimum jumps required
Not starting with maximum jump actually save one jump to reach at the end

Minimum number of jumps : thought process

What would be the brute force method to solve this? At each index, you try all possible jumps and get the combination which gives you the minimum jumps. This method will have exponential complexity which we do not want.

What is the original problem? It’s minJumps(start, end) Of all the jumps possible from start, let’s say we go to index k, then what how does problem reduces? Well, now we have to find minimum number of jumps from k to end. How to decide on k now? We try all k values from start+1 to start + a[i].

minJumps(start, end) = Min ( minJumps(k, end) )
for all k reachable from start 

Now, we have clear recursion relationship, what should be the base case? When k + A[k] > end, or k == end, we should return 1 as there would be only one jump required from k to end now.

package com.company;

/**
 * Created by sangar on 10.10.18.
 */
public class MinimumJumps {

    public int minimumNumberOfJump(int[] a, int start, int end){
        //If start == end, we reached the end, return 0.
        if(start == end) return 0;

        //if current element is 0, you cannot jump to end at all
        if(a[start] == 0) return Integer.MAX_VALUE;

        int minimumJumps = Integer.MAX_VALUE;

        for(int k=start+1; k<=start+a[start] && k<=end; k++){
            /*
            For each K from start+1 to end, find the minimum jumps.
             */
            int jumps = minimumNumberOfJump(a,k,end);
            if(jumps != Integer.MAX_VALUE && jumps + 1 <; minimumJumps){
                minimumJumps  = jumps + 1;
            }
        }
        return minimumJumps;
    }
}

Test cases for above function

package test;

import com.company.MinimumJumps;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class MinimumJumpTest {

    MinimumJumps tester = new MinimumJumps();

    @Test
    public void baseTest() {

        int[] a = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        assertEquals(3,
			tester.minimumNumberOfJump(a,0, a.length-1));
    }

    @Test
    public void arrayContainsZeroTest() {

        int[] a = {1, 3, 0, 0, 0, 2, 6, 7, 6, 8, 9};
        assertEquals(Integer.MAX_VALUE, 	  
			tester.minimumNumberOfJump(a,0, a.length-1));
    }

    @Test
    public void nullArrayTest() {

        assertEquals(0, tester.minimumNumberOfJump(null,0, 0));
    }

    @Test
    public void arrayWithTwoElementsTest() {

        int[] a = {1, 0};
        assertEquals(1,
			tester.minimumNumberOfJump(a,0, a.length-1));
    }
}

Let’s see execution trace of above function for an input.

Nodes in red are re-calculated

From the above execution tree, we notice that some subproblems are calculated again and again. This is typically known as overlapping subproblems.
Also, optimal solution to subproblem actually lead us to optimal solution for original problem which is optimal subproblem structure. These two property are must to apply dynamic programming to a problem.

What if we store minimum number of jumps required to reach a particular index. To reach first index, jumps required is 0. Jump[i] represents the number of reach index i. Solution to reach at the end of the array would be Jump[n-1]. How do we feel this array? For each i,  from  j = 0 to i-1 and check if j+a[j] <= i, if yes, update jump[i] = min (jump[i], jump[j]+1).

Minimum number of jumps: dynamic programming approach

package com.company;

/**
 * Created by sangar on 10.10.18.
 */
public class MinimumJumps {

    public int minimumNumberOfJumpDP(int[] a){

        if(a == null || a.length == 0) return 0;

        if(a[0] == 0) return Integer.MAX_VALUE;

        int[] jump = new int[a.length];

        //no jumps required for first element
        jump[0] = 0;

        for(int i=1; i<a.length;i++){
            jump[i] = Integer.MAX_VALUE;

            for(int j=0; j<i; j++){
                if(j+a[j]>=i && jump[j] != Integer.MAX_VALUE ){
                    jump[i] = Integer.min(jump[i], 1 + jump[j]);
                }
            }
        }
        return jump[a.length-1];
    }
}

Complexity of dynamic programming approach to find minimum number of jumps to reach end of an array is O(n2) with space complexity of O(n)

If you are interested to solve this problem in O(n) time, please visit stack overflow discussion 

Please share if there is something wrong or missing. If you are interested in taking coaching from one of our experienced teachers, please reach out to us at [email protected]

Find peak in array (local maxima)

Peak in array

Given an unsorted array, find a peak in array. A peak is defined as an element which is not smaller than its immediate neighbors. In an unsorted array, there can be many such peaks, referred to as local Maxima. Mathematically, ith element is called as peak following property holds true:

A[i-1] <= A[i] >=A[i+1]

For first element and last elements of array, left and right neighbors respectively, are considered as negative infinity.

A[0] = A[n] = -infinity

For example, peak in following array would be 6 or 7

Can you identify the peak in this array?

What would be peak in sorted array? It will be the last element of array and similarly, for reverse sorted array, first element will be peak.

Peak  in array : Thought process

I recommend two things: First, get your pen and paper to practice this problem yourself. Second, try to come up with brute force solution as soon as possible. Why? Because it adds to your confidence, when you have some solution already in hand.

Brute force approach to find peak in an array of integers will be to scan through it and for each element, check if greater than it’s greater than previous and next element.  If it is, return index of that element. In worst case we would end up scanning whole array (in a sorted array), so worst case complexity of brute force solution is O(N)

Obviously, this would not have been an interview question, if expectation was to solve it in O(N) complexity, anyone with basic programming knowledge can solve it. There is no way to differentiate a good candidate from an average based on this question then. However, interviewer expects you to solve it in better than O(N) complexity and that’s where problem becomes interesting.

What if we do not go linear and randomly check index m for local maxima? If it is local maxima, we are good, return the index of that element. If it is not peak and given that array is unsorted, three situations possible at that index :
1. Array is rising toward right, that means, next element is greater than current and it’s previous element.

2.  Array is falling towards right, that means, next element is less than current and it’s previous element.

3.  It’s a valley, where current element is less than both previous and next element.

In first situation, maximum should be on the right side of current index, why? In second situation, peak will be in left side of current index.

If A[m] < A[m+1], A[m] cannot be peak. However, if A[m+2] is less than A[m+1] is less than A[m+1], then A[m+1] can be a peak or some subsequent element can be. In worst case it would be the last element of array if whole A[m..end] is sorted.
If A[m] < A[m-1], in that case, either A[m-1] is peak or some element preceding it can surely be. In worst case, first element will be the peak.

Algorithm to find peak in array

Now question is how to select m? We want to minimize the worst case number of elements to check after splitting, which is possible by splitting the array in middle. Take mid as the starting point, this is classic case of divide and conquer  approach as we will discard half of the array based on certain condition.

  1. Find mid = low + (high-low)/2
  2. If A[mid-1] <= A[mid] =>A[mid+1], then return mid
  3. If A[mid-1] > A[mid], high = mid-1
  4. If A[mid+1] > A[mid], low = mid+1
  5. Repeat step 1 to 4 till there are more than one element in array. Else return that last element.

Let’s take an example and see if this algorithm works. We have given array a as below

peak in array example

Find mid and see if mid is peak we are looking for, in this case it is not as A[mid] is less than A[mid+1].We will discard left subarray and look for peak in right subarray starting from mid+1.

New low and high are shown, we find new mid. Is new mid, local maxima? No, as it is less than previous and next element, it is valley. We will discard right subarray and look for peak in left subarray.

Now, there is only one element, hence it should be peak in array.

peak in array example

Peak in array : Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    public  static int findPeak(int[] a){
        int low = 0;
        int high = a.length-1;

        while (low<high){
            int mid = low + (high-low)/2;
            if(mid == low ) return a[low] > a[high] ? low:high;

            //If mid is local maxima, return it.
            if(a[mid-1] <= a[mid]
                    && a[mid] >= a[mid+1]) return mid;
            //Discard right subarray
            else if(a[mid-1] > a[mid]) high = mid-1;
            //Discard left subarray
            else low = mid+1;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] input = {1,2,6,5,3,7,4};

        int index = findPeak(input);
        System.out.print("Peak found at : " + index);
    }
}

Always remember to check for array with two elements, that will catch almost all bugs regarding boundary overflow. Also, notice that since we are accessing mid+1 and mid-1 indices of array, make sure that these indices are within bounds of array. These two things are very important for a solution to be correct and acceptable in interview. Also, to understand more about binary search algorithm and how it works, please refer to Binary search algorithm

Complexity of divide and conquer algorithm to find peak in unsorted array is O(log n). Recurrence relation for this would be T(n) = T(n/2) + c

Please share if there is something wrong or missing. If you want to contribute to website and help others to learn, please reach out to us on [email protected]