Last occurrence of element with binary search

Last occurrence of element

This problem is very similar to First occurrence of element with binary search. Given a sorted array and an element, find last occurrence of element in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find last index. For example, in given array, last occurrence of 4 is at index 4. Can you guess what is last occurrence of element 6?

last occurrence of element

Brute force solution would be to scan entire array and compare each A[index] with key. If A[index] is equal to key and next element is not equal key, then return index. Worst case time complexity of brute force method is O(N). Can we do better than it?

Last occurrence of element : Thought process

One property of input array we did not use in brute force solution is array being sorted. To search in sorted array: binary search algorithm . If there are no duplicates in array, it will be super easy to find last occurrence using binary search, how can we modify it to solve problem with duplicates.
First question you should ask to yourself : What is candidate solution set? In plain terms, what can be a valid answer if there is key is present? Also, think about case when key is not present at all.

If key is present, candidate answer will be one of the indices. Range of indices is from 0 to array.length -1. We learned one concept  when solving for find greater or equal number or ceiling in sorted array. The concept was, we can apply binary search to any set of input where following condition is met :

Binary search can be used if and only if for all x in candidate Set Spredicate(x) implies predicate(y) for all y > x or for all y < x

If A[index] is less than or equal to key, than all A[y] will be less than or equal to A[index] where y < index, which satisfies our condition to apply binary search.
This means when predicate return true, which is : element equal or less than key, there is no point looking into left subarray, as all elements will be less than or equal to key. Last occurrence of key can not be less than current index. Hence, discard Array[start, index-1] and look in right side of array, Array[index, end].
What should be start point for index? Obviously, it will be mid index. Based on if predicate(mid) is true or false, we discard left or right half of array.

When to stop? When just one element in array. at that point, check if that element is key, if yes return index else return -1.

Last occurrence of element in sorted array : Example

Let’s take an example and see how it works? Take an array as shown below and find last occurrence of element 2.

 

Start with mid index and see if it is less than or equal to key, it is, so discard left subarray excluding mid.

 

New array to be searched is from index 3 to 7. Find new mid, element at new mid is less than or equal to key, in that case discard left subarray.

Search space is reduced from index 5 to 7. Mid is 6 and Array[6] is greater than key, so again discard right subarray.

 

 

At this point, there is only one element left in candidate set. Is it equal to key? If yes, return the index.

last occurrence of element

 

Can you please draw the execution flow to find 1 and say 10 (which does not exist in array)? Does algorithm work for those cases?

Last occurrence of element in sorted array : Implementation

package com.company;

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

    private static boolean isLessThanEqualTo(int[] a, int index, int key){
        if(a[index] <= key) return true;

        return false;
    }

    public static int findLastOccurrence (int[] a, int start, int end, int key){

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

            if(isLessThanEqualTo(a, mid, key)){
                start = mid;
            }
            else{
                end= mid-1;
            }
        }
        return (a[start] == key) ? start : -1;
    }

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

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

Same method can be implemented recursively as follow

public static int findLastOccurrence Recursive(int[] a, int start, int end, int key){

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

        if(isLessThanEqualTo(a, mid, key)){
            return findLastOccurrenceRecursive(a,mid,end, key);
        }
        else{
            return findLastOccurrenceRecursive(a,start,mid-1, key);
        }
    }
    return (a[start] == key) ? start : -1;
}

Worst case complexity to find last occurrence of element in sorted array using binary search algorithm is O(log n).

What did we learn from this problem? First, how to identify if a problem can be solved using binary search. We learned how solution depends on candidate solution set. How can we discard some part of that set based on constraints in problem. For example, in this problem, candidate set was all indices of array, but based on constraint that element should be equal to key, half of those indices were discarded.
Remember to check last element for constraints of problem, if matches, then it is solution, else there is no solution.

Hope, this article helps you to prepare better for your interviews. If you find anything missing or wrong, please reach out to us through comments, email at communications@algorithmsandme.com

First occurrence of element with binary search

First occurrence of element in sorted array

Given a sorted array and an element, find the first occurrence of key in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find first index. For example, in given array, first occurrence of 4 is at index 3. Can you guess what is first occurrence of element 6?

first occurrence of element

Brute force solution would be to scan entire array and compare each A[index] with key. If A[index]  == key, then return index. Worst case time complexity of brute force method is O(N). Can we do better than it?

First occurrence of element : Thought process

One property of input array we did not use in brute force solution is array being sorted. To search in sorted array: binary search algorithm . If there are no duplicates in array, it will be super easy to find first instance using binary search, how can we modify it to solve problem with duplicates.
First question you should ask to yourself : What is candidate solution set? In plain terms, what can be a valid answer if there is key is present? Also, think about case when key is not present at all.

If key is present, candidate answer will be one of the indices. Range of indices is from 0 to array.length -1. We learned one concept  when solving for find greater or equal number or ceiling in sorted array. The concept was, we can apply binary search to any set of input where following condition is met :

Binary search can be used if and only if for all x in candidate Set Spredicate(x) implies predicate(y) for all y > x.

If A[index] is greater than or equal to key, than all A[y] will be greater than or equal to A[index] where y > index, which satisfies our condition.
This means when predicate return true, there is no point looking into right subarray, as all elements will be greater than or equal to key. First instance of key can not be more than index. Hence, discard Array[index+1, end] and look in left side of array, Array[start, index].
What should be start point for index? Obviously, it will be mid index. Based on if predicate(mid) is true or false, we discard right or left half of array.

When to stop? When just one element in array. at that point, check if that element is key, if yes return index else return -1.

First occurrence of element in sorted array : Example

Let’s take an example and see how it works? Take an array as shown below and find first instance of element 6.

Start with mid index and see if it is greater than or equal to key, it is not, so discard the left subarray including mid.

New array to be searched is from index 5 to 9. Find new mid, element at new mid is greater than or equal to key, in that case discard right subarray.

Search space is reduced from index 5 to 7. Mid is 6 and Array[6] is equal to key, so again discard right subarray.

first occurrence of element

Find mid again, which is 5. Array[5] is equal to key, so discard right sub array.

first occurrence of element

At this point, there is only one element left in candidate set. Is it equal to key? If yes, return the index.

first instance of element in sorted array Can you please draw the execution flow to find 1 and say 10 (which does not exist in array)? Does algorithm work for those cases?

First occurrence of element in sorted array : Implementation

package com.company;

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

    private static boolean isGreaterThanEqualTo(int[] a, int index, int key){
        if(a[index] >= key) return true;

        return false;
    }

    public static int findFirstOccurrence (int[] a, int start, int end, int key){

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

            if(isGreaterThanEqualTo(a, mid, key)){
                end = mid;
            }
            else{
                start = mid + 1;
            }
        }
        return (a[start] == key) ? start : -1;
    }

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

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

Same method can be implemented recursively as follow

public static int findFirstOccurrence Recursive(int[] a, int start, int end, int key){

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

        if(isGreaterThanEqualTo(a, mid, key)){
            return findFirstOccurrenceRecursive(a,start,mid, key);
        }
        else{
            return findFirstOccurrenceRecursive(a,mid+1,end, key);
        }
    }
    return (a[start] == key) ? start : -1;
}

Worst case complexity to find first occurrence of element in sorted array using binary search algorithm is O(log n).

What did we learn from this problem? First, how to identify if a problem can be solved using binary search. We learned how solution depends on candidate solution set. How can we discard some part of that set based on constraints in problem. For example, in this problem, candidate set was all indices of array, but based on constraint that element should be equal to key, half of those indices were discarded.
Remember to check last element for constraints of problem, if matches, then it is solution, else there is no solution.

Hope, this article helps you to prepare better for your interviews. If you find anything missing or wrong, please reach out to us through comments, email 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.