Ship capacity problem

There are some problems which do not appear to be a binary search problem at first. For example, ship capacity problem on leetcode. Problem statement is:
A conveyor belt has packages that must be shipped from one port to another within D days.
The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

For example:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed. 

Ship capacity problem and binary search algorithm

At first glance, it does not appear to be a binary search problem. Where is the input we will search on? That’s where we have to remember that to apply a binary search, we actually do not need an input set, all we need is lower and upper bound.

Hint 1
What is the minimum capacity you would need to ship this cargo? You can choose the lowest possible capacity if you infinite number of days to ship all weights.

Hint 2
What if you have only one day to ship all the weights? In that case, what will be the capacity of the ship? Do you need more than capacity ever?

To find these bounds, try to vary the constraint to extremes. In the example of ship capacity, try to put the number of days constraints to an extreme. What if we had an infinite number of days to ship the cargo?

Can you please explain more?
In that case, we will need a ship that has at least capacity greater than equal to the heaviest weight cargo, as no matter how many days, we cannot move the cargo.

Again, what if I had only 1 day to ship the whole cargo? In that case, we need a ship that can take all the weights in 1 day, so ship capacity should be the sum of all the weights.

Now, we know the lower and upper bound of the ship, all we have to adjust the capacity and see if we can ship cargo in D days? Start with mid, see if we can. If yes, then try a smaller capacity. If not, then try greater capacity. All we are doing is find the first capacity between lower and upper bounds. It seems like the first occurrence problem now.

Understood the concept, you still need help with implementation? Please see the code below.

Ship capacity problem implementation

    public int shipWithinDays(int[] weights, int D) {
        
        int upperLimit = 0;
        int lowerLimit = 0;
        
        for(int i = 0; i<weights.length; i++){
            upperLimit+= weights[i];
        }
        //Not returning from while loop :)
        while(lowerLimit < upperLimit){
            int shipCapacity = lowerLimit + (upperLimit - lowerLimit)/2;
            
            if(isItPossible(D, shipCapacity, weights)){
                upperLimit = shipCapacity;
            }
            else{
                lowerLimit = shipCapacity + 1;
            }
        }
        
        return lowerLimit;
        
    }
    
    private boolean isItPossible(int D, int shipCapacity, int[] weights){
        
        int currentLoad = 0;
        int days = 1;
        int i = 0;
        
        while(i<weights.length){
            if(weights[i] > shipCapacity) return false;
            
            currentLoad+= weights[i];
            if(currentLoad == shipCapacity){
                days++; i++;
                currentLoad = 0;
            }
            else if(currentLoad > shipCapacity){
                days++;
                currentLoad = 0;
            }
            else{
                i++;
            }
        }
        
        return days <= D;
    }

The time complexity of the solution is O(nlogc) where n is number of weights and c is capacity range.

Please share if you find anything wrong or missing. If you are looking for coaching to prepare for your technical interviews, please book a free session with us.

Keep an eye on the binary search algorithm

What is binary search algorithm

A classic example of the application of the binary search algorithm is searching for a word in a dictionary, or when you open a page in a book. The process you follow depends on two things: first, you know that words in the dictionary or pages in the book are in sorted order; second, you know what is the lower bound and upper bound of search space? The word you are looking for should start with A to Z or page you are looking for should be between the first page and the last page of the book.

If it is a sorted range of items and you know the upper and lower bound of your result, think binary search algorithm

Most important fact to know about binary search is that it reduces search complexity from linear O(n) to logarithmic O(log n).

A typical iterative implementation of the binary search algorithm looks like below. To understand more how it exactly works in details, follow this post on it.

    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 the element at mid is not equal to key
            what is the relationship 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;
    }
How can you test your binary search implementation? Always dry run your code against an array of size 1 and 2. See if your code works for these cases properly? If it does, it will work for the rest of the cases as well.

A log of candidates get confused when to return from the while loop, should it be start < end or should it be start <= end Here is the rule of thumb for this:

If you are returning within the while loop (like in above case), use start<=end, if you are not returning from while loop, use start < end (like first occurrence and last occurrences )

Whenever you have identified a problem to be a binary search problem, just go ahead and write down the template code above first and then do the modifications. Another thing you should consider is should mid be included in subproblem or should it be discarded. In the implementation of plain binary search, if A[mid] is not equal to key, mid is no more a candidate, whereas in first instance problem, mid remains candidate in left part of the search.

1. Last occurrence of an element in a sorted array

    public int findLastOccurrence (int[] a, int key) {
        return findLastOccurrence(a, 0, a.length-1, key);
    }
    private int findLastOccurrence (int[] a, int start, 
                                 int end, int key){
      /*We do not return from the while loop
       start is less than end */
        while(start < end){
            /* Notice that we have + 1 to move start
                 in case there are only two elements left
             */

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

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

2. Find the ceiling of a number in a sorted array

private int findCeiling (int[] a, int start,
                             int end, int key){

      /*We do not return from the while loop
       start is less than end */
        while(start < end){
            int mid = start + ((end - start)) / 2;

            if(a[mid] < key){
                start = mid + 1;
            }
            else{
                end= mid;
            }
        }

        return start;
    }

Binary search and sorted rotated array

One pattern of the binary search algorithm that is usually asked in interviews is sorted rotated array. Given a sorted rotated array, find the pivot or find the minimum in that array or find an element in it.

Key to apply binary search on a sorted rotated array is that if you split it in the middle, at least one part will be sorted.

Compare the middle element with the end of the array and you know which part is sorted. If A[mid] < A[end] then right part is sorted and if A[mid] > A[end] then left part is sorted. Based on this information, we can check if the key falls in the sorted part if not, the look in the unsorted part.

Find an element in sorted rotated array

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

       //Returning within while loop, so start<=end
        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;
    }

Minimum in a sorted rotated array

    public int findMinimum (int[] a) {
        return findMinimum(a, 0, a.length-1);
    }
    
    private int findMinimum (int[] a, int start,
                             int end){
        while (start < end) {
            int mid = start + (end - start) / 2;

            /* Check if left part of the array is sorted
             or the right part */
            if (a[mid] < a[end]) {
                /*If left part is sorted,
                  then minimum cannot be on
                  the right side of mid,
                  but mid still can be.
                 */
                end  = mid;
            } else {
                start  = mid+1;
            }
        }
        return start;
    }

Binary search and invisible input range

There are some problems which do not appear to be a binary search problem at first. For example, ship capacity problem on leetcode. At first glance, it does not appear to be a binary search problem. Where is the input we will search on? That's where we have to remember that to apply a binary search, we actually do not need an input set, all we need is lower and upper bound.
How can we find the lower and upper bound of ship capacity?

To find these bounds, try to vary the constraint to extremes. In the example of ship capacity, try to put the number of days constraints to an extreme. What if we had an infinite number of days to ship the cargo?

In that case, we will need a ship that has at least capacity greater than equal to the heaviest weight cargo, as no matter how many days, we cannot move the cargo.

Again, what if I had only 1 day to ship the whole cargo? In that case, we need a ship that can take all the weights in 1 day, so ship capacity should be sum of all the weights.

Now, we know the lower and upper bound of the ship, all we have to adjust the capacity and see if we can ship cargo in D days? Start with mid, see if we can. If yes, then try a smaller capacity. If not, then try greater capacity. All we are doing is find the first capacity between lower and upper bounds. It seems like the first occurrence problem now.

    public int shipWithinDays(int[] weights, int D) {
        
        int upperLimit = 0;
        int lowerLimit = 0;
        
        for(int i = 0; i<weights.length; i++){
            upperLimit+= weights[i];
        }
        //Not returning from while loop :)
        while(lowerLimit < upperLimit){
            int shipCapacity = lowerLimit + (upperLimit - lowerLimit)/2;
            
            if(isItPossible(D, shipCapacity, weights)){
                upperLimit = shipCapacity;
            }
            else{
                lowerLimit = shipCapacity + 1;
            }
        }
        
        return lowerLimit;
        
    }
    
    private boolean isItPossible(int D, int shipCapacity, int[] weights){
        
        int currentLoad = 0;
        int days = 1;
        int i = 0;
        
        while(i<weights.length){
            if(weights[i] > shipCapacity) return false;
            
            currentLoad+= weights[i];
            if(currentLoad == shipCapacity){
                days++; i++;
                currentLoad = 0;
            }
            else if(currentLoad > shipCapacity){
                days++;
                currentLoad = 0;
            }
            else{
                i++;
            }
        }
        
        return days <= D;
    }

If you are looking for more problems on this concept, follow number of pages to read problem

Please share if there is any issue or mistake in the post. We provide coaching to prepare you for an interview, we explain concepts, problems, tips, and tricks to master in an interview. If you are interested in such coaching, please book a session with us.

Number of occurrences of element

Number of occurrences of element

Given a sorted array and a key, find the number of occurrences of a key in that array. For example, in the below array, the number of occurrences of 3 is 3.

number of occurrences of element

Brute force method will be to scan through the array, find the first instance of an element and then find the last instance, then do the math. The complexity of that method is O(N). Can we do better than that?

Did you get some hint when brute force method was described? Yes,we have already cracked the problem to find first occurrence and last occurrence in O(log n) complexity earlier. We will be using those two methods, all we need to do know is math.

occurrences = lastInstance - firstInstance + 1

Number of occurrences of element : 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;
    }

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

        return false;
    }

    private int findFirstOccurance(int[] nums, int target){
        int start = 0;
        int end = nums.length-1;
        
        while(start<end){
            int mid =  start + (end-start)/2;
            
            if(if(isGreaterThanEqualTo(nums, mid, target)){){
                end = mid;
            }
            else{
                start = mid+1;
            }
        }
        return start < nums.length && nums[start] == target ? start : -1;
    }
    
    private int findLastOccurance(int[] nums, int target){
        int start = 0;
        int end = nums.length-1;
        
        while(start<=end){
            int mid =  start + (end-start)/2;
        
            if(isLessThanEqualTo(nums, mid, target)){
                start = mid+1;
            }
            else if(nums[mid] > target){
                end = mid-1;
            }
        }
        return end >= 0 && nums[end] == target ? end : -1;
    }

    public  static  int numberOfOccurrences(int[] a, int key){
        int firstInstance = findFirstOccurance(a, key);
        int lastInstance = findLastOccurance(a, key);

        return (firstInstance != -1) ? lastInstance-firstInstance + 1 : 0;
    }

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

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

    }
}

The worst case time complexity of the algorithm to find the number of occurrences of an element in a sorted array is O(log n). We are using the iterative method to find the first and last instances, therefore, there is no hidden space complexity of the algorithm.

You can test the code at leetcode
Please share if there is something wrong or missing. Also if you want to contribute to algorithms and me, please drop an email at [email protected]

Last occurrence element in array

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

first and last occurrence of x

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

Binary search and last occurrence

One property of input array we did not use in brute force solution is the array being sorted. The de facto for searching in a sorted array is, of course, binary search algorithm. If there are no duplicates in the array it will be super easy to find the last occurrence using binary search, how can we modify it to solve a problem with duplicates.

The first question you should ask yourself is: What is the candidate solution set? In simple terms, what can be a valid answer if the key is a part of the input array? Also, think about the case when a key is not present at all.

If the key is present, the candidate answer will be one of the indices. Range of indices is from 0 to array.length -1. We learned a concept when solving to find a greater or equal number or ceiling in a sorted array. The concept was: we can apply binary search to any set of inputs where the 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[i] is less than or equal to the key, then all the A[y] will be less than or equal to A[i] where y < i, which satisfies our condition to apply binary search.

This means that when predicate returns true, which is: element equal or less than the key, there is no point looking into left subarray, as all elements will be less than or equal to key. The last occurrence of the key can not be less than the current index. Hence, discard Array[start, i-1] and look in the right side of array, Array[i, end].
What should the start point be for index u? Obviously, it will be the middle index in the left part of the array. Based on if predicate(mid) is true or false, we discard left or right half of array.

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

Last index of number using recursion: Example

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

last index of number using recursion

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

binary search first and last occurrence

first and last occurrences of x

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

python find last occurrence in list

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

At this point, there is only one element left in the candidate set. Is it equal to the 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 the array)? Does the algorithm work for those cases?

Last occurrence of x in a sorted array

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 (end >=0 && a[end] == key) ? end : -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);
    }
}

The same method can be implemented recursively as follow

Find last occurrence of x recursive implementation
public static int findLastOccurrence Recursive(int[] a, int start, int end, int key){

    if(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 (end >=0 && a[end] == key) ? end: -1;
}

Worst-case complexity to find the last occurrence of element in a 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 a binary search. We learned how a solution depends on the candidate solution set. How can we discard some parts of that set based on constraints in the problem? For example, in this problem, candidate set was all indices of an array, but based on constraint that element should be equal to key, half of those indices were discarded.
Remember to check the last element for constraints of the problem, if matches, then it is a solution, else there is no solution.

I 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 [email protected]

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 [email protected]

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 [email protected]

 

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 [email protected] 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

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

Let’s understand what is a 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, the first question is what should be output if a key does not exist in array? What happens if there are duplicate integers in array, which index should be returned? Maybe 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 an array and compare them with key, once key matches any element, we return the index saying the key was found at that index. Simple isn’t it? How many comparisons you have to make in the worst-case scenario? Yes, it will be equal to the number of elements in array to be searched. In big O notation, the worst complexity of the 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 an array.

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

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

In a brute force solution, we started with the first element and went all the way to the 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 an array based on condition described. The optimum solution would be to start from 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 the left part of the mid or right part of the 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 the 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 the 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.

The 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.

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

Now that we have learned algorithms and solved a couple of examples, it’s time to implement the 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 the element at mid is not equal to key
            what is relationship 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 the element at mid is not equal to key
            what is relationship 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 the complexity of the 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 a 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 an array, which becomes more and more evident as data size grows. To look for a key in 1 billion integers, a simple search would take 1 billion comparisons whereas 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 the website and share your knowledge with learners, please write to us at [email protected]

Longest Increasing Subsequence in O(nlogn)

In the last post, longest increasing subsequence, we discussed brute force and dynamic programming based solutions. The complexity of the brute force solution is exponential whereas for the dynamic programming approach it is O(n2). Question is – Can we find the longest increasing subsequence in O(nlogn) complexity?

Let’s revisit the problem statement: Given an array of integers, find the length of the longest increasing subsequence. An increasing subsequence contains elements A[i] and A[j] only if i < j and A[i]A[j].
For example,

Input:
[2,4,5,3,1,6,7], 
Output:
5
Explanation:
The increasing subsequences are [2,4,5,6,7], [2,3,6,7], [1,6,7] and many more. The longest subsequence here has a length of 5.

The basic idea behind the solution is to keep track of all active subsequences at a given point in time. Based on the current number being considered, update these active lists. To understand this process, let’s work out an example.

A = {2,8,7}
Monotonically increasing subsequences are {2,8} and {2,7}

What if we add another element, 11 in this?

A = {2,8,7,11}
Monotonically increasing subsequences are {2,8,11} and {2,7,11}

What if new element 9 is added to array? What happens now? If we add it t0 subsequences, the length of the longest subsequence remains 3.

A = {2,8,7,11,9}
Monotonically increasing subsequences are {2,8,9} and {2,7,9}

The decision to take for each element being considered is whether we create new active subsequences with length 3 with element 9 in them or continue with 11. If the next element is 10 we know that adding 9 to subsequence leads us to longer subsequences rather than keeping 11.

How do we decide when to replace and when to continue with the old element in the list of subsequences?
We add a new number A[i] to the sequence if A[i] > E, E is the last element in subsequence
and replace an number with A[i], if there exists a number A[j] such that if E > A[i] < A[j], it means, the new number falls somewhere between A[j] and E.

What if A[i] is smaller than all elements in the present list of subsequences? In this case, we have to create a new list and add A[i] into it. The invariant is to maintain lists of increasing sequences and update them based on the next number.
Each time a new element is to be added, scan all the lists of subsequences in decreasing order of their length. The following algorithm shows how to add/replace the new elements in the existing lists or to create a new list with it.

1. If A[i] is the smallest among all end candidates of active lists, start a new active list with A[i] of length 1.
2. If A[i] is largest among all end candidates of active lists, clone the largest active list, and append A[i] to it.
3. If A[i] is in between, find the list with the largest end number that is smaller than A[i]. Clone and append A[i] to this list.
4. Discard all other lists of the same length as that of this modified list.

LIS in nlogn example

Let’s take an example and see how it works with an array A = [ 0, 8, 4, 12, 2, 10, 6, 14].

For A[0], there are no active lists of subsequences, we will create a new one.
longest increasing subsequence in logn

Next, we go to A[1] which is 8. A[i] is greater than the ends of all the current lists, we will take the longest one and append A[1] to it.
longest increasing subsequence in logn

For A[2] with value 4, A[i] is less than the end of one of the list and greater than the end of other. We will find the list which has end less than A[i], in this case, the first list containing [0]. Clone it and append A[2] to it and discard all other lists of the same length.

For A[3] with value 12, it is the same case as A[1] since it is greater than all the ends of the current lists, we will clone the longest available list and append it to that.

A[4] with value 2, it has the same case as A[2], Clone the one with largest end which is less than A[4], append A[4] to it and discard all same length lists.

A[5] with value 10. Same as A[4]. Clone, extend, and discard all the same length subsequences.
Lists = [ [0], [0, 2], [0,2,10] ] and [0, 4, 12] is discarded.

A[6] is 6. Same as A[5] We will clone the list which has end smaller than A[6], extend it, and discard all other lists which have the same length.
Lists = [ [0], [0, 2], [0,2,6] ] and [0, 2, 10] is discarded.

Following the same approach, we will go through all the numbers in the given array. The longest increasing subsequence in the given array is [ 0,2,6,14] with a length of 4.
lis in nlogn

It seems like a lot of things need to be done just for maintaining the lists and there is significant space complexity required to store all of these lists. We can optimize on this, observe that we use only ends of the list and their sizes. We do not care what was prior to them in list. So, can we store the ends of all the lists of an auxiliary array and do operations on them? Size of this array in worst case will be n.

To append to the list, add another element in the auxiliary array. To replace just overwrite the smallest number which is greater than the current number. To find the smallest number which is greater than the current number, we can use binary search algorithm.

To find the length of the longest subsequence, keep track of the length of the auxiliary array because this will be the length of LIS.

Show me implementation of longest increasing subsequence in O(nlogn)

    public int lengthOfLIS(int[] nums) {
        
        if(nums == null || nums.length == 0) return 0;
        
        int [] dp = new int[nums.length]; 
        int len = 0;
        
        for(int num : nums){
            int index = Arrays.binarySearch(dp, 0, len, num);
            
            if(index < 0)
                index = -(index+1);
            dp[index] = num;
            
            if(index == len)
                len++;
        }
        
        return len;
    }

The complexity of this algorithm is O(nlogn) as for each element in the array, it requires O(logn) time to find the ceiling of it and put it at the correct position.

This article has taken some inspiration from: http://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn and the comments provided by readers under these articles.

What are the problems you can solve with the longest increasing subsequence?
1. Russian doll envelopes.
2. Box stacking problem.
3. Bridges across the river.

Please share if you find something wrong or missing. Also, if you want to contribute to the website, please refer to Publishing and contact us. We would love to publish your article and at the same time, will pay you too.