Difference between array and linked list

Difference between array and linked list

In last post : Linked list data structure, we discussed basics of linked list, where I promised to go in details what is difference between array and linked list. Before going into post, I want to make sure that you understand that there is no such thing called one data structure is better than other. Based on your requirements and use cases, you chose one or the other. It depends on what is most frequent operation your algorithm would perform in it’s lifetime. That’s why they have data structure round in interview process to understand if you can chose the correct one for the problem.

What is an array?
Array is linear, sequential and contiguous collection of elements which can be addressed using index.

What is a linked list?
Linked list is linear, sequential and non-contiguous collection of nodes, each node store the reference to next node. To understand more, please refer to Linked list data structure.

Difference between arrays and linked list

Static Vs dynamic size

Size of an array is defined statically at the compile time where as linked list grows dynamically at run time based on need. Consider a case where you know the maximum number of elements algorithm would ever have, then you can confidently declare it as array. However, if you do not know, the linked list is better. There is a catch : What if there is a rare chance that number of elements will reach maximum, most of the time it will be way less than maximum? In this case, we would unnecessary allocating extra memory for array which may or may not be used. 

Memory allocation

An array is given contiguous memory in system. So, if you know the address of any of the element in array, you can access other elements based position of the element.

linked list vs arrays
Statically allocated contiguous memory

Linked list are not store contiguous on memory, nodes are scattered around on memory. So you may traverse forward in linked list, given node (using next node reference), but you can not access nodes prior to it.

arrays vs linked list
Dynamically allocated non-contiguous memory

Contiguous allocation of memory required sufficient memory before hand for an array to be stored, for example if want to store 20 integers in an array, we would required 80 bytes contiguous memory chunk. However, with linked list we can start with 8 bytes and request more memory as when required, which may be wherever. Contiguous allocation of memory makes it difficult to resize an array too. We have to look for different chunk of memory, which fits the new size, move all existing elements to that location. Linked list on other hand are dynamically size and can grow much faster without relocating existing elements.

Memory requirement

It’s good to have non-contiguous memory then? It comes with a cost. Each node of linked list has to store reference to next node in memory. This leads to extra payload of 4 bytes in each node. On the other hand, array do not require this extra payload. You  have to trade off extra space with advantages you are getting. Also, sometime, spending extra space is better that have cumbersome operations like shifting, adding and deleting operation on array. Or value stored in node is big enough to make these 4 bytes negligible in analysis.

Operation efficiency

We do operations of data structure to get some output. There are four basic operations we should be consider : read, search, insert/update and delete.

Read on array is O(1) where you can directly access any element in array given it’s index. By O(1), read on array does not depend on size of array.
Whereas, time complexity of read on linked list is O(n) where n is number of nodes. So, if you have a problem, which requires more random reads, array will over-weigh linked list.

Given the contiguous memory allocation of array, there are optimized algorithms like binary search to search elements on array which has complexity of O(log n). Search on linked list on other hand requires O(n).

Insert on array is O(1) again, if we are writing within the size of array. In linked list, complexity of insert depends where do you want to write new element at. If insert happens at head, then it O(1), on the other hand if insert happens at end, it’s O(n).

Insert node at start of linked list
Insert node at the tail of linked list

Update means here, changing size of array or linked list by adding one more element. In array it is costly operation, as it will require reallocation of memory and copying all elements on to it. Does not matter if you add element at end or start, complexity remains O(1).
For linked list, it varies, to update at end it’s O(n), to update at head, it’s O(1). 
In same vain, delete on array requires movement of all elements, if first element is deleted, hence complexity of O(n). However, delete on linked list O(1), if it’s head, O(n) if it’s tail.

To see the difference between O(1) and O(n), below graph should be useful.

difference between array and linked list
Complexity analysis graph

Key difference between array and linked list are as follows

  • Arrays are really bad at insert and delete operation due to internal reallocation of memory.
  • Statically sized at the compile time
  • Memory allocation is contiguous,  which make access elements easy without any additional pointers. Can jump around the array without accessing all the elements in between.
  • Linked list almost have same complexity when insert and delete happens at the end, however no memory shuffling happens
  • Search on linked list is bad.=, usually require scan with O(n) complexity
  • Dynamically sized on run time.
  • Memory allocation is non-contiguous, additional pointer is required to store neighbor node reference. Cannot jump around in linked list.

Please share if there is something wrong or missing. If you wan to contribute to website, please reach out to us at communications@algorithmsandme.com

Median of two sorted arrays

Median of two sorted array

Before going any further, let’s understand what is a median? “Median” is “middle” value in list of numbers. To find median, input should be sorted from smallest to largest. If input is not sorted, then we have to first sort and them return middle of that list. Question arises is what if number of elements in list are even? In that case, median is average of two middle elements. Ask of this problem is to find median of two sorted arrays.
For example :

median of two sorted array

Before going into the post, find a pen and paper and try to work out 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 solution.
Let’s simplify the question first and then work it upwards. If question was to find median of one sorted array, how would you solved it?
If array has odd number of elements in it, return A[mid], where mid = (start + end)/2; else 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 two sorted arrays. To find median of two sorted arrays in no more simple and 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 array into one, problem is reduced to find median of one array. In above example, it will be C = [1,3,5,5,7,9,10,12,15,17]. 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 beginning of two arrays and advance the pointer of array whose current element is smaller than current element of other. This smaller element is put on to output array which is sorted merge array. Merge will use an additional space to store N elements (Note that N is here sum of size of both sorted arrays). Best part of this method is that it does not consider if size of two arrays is same or different. It works for all size of arrays.

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 median. With this optimizations, time complexity remains O(N), however, space complexity reduces to O(1).

Median of two sorted arrays implementation

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);
    }
}

Complexity to find median of two sorted arrays using merge operation is O(N).
Optimized version to find median of two 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);
    }
}

Median of two sorted array using binary search

One of the property which leads 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 condition 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. First array is of size m, and it can be split into m+1 ways at 0 to at m. If we split at i, length(A_left) – i and length(A_right) = m-i.

When i=0, len(A_left) =0 and when i=m, len(A_right) = 0.

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

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

If len(A_left) + len(B_left) == len(A_right) + len(B_right) , 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 median? As we know, median is middle of sorted list, we have to guarantee that all elements on left array should be less than elements in 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 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 picture. We can start i 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 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] is true. So, limit search space for i to mid+1 to m and 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 array as follows.

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

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.

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

This algorithm has very dangerous implementation caveat, which 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);
    }
}

Complexity of this algorithm to find median of two sorted arrays is log(max(m,n)) where m and n are size of two arrays.
Please share your views and suggestions. If you liked content, please share it. If you are interested in contributing to site, please contact us.

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 communications@algorithmsandme.com

Pair with given sum in array

Pair with given sum in array

Given an array a[] and a number X, find two elements or pair with given sum X in array. For example:

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

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

Pair in array with given sum : thought process

Ask some basic questions about the problem, it’s a good way to dig more into 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 sum equal to X?
  • If there can be negative numbers in array?

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 array and hash together to solve a problem?

Find pairs with given sum : 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, These variable are used to traverse array from two ends of array.
  2. While two variables 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 is greater than X, move towards left from end i.e decrease right by 1
  5. Else if sum is less than X,then move towards right from start, i.e increment left
  6. At last, if sum is equal to X, then return (left, right) as pair.

Example

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 pair which sum as 17.

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

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

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

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

Now, A[left] + A[right]  is equal to sum and so add this pair in 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

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

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

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

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 a pair of numbers in array with sum X 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.

Find a pair with given sum in array : Without sorting

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?

Additional constraint put on 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 entire array and find all A’s required for each element. Scan array again and check there was B which required current element as A.
To keep track of required A values, we will create an 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 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 sum-max value of 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 array. It will work in languages which 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.

Pairs with given sum : 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 learning process of other by sharing your knowledge, please write to us at communications@algorithmsandme.com

Minimum in sorted rotated array

Find 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.  Problem today is bit different, there is no key to find first of all. Ask of problem is to find minimum in sorted rotated array.

To understand problem, first let’s understand what is 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 last element of array is push at the start and all elements of 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, it’s rotation by 2 and so on.

Find element in sorted rotated array
Sorted array
Sorted rotated array

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

Find minimum in sorted rotated array : Thought process

As always, first come up with a brute force solution without worrying about any optimizations as of now. Simplest way would be to scan through array and keep track of minimum. Complexity of this method is O(N), however, what is the fun if we do it in O(N) time complexity ?

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

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

What will happen if start rotating array now, is the condition that all the elements on right of minimum element are greater than it still hold? Yes, it does. Either there will be no element on right side of minimum or the will be definitely greater than it.

So, idea is we randomly pick an element and see if elements on right side of it are greater. No need to go through each element, compare selected element with last index element, if last index element is greater, selected element can be minimum. (Remember we are working sorted array!).
Start comparing with middle element. What information comparison between middle and end element gives us?
Array could have been in two ways : It is rotated more than half or it is rotated less than half.
If middle element is less than last element, array is rotated less than half, and hence, minimum element should be on the left half of array.
If middle element will be greater than last element, array is rotated more than half, hence minimum element should be in right part of array.
What if middle element is the minimum element? See if element on left and right of mid are both greater than element at mid, mid is index of minimum element.
Let’s take an example and see how this method works and then come up with concrete algorithm to find minimum in sorted rotated array. For example, array is given as below.
minimum in sorted rotated array
First, we find the mid, check if mid is minimum?  A[mid] > A[mid-1], so it cannot be minimum element. So, see if array is rotated more than half or less than half.
Since, A[mid] > A[end], array is rotated more than half and hence, minimum should be on the right side.
We will discard the left subarray and focus on right subarray to find minimum.
Again, find the mid, is mid the minimum? No, so compare it with end, since, A[mid] < A[end],  minimum should be on the left side, discard right subarray.
Find mid again and this time mid satisfy the condition : A[mid-1] and A[mid+1] both are greater than A[mid], hence, A[mid] should be the minimum element.
minimum in sorted rotated array
Can you come up with execution trace when array is not rotated more than half to start with?

Minimum in sorted rotated array : Algorithm

  1. Find mid = start + (end- start) /2
  2. See if mid is minimum element i.e is A[mid] < A[mid-1] and A[mid] < A[mid+1]. If yes, return mid
  3. Else if A[mid] > A[end]:
    • Array is rotated more than half, minimum should be on right subarray
    • Continue with subarray with start =  mid+1
  4. Else if A[mid] < A[end]:
    • Array is rotated less than half, minimum should be on left subarray
    • Continue with subarray with end = mid-1

Minimum in sorted rotated array implementation

package com.company;

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

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

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

            if (mid == 0 || (input[mid] <= input[mid+1]
                    && input[mid] < input[mid-1])) return mid;
            else if (input[mid] > input[mid]) {
                 /* Array is rotated more than half, hence minimum
                 should be in right sub-array
                  */
                start  = mid + 1;
            } else {
                 /* Array is rotated less than half, hence minimum
                 should be in left sub-array
                  */
                end  = mid - 1;
            }
        }
        return start;
    }
    public static void main(String[] args) {
        int[] input = {10,11,15,17,3,3,3,3,3,3};

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

    }
}

Recursive implementation of same function

package com.company;

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

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

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

            if(mid == 0 || (input[mid] < input[mid-1]
                            && input[mid] <= input[mid+1] ) ) return mid;

            else if(input[mid] > input[end]){
                /* Array is rotated more than half and hence,
                search in right subarray */
                return findMinimumRecursive(input, mid+1, end);
            }else {
                return findMinimumRecursive(input, start, mid - 1);
            }
        }
        return start;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,18,19,20};

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

    }
}

Complexity of algorithm to find minimum in sorted rotated array is O(log N), with recursive implementation having implicit space complexity of O(log N).

What did we learn from this problem?
First learning is to always go for brute force method. Second, try to draw the effect of any additional operations which are done on original array. In sorted rotated array, try to have rotation one by one and see what impact it has on minimum element? Try to classify individual class and design your algorithm. In this problem, we identify that based on how many times array is rotated, minimum can be in right or left subarray from middle and that gave idea for discarding half of the array.

Please share if there is something wrong or missing, or any improvement we can do. Please reach out to us if you are willing to share your knowledge and contribute to learning process of others.

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.

Kth smallest element in two sorted arrays

Find Kth smallest element in two sorted arrays

We have already solved problem to find kth smallest element in an array using quick sort modification and min heap. Today, our problem is to find Kth smallest element in two sorted arrays. In another words, given two sorted arrays, find Kth smallest element of union of these two 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 return Kth smallest element merged 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. Time complexity of merge is O(n+m) and additional space complexity of O(m+n) where m and n are sizes of two sorted arrays.

Now that we already know brute force solution, can we do better than this?
kth 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 first array, how many maximum number 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.

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. There for A[i] >= B[j-1]

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

In order to be kth smallest element, index i and j have to satisfy two conditions, (A[i] >= B[j-1] && B[j] >= A[i-1]) and also i+j  =  k-1 or j = k-1-i

What if A[i] < B[j-1]  as we saw in 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 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 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 o, return min(A[i], B[j]).

There is lot to process I know, let’s take an example and see how it works. Below are the two sorted arrays and K  = 7.

First thing to notice is that k is greater than m, size of array A. Hence 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.

Code to find Kth smallest element in two sorted arrays

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 in union of two arrays is O(log(N+M)).

Please share if there is something wrong or missing. we would be glad to hear from you.

Subarray with sum zero

Subarray with sum zero

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

subarray with sum zero
Input array
Array highlighted adds up to zero
subarray with zero sum

Brute force method to find subarray with sum zero will be to find all sub-arrays of the 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;

        for(int i=0; i<len; i++){
            int  sum  = 0;
            for(int j=i; j<len; j++){
                sum += a[j];
                if(sum == 0){
                    return Arrays.copyOfRange(a,i,j+1);
                }
            }
        }
        return new int[0];
    }
}

Test cases

package test;

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

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

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

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumBruteTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }

    @Test
    public void subarrayWithZeroSumBruteNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }

    @Test
    public void subarrayWithZeroSumBruteOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }
}

Find subarray with sum zero: thoughts

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 between index i 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.

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)

        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                if(T[i]== T[j]){
                    return Arrays.copyOfRange(a, i+1, j+1);
                }
            }
        }
        return new int[0];
    }
}

Test cases

package test;

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

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

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

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

    @Test
    public void subarrayWithZeroSumNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

    @Test
    public void subarrayWithZeroSumOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

The complexity of the algorithm to find a subarray with zero sum in a given array of integers 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.

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>();

        int sum  = 0 ;
        for(int i=0; i<len; i++){
            sum  += a[i];
            if(T.get(sum) != null){
                return Arrays.copyOfRange(a,T.get(sum)+1, i+1);
            }
            T.put(sum, i);
        }

        return new int[0];
    }
}

Test cases

package test;

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

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

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

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumOptimizedTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

    @Test
    public void subarrayWithZeroSumOptimizedNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

    @Test
    public void subarrayWithZeroSumOptimizedOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

}

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

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 communications@algorithmsandme.com

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 communications@algorithmsandme.com