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 number of pages to read

Minimum number of pages to read

In previous post Ceiling in sorted array using binary search , we understood a very important concept about application of binary search in problems where minimum or maximum of something is asked. In the post mentioned above, we were asked to find minimum element which is greater than target value. We will use the same concept to solve another interesting problem : Find minimum number of pages to read for each student. Problem statement:
Given N different books and M students. Each book has certain pages. Every student is assigned to read some consecutive books.  Find a minimum number of pages each student has to read, so that all books are read. It should be noted that a student cannot read partial book, he/she needs to read entire book. For example, if number of pages of 8 books are as given below and there are 3 students to finish those books, a student has to read at least 84 pages. Books have to be read in sequence and either complete book is read or not read at all by student.

minimum number of pages to read

Books read by each student is shown below

If we change the order of books as shown below, minimum number of pages each student has to read are 82

Minimum number of pages to read : Thought process

Before we solve it, let’s revisit the basic premise to use binary search algorithm.

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

In this problem, if students can finish N books with each student reading K pages, then it is definitely possible to finish N books by reading K+1 and more pages. This statement implies, that problem satisfy to apply binary search.

For binary search algorithm, three things are required : search space or candidate solution set, lower bound and upper bound of search space.
Assume that there is only one student, what will be the minimum number of pages he or she has to read to finish all books? Obviously, student has to read at least all pages in all books. This gives us upper bound of our solution set. Answer of this problem cannot be more than this upper bound.

Now, assume that we have N students but there is no book to read. Then minimum number of pages to be read by each student is zero. Well, student cannot read less than zero pages, hence lower bound of solution is zero.
At this point, we know lower and upper bound of solution. How can we find the required minimum number of page with N books and M students?

Idea is to start with middle of lower and upper bounds of pages to be read. Let’s call it K. With each student reading K pages, will all books be completed? If yes, it is always possible to finish all books with each student reading more than K pages, hence, there is no need to check from K to upper bound. All we need to verify that if there is a solution with each student reading K or less than K pages each.

Designing predicate function

What will be predicate? Predicate will be implemented by going through each book’s pages and see when sum of pages goes more than current candidate minimum. As soon it current sum goes more than candidate minimum, we add one more student. When all books are finished, we check if we required less than equal to M students. If yes, this candidate solution is valid and predicate should return true. If more than M students are required to finish all books, then current candidate is not valid and hence function return false.

Based on what is returned from predicate function, either right or left subset of candidate solution is discarded. In this example, if predicate function returns true, upper bound to be searched will be set to K. Else lower bound will be set to K+1.

Minimum number of pages to read  implementation

package com.company;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by sangar on 28.3.18.
 */
public class Books {
    public static boolean predicate(long[] books, long candidate, int days){

        long currentPages = 0;
        int studentRequired = 1;
        int i = 0;

        while(i<books.length){
            if(books[i] > candidate){
                return false;
            }
            if(currentPages + books[i] <= candidate){
                currentPages+=books[i];
                i++;
            }else{
                currentPages = 0;
                studentRequired++;
            }
        }
        return days >= studentRequired;
    }

    public static void main(String args[] ) throws Exception {
        Scanner scanner = new Scanner(System.in);

        int books = scanner.nextInt();
        int students = scanner.nextInt();

        long [] pages = new long[books];

        for(int i=0; i<books; i++){
            pages[i] = scanner.nextLong();
        }

        long low = 0;
        long high = Arrays.stream(pages).sum();

        while(low < high){
            long mid  = low + ( (high - low) >> 1);

            if(predicate(pages, mid, students)){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        System.out.println(low);
    }
}

Complexity of algorithm to find minimum number of pages will be O(sum of pages of all books).

More problems on similar lines

It’s very interesting to see how many problems can be solved using same approach. I solved one on Hacker Rank : BooBoo and upsolving

  public static boolean predicate(long[] time, long candidateTime, int days){

        long currentTime = 0;
        int daysRequired = 1;
        int i = 0;

        while(i<time.length){
            if(time[i] > candidateTime){
                return false;
            }
            if(currentTime + time[i] <= candidateTime){
                currentTime+=time[i];
                i++;
            }else{
                currentTime = 0;
                daysRequired++;
            }
        }
        return days >= daysRequired;
    }

    public static void main(String args[] ) throws Exception {
        Scanner scanner = new Scanner(System.in);

        int tasks = scanner.nextInt();
        int days = scanner.nextInt();

        long [] time = new long[tasks];

        for(int i=0; i<tasks; i++){
            time[i] = scanner.nextLong();
        }

        /* What will be the maximum time he has to practice?
        It will be when he has only one day and all problems needs to be solved.
        that will give us the upper bound of time.

        What will be minimum time required? When he has no problems to be solved.
        That will give us lower bound of time.

        Idea is to start with middle of lower and upper bounds.And see if all problems can be solved
        by practicing that amount of time each day. If yes, there is a possibility that it can be done
        in less than that, hence, we try to find reduce our search space from lower bound to mid. Should mid be included?

        If all problems can not be solved by practicing mid amount of time, then there is no way it can be done
        by practicing less. Hence we increase the time and start looking in mid+1 to higher bound
        */

        //first let's set lower and higher bound.
        long low = 0;
        long high = Arrays.stream(time).sum();

        while(low < high){
            long mid  = low + ( (high - low) >> 1);

            if(predicate(time, mid, days)){
                high = mid;
            }else{
                low = mid+1;
            }
        }

        System.out.println(low);
    }

Similar method can be applied to topcoder problem Fair Work, try it yourself, if are able to solve it, please drop code in comment.

Please share if there is something is wrong or missing. If you want to contribute to website and share your knowledge with learners, please write to communications@algorithmsandme.com.

 

Ceiling in sorted array using binary search

Ceiling in sorted array

In last post, binary search algorithm, we discussed basics of algorithm, it’s implementation and worst case complexity. Today, we will use binary search algorithm to solve another problem called find ceiling in sorted array. To understand problem, first let’s understand what is ceiling? Given an array of integer and element X, ceiling of X is the smallest element in array greater than or equal to X. For example in given array below, ceiling of 7 would be 9. It’s good to know that array is sorted array.

ceiling in sorted array

What will be the most simple solution? To scan through array and see for each index i, if key lies between A[i] and A[i+1] or is equal to A[i], return index i. Worst case complexity would be O(N). But then what’s the fun in solving problem in O(N) complexity!

Ceiling in sorted array : Thought Process

We know that array is sorted, which makes sure that if A[i]> key, all A[j] will also be greater than key for j <i. This helps us to discard some part of array.How?
If all A[j] are greater than key, it means that from i to end of array, minimum element which is greater than key will be A[i] or any element left of i. But surely not on the right side.

This seems like binary search, we split in mid and based on relation of mid with key, we either discard left or right part of array and focus on other. Whenever, you feel like binary search can be used to solve any problem, it’s good to prove that it will work.

Consider all possible solutions as a set S, any value in that set can be answer to problem. Now, let’s say we have a predicate which takes input from candidate set S. This predicate validates that candidate does not violet any condition given problem statement. Predicate function can return any value, for purpose of simplicity, in this article assume that it return true or false.

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

Why do I need this abstraction, when I can solve this problem with slight modification of binary search?  That’s true, but then you are not realizing the true power of binary search.  This is because many problems can’t be modeled as searching for a particular value, but it’s possible to define and evaluate a predicate such as “Is there an assignment which costs x or less?”, when we’re looking for some sort of assignment with the lowest cost.

How to find ceiling in sorted array with this method?

What will be our candidate solution set S in this problem? Since, we are looking for an array index which satisfy the condition, that it is smallest element greater than key, every index is in candidate set.
What is the predicate here?  Predicate is : if element at i is greater than key. If it is, predicate returns true else false.

Does the condition to apply binary search apply? If p(x) is true, then for all y>x>, p(y) is also true. So we can apply binary search on candidate set and find which is the least x, where predicate returns true.

Ceiling in sorted array : Implementation

package com.company;

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

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

        return false;
    }

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

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

            if(predicate(a, mid, key)){
                end = mid;
            }
            else{
                start = mid + 1;
            }
        }

        if(!predicate(a,start, key)) return -1;

        return  start;

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

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

    }
}

Important part of this implementation is to get lower and higher bounds of solution. In ceiling problem, lowest possible value is 0, first index of array and highest will be array length-1.  How to deal with mid index? Should it be included in any subarray? If yes, which left or right? Answer is it depends what are you looking for. In this example, if A[mid] > key, that is predicate(mid) is true, it is likely to be smallest element which is greater than key, so we must include it in left subarray partition.

high = mid;

However, if predicate(mid) is false, then mid is not required on right subarray.

low = mid+1;

To test that your implementation for any binary search application works, always test your code on a two-element set where the predicate is false for the first element and true for the second.

Complexity of this algorithm to find ceiling in sorted array is O(log N).

Learnings

This problem makes us understand that binary search is not limited to array indices, it can be applied to any discrete set which satisfy mentioned condition. Find, candidate solution set, predicate and make sure that predicate follows that p(x) implies p(y) for all y < x
In next few post, we will take problems from Top coder and SPOJ, and solve them using binary search.

Please feel free to drop us comment or email at communications@algorithmsandme.com if you find anything wrong or missing. If you are willing to write articles and share your knowledge with other learners, please drop us a message.

Binary search algorithm

Binary search algorithm

Binary search algorithm is very known algorithm and taught in basics of computer science algorithm class. It is simple algorithm however, it is very powerful one, can be used to solve many problems.  Classic example of application of binary search algorithm is searching of a word in dictionary.  What process do you follow? That’s exactly everything about BSA.

Let’s understand what is binary search algorithm in programming terms. Given a sorted array of integers, find a key or a number or an element in that sorted array.

Binary search algorithm : Thought process

Before coming up with any solution, first question is what should be output if key does not exist in array? What happens if there are duplicate integers in array, which index should be returned? May be it is good to as for data size, range and nature of data before rushing into any solution. Once, you have this information, you are better equipped to solve the problem right.

Assuming that you  have no knowledge of binary search algorithm, how would you that?

Brute force or simple method would be to go through all elements of array and compare them with key, once key matches any element, we return the index saying key was found at that index. Simple isn’t it? How many comparisons you have to make in worst case scenario? Yes, it will be equal to number of elements in array to be searched. In big O notation, worst complexity of brute force method will be O(N), which occurs when either searched key is not there in array at all or it is at the end of array.

How can we improve worst case complexity of simple search? What information given in problem statement we have not yet used? We did not consider the fact that array is sorted.

Second question is how can we use that information? Since array is sorted, we already know that for any element of array at index i, all elements on left of i, from start to i-1 will be smaller and all elements on right of i, from i+1 to end will be greater than it. But how does it help us?

In brute force solution, we started with first element and went all the way to last element comparing each one with key to be found. Can we start randomly from anywhere and see where would key to be found may be located in array based on condition described. Optimum solution would be to start from the mid.

Start at mid and see if A[mid] is what you are looking for? If yes, great! return mid. But if it not what you are looking for then key can be anywhere in array. How can you decide if you have to search in left part of mid or right part of array? That’s where sorted property of array comes to help! If A[mid] < key, that means,  key must not be before mid. So, we discard array[start..mid] and only look for key in remaining part of array that is A[mid+1..end].
Similarly, if A[mid] > key , key cannot be after mid, hence we can discard right subarray A[mid..end] and look for key in A[start..mid-1].

So when do we call that key is not present? When size of array goes less than one, where start > end, and we have not found the key, we can say that key is not present at all in the array.

Let’s take an example and see how it works! We have an array as shown below and we are looking for key 10:

First, find mid of array, it is index 4 = 0+9/2

Next, is A[mid] is equal to key? Nope. Is key greater than A[mid]? Yes. What do we do? We focus on the right part of array from mid and discard left subarray.

New start is index 5. Find mid of new reduced array, which will be 7 = ( 5 + 9 ) /2. Is A[mid] == key? No, is key greater than key? No, hence, discard right subarray and search in left subarray.

New end of array is 6 and start is 5. Find new mid which is 5. Is A[5] == key? No. Is key greater A[mid]? Yes, then discard left subarray and focus on right subarray.

At this point, end = start = 6, hence mid = 6. Is A[mid] == key? Yes, hence return mid index.

Hope this example made it clear how binary search algorithm works. Can you draw execution flow if key to be searched is let’s say 5?

Now that we have learned algorithm and solved couple of examples, it’s time to implement algorithm.

Binary search algorithm implementation

package com.company;

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

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

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

            /*Check if element at mid index
            element we are looking for? If yes, return mid*/
            if(a[mid] == key) return mid;

            /*
            If element at mid is not equal to key
            what is relationsip between A[mid] and key.
            If A[mid] > key, we look in left subarray
            else we look into right subarray
             */
            if(a[mid] > key){
                end = mid-1;
            }else{
                start = mid+1;
            }
        }
        return -1;
    }

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

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

    }
}

Recursive implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {
    public static int binarySearchRecursive(int[] a, int start, int end, int key){

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

            /*Check if element at mid index
            element we are looking for? If yes, return mid*/
            if(a[mid] == key) return mid;

            /*
            If element at mid is not equal to key
            what is relationsip between A[mid] and key.
            If A[mid] > key, we look in left subarray
            else we look into right subarray
             */
            if(a[mid] > key){
                return binarySearchRecursive(a,start, mid-1, key);
            }else{
                return binarySearchRecursive(a,mid+1, end, key);
            }
        }
        return -1;
    }

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

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

    }
}

What will be complexity of binary search  algorithm? It is O(log N). Please follow this link to understand more how does it happen.
Worst case complexity of binary search tree

It’s also important to explain that recursive implementation takes more space than it seems. Since, each function call puts a stack frame on stack, it will take O(log N) stack frames. So, when you are dealing with huge chunk of data in production, go for iterative implementation rather than recursive.

Also, it is important to understand that it makes a huge difference when you use BSA to find a key in array, which becomes more and more evident as data size grows. To look for a key in 1 billion integers, simple search would take 1 billion comparisons where as binary search will take only 32 comparisons.
If you want to learn more tricks to find mid so that case where start and end are very big numbers, read Google Reasearch on this topic.

Please share if there is anything wrong or missing.If you want to contribute to website and share your knowledge with learners, please write to us at communications@algorithmsandme.com.

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.

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