Spiral traversal of a matrix

Given a 2d matrix of dimension n*m, the task is to print the matrix in spiral order. (To understand what is spiral order please refer to the diagram) For example:

Input:
3 3
1 2 3
4 5 6
7 8 9

Output: 
1 2 3 6 9 8 7 4 5

Explanation: The below diagram clearly shows the order of printing to be followed.

Spiral traversal of a matrix thought Process

1. The number of elements to be printed is n*m. We will maintain a count variable to keep track of the number of elements printed till now.

2. There are four directions in which we need to print the elements as shown below. The numbering indicates the order of printing.

3. For each direction, we need start and end to print the elements. Let’s maintain four variables, row, col, rowe, cole.

row = row starting index
col = column starting index
rowe = row ending index
cole = col ending index

Let, row = 0, col = 0, rowe = 2, cole = 2, After handling any row or column, we need to update the variables.

4. To handle rows like this,
Spiral traversal of a matrix

We will print elements from col to cole i.e, [0,2] with the row being fixed. After printing each row, we will update the row to row + 1.
Now, row = 1
5. To handle column like this,

Spiral traversal of a matrix

We will print elements from row to rowe i.e, [1,2] with cole being fixed. After printing each column, we will update the cole to cole – 1. Now, cole = 1

6. To handle rows like this,

We will print elements from cole to col i.e, [1,0] with the row being fixed. After printing each row, we will update the rowe to rowe – 1. Now, rowe = 1

7. To handle columns like this,

We will print elements from row to rowe i.e, [1,1] with col being fixed. After printing each column, we will update the col to col + 1.
Now, col = 1

Points 4,5,6,7 explains four operations. These four operations need to be performed in a loop until the number of elements printed reaches n*m. As soon as printed elements reach n*m, break out of the loop.

Any corner cases or where you can make mistakes? Yes. Take care of the cases where the number of rows is 0 and check whether the number of printed elements reaches n*m or not in every loop.

The code is given below:

public class Solution {

    public static void spiralPrint(int a[][]){
        
        int n = a.length;
        
        if(n == 0)
            return;
        
        int m = a[0].length;
        
        int count = n*m;
        int num = 0;
        
        int row = 0, col = 0;
        int rowe = n-1, cole = m-1;
        
        while(num < count)
        {
         // step 4
            for(int i = col; i <= cole && num < count; i++)
            {
                System.out.print(a[row][i] + " ");
                num++;
            }
            row++;
           // step 5 
            for(int i = row; i <= rose && num = col 
                        && num = row && num < count; i--)
            {
                System.out.print(a[i][col] + " ");
                num++;
            }
            col++;
        }

    }
}


The time complexity of the implementation is O(n*m) as we are doing constant work on every index whereas space complexity is O(1) as no extra space is used.

This article is contributed by Mukul, if you also contribute to Algorithms and Me, please check out our publisher’s program.

Plus One Linked List

Given a number represented by a linked list, add 1 to that number and return a new linked list. For example, if the number is 2345, then it is represented as linked as shown below.

plus one linked list

When we add one to 2345 represented by the linked list, the resulting linked list looks as follows.

add 1 to linked list

Thought process

First of all, think if there is only one node in the linked list, that means the linked list represents a single-digit number. What will do? We will add 1 to the node.val and return a new node with the sum. This is our smallest case, however, there is a catch here as well. What if the single-digit number is 9. In that case, the sum is 10 and since every node contains only a single digit of the number, we can store 0 in the new node. What happens to 1? We can treat that 1 as a carry.
Now, there are no digits present to add carry to (remember we had only one node linked list), we will create a new node and put carry in that and then linked the carry node to the previous node with 0.

add one to linked list

This is a very important case which we learned here. When you have processed all the nodes of the linked list, if the carry remains, create a new node and attach it to the head of the list. Most of the students make a mistake in this case.

How about when there is more than one node in the linked list? In that case, 1 is added to the node in the end and carry is propagated, if any, backward till head. Next question, how can you process the last node of the linked list and move backward? Well, remember how we print a linked list in the reverse order. We go deep in the linked list till the last node and use recursion unfolding to come backward. We can use the same concept. Go to the last node recursively, maintain a carry and move backward till the head. Once, you have processed head node, check if carry is non zero, if it is, creates a new node and attach it at front.

plus one linked list

plus 1 in linked list

Show me the implementation

package AlgorithmsAndMe;

import java.util.List;

public class PlusOne {
    int carry = 0;


    public ListNode addOneToLinkedList(ListNode head){
        ListNode newList = addOneToLinkedListUtil(head, 1);

        if(carry > 0){
            ListNode newNode = new ListNode(carry);
            newNode.setNext(newList);
            return newNode;
        }
        return newList;
    }

    public ListNode addOneToLinkedListUtil(ListNode head, int val){

        if(head == null) return null;

        if(head.getNext() == null){
            return createNode(head, val);
        }

        ListNode returnedNode = 
             addOneToLinkedListUtil(head.getNext(), val);

        ListNode newNode = createNode(head, carry);
        newNode.setNext(returnedNode);

        return newNode;
    }

    private ListNode createNode(ListNode node, int val){
        int newVal = node.getValue() + val % 10;
        carry = (node.getValue() + val) / 10;

        return new ListNode(newVal);
    }
}

The complexity of the code is O(n), we will be processing each node at least once. The tricky part is space complexity, as recursion takes implicit stack memory, the space complexity is also O(n).
This code creates a new node, what if we new list does not have to be created and we have to return the same list back. The below code implements the PlustOne such that it returns the same list back.

package AlgorithmsAndMe;

import java.util.List;

public class PlusOne {

    public ListNode addOneToLinkedList2(ListNode head){
        int c = addOneToLinkedListUtil2(head);

        if(carry > 0){
            ListNode newNode = new ListNode(carry);
            newNode.setNext(head);
            return newNode;
        }
        return head;
    }

    public int addOneToLinkedListUtil2(ListNode head){

        if(head == null) return 1;
        int sum = head.getValue() 
                      + addOneToLinkedListUtil2(head.getNext());
        head.setVal(sum % 10);

        return sum / 10;
    }
}

In the next post, we will look at how to add two numbers represented by two linked lists.

If you are preparing for interview and looking for personalized coaching, please reach out to us on [email protected] or book a free session with us.

Combination sum problem

Combination sum problem

Given an array of integers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Also, the same candidate can occur in the combination multiple times.

For example, Input: candidates = [4,3,5,9], target = 9, a solution set is:[ [9], [3,3,3], [4,5]]

How can do we go about it? What happens if I take the coin 4 in the current example? Then all need to find in the candidates array if there is a combination adds up to 9-4 = 5. It seems like a recursion. For recursion, we need a termination condition. In this case, if I have on candidates to add and target is greater than zero, then whatever combination I have till now has no value, so I terminate the recursion in this case.

Second what if I have already found a combination that adds up to target? Then I will put that combination in the list of combinations and return.

What happens in recursive implementation? Well, we go through each coin, add that to the current combination and see if leads to the target? If it does, it will be added to the result list along with the list of other candidates. If not, we just remove the current coin (backtrack) from the current combination and try the next coin.

This approach is called the exhaustive search and backtracking paradigm of problem-solving where you search the entire input set to see to find the answer. However, in this case, we can prune the search path as soon as we know that the current set of candidates add up more than the target.

Combination sum : implementation

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates,
                                              int target) {
        /* The result list contains all the combination 
           which add up to target.
        */
        List<List<Integer>> result = new ArrayList<List<Integer>> ();
        
        //We start with the first coin and search exhaustively.
        combinationSumUtil(candidates,
                           target,
                           result,
                           new ArrayList<Integer>(),
                            0
        );
        
        return result;
        
    }
    
    public void combinationSumUtil(int[] candidates, 
                                  int target,
                                  List<List<Integer>> result,
                                  List<Integer> current, 
                                  int index){
        
        /* 
           First termination condition: if there are no coins left
           and required target is more than zero.
        */
        if(target > 0 && index == candidates.length){
            return;    
        }

        /* 
           Second termination condition: if target is zero,
           we can add the current combination to the result
        */
        if(target == 0 && index < candidates.length){
            result.add(new ArrayList<>(current));
            return;
        }
        
        /* 
           Start from the current index, and go through
           all the coins.
        */
        for(int i=index; i<candidates.length; i++){
            /* 
               This is where we prune the branches 
               of our exhaustive search
            */
            if(target - candidates[i] >=0){
                current.add(candidates[i]); // add to the list
                combinationSumUtil(candidates, 
                                   target-candidates[i],
                                   result, current, i);
                
                /* Remove the candidate from the list and 
                   check other combinations.
                */  
                if(current.size() > 0)
                    current.remove(current.size()-1);
            }
        }
        
    }
}

The time complexity is C(n,1) + C(n,2) + … + C(n,n) = 2^n – C(n,0) = O(2n).

The beauty of this solution is that it works with negative candidates as well, where the Dynamic programming solution for it may not work.

Maximum area rectangle in a histogram

A histogram is a diagram consisting of rectangles whose area is proportional to the frequency of a variable and whose width is equal to the class interval. Below is an example of a histogram.

maximum area rectangle in histogram

Given a histogram, whose class interval is 1, find maximum area rectangle in it. Let me explain the problem in more details.

In the histogram above, there are at least 6 rectangles with areas 2, 1,5,6,2, and 3. Are there more rectangles? Yes, we can make more rectangles by combining some of these rectangles. A few are shown below.

Apparently, the largest area rectangle in the histogram in the example is 2 x 5 = 10 rectangle. The task is to find a rectangle with maximum area in a given histogram. The histogram will be given as an array of the height of each block, in the example, input will be [2,1,5,6,2,3].

Maximum area rectangle: thoughts

First insight after looking at the rectangles above is: block can be part of a rectangle with a height less than or equal to its height. For each block of height h[i], check what all blocks on the left can be part of a rectangle with this block. All the blocks on the left side with a height greater than the current block height can be part of such a rectangle.
Similarly, all the blocks on the right side with a height greater than the current block height can be part of such a rectangle.
Idea is to calculate leftLimit and rightLimit and find the area (rightLimit - leftLimit) * h[i].
Check if this area is greater than previously known area, then update the maximum area else, continue to the next block.

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        if(heights.length == 0) return 0;
        int maxArea = Integer.MIN_VALUE;

        for(int i=0; i<heights.length; i++){
            //Find the left limit for current block
            int leftLimit = findLeftLimit(heights, i);

            //Find the right limit for current block
            int rightLimit = findRightLimit(heights, i);

            int currentArea = (rightLimit - leftLimit-1) * heights[i];
            maxArea = Integer.max(maxArea, currentArea);
        }

        return maxArea;
    }

    private int findLeftLimit(int [] heights, int index){
        int j = index-1;
        while (j >= 0 && heights[j] >= heights[index]) j--;

        return j;
    }

    private int findRightLimit(int [] heights, int index){
        int j = index+1;
        while (j < heights.length && heights[j] >= heights[index])
            j++;

        return j;
    }
}

The time complexity of the implementation is O(n2); we will left and right of each block which will take n operations, we do it for n blocks and hence the complexity is quadratic. Can we optimize the time complexity?

If heights[j] >= heights[i] and leftLimit of index j is already known, can we safely say that it will also be the leftLimit of index i as well?
Can we say the same thing for rightLimit well? Answers to all the questions are yes. If we store the left and right limit for all indices already seen, we can avoid re-calculating them.

class Solution {
    public int largestRectangleArea(int[] heights) {
        
        if(heights.length == 0) return 0;

        int maxArea = Integer.MIN_VALUE;

        //Finds left limit for each index, complexity O(n)
        int [] leftLimit = getLeftLimits(heights);
        //Find right limit for each index, complexity O(n)
        int [] rightLimit = getRightLimits(heights);

        for(int i=0; i<heights.length; i++){
            int currentArea = 
                (rightLimit[i] - leftLimit[i] -1) * heights[i];
            maxArea = Integer.max(maxArea, currentArea);
        }

        return maxArea;
    }

    private int[] getLeftLimits(int [] heights){

        int [] leftLimit = new int[heights.length];
        leftLimit[heights.length-1] = -1;

        for(int i=0; i<heights.length; i++) {
            int j = i - 1;
            while (j >= 0 && heights[j] >= heights[i]) {
                j = leftLimit[j];
            }
            leftLimit[i] = j;
        }
        return leftLimit;
    }

    private int[] getRightLimits (int [] heights){

        int [] rightLimit = new int[heights.length];
        rightLimit[heights.length-1] = heights.length;

        for(int i=heights.length-2; i>=0; i--){
            int j = i+1;
            while(j<heights.length 
                      && heights[j] > heights[i]){
                j = rightLimit[j];
            }
            rightLimit[i] = j;
        }
        return rightLimit;
    }
}

The array leftLimitcontains at index i the closest index j to the left of i such that height[j] < height[i]. You can think about each value of the array as a pointer (or an arrow) pointing to such j for every i. How to calculate leftLimit[i]? Just point the arrow one to the left and if necessary just follow the arrows from there, until you get to proper j. The key idea here to see why this algorithm runs in O(n) is to observe that each arrow is followed at most once.

Largest area rectangle: stack-based solution

There is a classic method to solve this problem using the stack as well. Let’s see if we can build a stack-based solution using the information we already have. Let’s we do not calculate the area of the rectangle which includes the bar when we are processing it. When should we process it? Where should this bar be put on? If we want to create a rectangle with a height of this bar, we should find the left and right boundaries of such a rectangle. We should put this bar on a stack.
Now when you are processing bar j if height[j] is less than the bar on the top of the stack, we pop out the bar at the top. Why? Because this is the first bar on the right which has a height less than the height of the bar at top of the stack. This means if we want to make a rectangle with a height of the bar at the top of the stack, this index means the right boundary. This also gives away that all the blocks on the stack are in increasing order, as we never put a block which has a height less than the height of block at the top on to the stack. It means the next bar on the stack is the first bar which has a height lower than the bar at the top. To calculate the area of the rectangle with height as h[top], we need to take width as current index j - stack.peek() - 1

So the idea is that:

  1. For each bar, take its height as the rectangle’s height. Then find the left and right boundaries of this rectangle.
  2. The second top bar in the stack is always the first bar lower than the top bar on the stack on the left.
  3. The bar that j points to is always the first bar lower than the top bar in the stack on the right.
  4. After step 2 and 3, we know the left and right boundaries, then know the width, then know the area.
private int maxAreaUsingStack(int[] heights){

        Stack<Integer> s = new Stack<>();

        int maxArea = 0;
        for(int i=0; i<=heights.length; i++){
            //Handling the last case
            int h = i == heights.length ? 0 : heights[i];
            while(!s.empty() && h < heights[s.peek()]){
                int top = s.pop();
                int leftLimit = s.isEmpty() ? -1 : s.peek();
                int width = i-leftLimit-1;

                int area = width * heights[top];
                maxArea = Integer.max(area, maxArea);
            }
            s.push(i);
        }
        return maxArea;
    }
The time complexity of the code is O(n) with an additional space complexity of O(n) If you are preparing for a technical interview in companies like Amazon, Facebook, etc and want help with preparation, please register for a coaching session with us.

Segregate 0s and 1s in an array

Given an array of 0s and 1s, segregate 0s and 1s in such as way that all 0s come before 1s. For example, in the array below,

segregate 0s and 1s in an array

The output will be as shown below.

segregate 0s and 1s in an array

This problem is very similar to Dutch national flag problem

Different methods to segregate 0s and 1s in an array

Counting 0s and 1s.
The first method is to count the occurrence of 0s and 1s in the array and then rewrite o and 1 onto original array those many times. The complexity of this method is O(n) with no added space complexity. The only drawback is that we are traversing the array twice.

package com.company;

/**
 * Created by sangar on 9.1.19.
 */
public class SegregateZerosAndOnes {

    public void segregate(int[] a) throws IllegalArgumentException{

        if(a == null) throw new IllegalArgumentException();
        int zeroCount = 0;
        int oneCount = 0;

        for (int i = 0; i < a.length; i++) {
            if (a[i] == 0) zeroCount++;
            else if (a[i] == 1) oneCount++;
            else throw new IllegalArgumentException();
        }

        for (int i = 0; i < zeroCount; i++) {
            a[i] = 0;
        }

        for (int i = zeroCount; i < zeroCount + oneCount; i++) {
            a[i] = 1;
        }
    }
}

Using two indices.
the second method is to solve this problem in the same complexity, however, we will traverse the array only once. Idea is to maintain two indices, left which starts from index 0 and right which starts from end (n-1) where n is number of elements in the array.
Move left forward till it encounters a 1, similarly decrement right until a zero is encountered. If left is less than right, swap elements at these two indice and continue again.

1. Set left = 0 and right = n-1
2. While left < right 2.a if a[left] is 0 then left++
2.b if a[right] is 1 then right– ;
2.c if left < right, swap(a[left], a[right])

segregate 0s and 1s implementation

public void segregateOptimized(int[] a) throws IllegalArgumentException{

        if(a == null) throw new IllegalArgumentException();
        int left = 0;
        int right = a.length-1;

        while(left < right){
            while(left < a.length && a[left] == 0) left++;
            while(right >= 0 && a[right] == 1) right--;

            if(left >= a.length || right <= 0) return;
            
            if(a[left] > 1 || a[left] < 0 || a[right] > 1 || a[right] < 0)
                throw new IllegalArgumentException();

            if(left < right){
                a[left] = 0;
                a[right] = 1;
            }
        }
    }

The complexity of this method to segregate 0s and 1s in an array is O(n) and only one traversal of the array happens.

Test cases

package test;

import com.company.SegregateZerosAndOnes;
import org.junit.*;
import org.junit.rules.ExpectedException;

import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 28.8.18.
 */
public class SegregateZerosAndOnesTest {

    SegregateZerosAndOnes tester = new SegregateZerosAndOnes();

    @Test
    public void segregateZerosAndOnesOptimizedTest() {

        int[] a = {0,1,0,1,0,1};
        int[] output = {0,0,0,1,1,1};

        tester.segregateOptimized(a);
        assertEquals(Arrays.toString(output), Arrays.toString(a));

    }

    @Test
    public void segregateZerosAndOnesAllZerosOptimizedTest() {

        int[] a = {0,0,0,0,0,0};
        int[] output = {0,0,0,0,0,0};

        tester.segregateOptimized(a);
        assertEquals(Arrays.toString(output), Arrays.toString(a));

    }

    @Test
    public void segregateZerosAndOnesAllOnesOptimizedTest() {

        int[] a = {1,1,1,1,1};
        int[] output = {1,1,1,1,1};

        tester.segregateOptimized(a);
        assertEquals(Arrays.toString(output), Arrays.toString(a));

    }

    @Test(expected=IllegalArgumentException.class)
    public void segregateZerosAndOnesOptimizedIllegalArgumentTest() {

        int[] a = {1,1,1,1,2};
        tester.segregateOptimized(a);
    }

    @Test(expected=IllegalArgumentException.class)
    public void segregateZerosAndOnesOptimizedNullArrayTest() {

        tester.segregateOptimized(null);
    }

}

Please share if you have any suggestion or queries. If you are interested in contributing to the website or have an interview experience to share, please contact us at [email protected]

Minimum cost of connecting n ropes

Given n ropes of different lengths, connect these ropes in one rope. The cost to connect two ropes is equal to the sum of their lengths. We have to connect these ropes with minimum cost.

For example,

Input:
5, 2, 3, 9.
Output:
34
Explanation:
We can connect the ropes in the following way: First, connect the ropes of lengths 2 and 3, the cost of this connection is the sum of lengths of ropes which is 2 + 3 = 5. We are left with three ropes with lengths5,5, and 9. Next, connect the ropes of lengths 5 and 5. The cost of connection is 10. Total cost till now is 5 + 10 = 15. We have two ropes left with lengths 10 and 9. Finally, connect the last two ropes and all ropes have connected, Total Cost would be 15 + 19 = 34.

Another way of connecting ropes would be: connect ropes with lengths 5 and 9 first (we get three ropes of 3, 2, and 14), then connect 14 and 3, which gives us two ropes of lengths 17 and 2. Finally, we connect 19 and 2. Total cost in this way is 14 + 17 + 21 = 52. which is much higher than the optimal cost we had earlier.

Connect n ropes with minimum cost: A priority queue problem

When we were doing calculations in examples, did you notice one thing? Lengths of the ropes connected first are added subsequently in all the connections. For example, we connected ropes with length 2 and 3 in the first example, it gets added to next connect as part of the rope with length 5, and again when we connect the ropes with lengths 15 and 9, 2 + 3 is already inside 15.

Read Huffman coding to understand how to solve this problem from this hint.

All we have to make sure that the most repeated added rope is the smallest, then the second smallest and so on. This gives the idea that if we sort the ropes by their sizes and add them, sort again the array again until there are no ropes to add. It will always give us the optimal solution to connect ropes.

What will be the complexity of sorting based implementation? The complexity will be dominated by the sorting algorithm, best we can achieve is O(nlogn) using quicksort or merge sort. Also, connecting two ropes we have to sort the arry again. So overall complexity of this method is O(n2logn)

Can we do better than this? Do we need the array sorted at all times? All we need is the two ropes with the least length. What data structure gives us the minimum element in the least time. Priority queue will be our data structure. If we create a min-heap with lengths of ropes, we can easily find the two ropes with the least length in O(1) complexity.

  1. Create a min heap (priority queue) from the array of rope lengths
  2. Fetch the root which will give us smallest rope
  3. Fetch the root again which will give us second smallest rope
  4. Add two ropes and put it back into heap (heapify)
  5. Go back to step 2

connect n ropes with minimum cost

Min cost to connect ropes java implementation

 
package com.company;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * Created by sangar on 3.1.19.
 */
public class ConnectRopes {

    public int getMinimumCost(int[] ropeLength){

        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();

        /*
        There is no shortcut for converting from 
        int[] to List<Integer> as Arrays.asList
        does not deal with boxing and will just create a List<int[]>
        which is not what you want.
         */
        List<Integer> list = Arrays.stream(ropeLength)
                            .boxed().collect(Collectors.toList());

        /*
        Javadoc seems to imply that addAll is 
        inherited from AbstractQueue where
        it is implemented as a sequence of adds.
        So complexity of this operation is O(nlogn)
         */
        minHeap.addAll(list);

        int totalLength = 0;

        while(minHeap.size() > 1){
            int len1 = (int)minHeap.remove();
            int len2 = (int)minHeap.remove();

            totalLength+=(len1 + len2);

            minHeap.add(len1+len2);
        }

        return totalLength;
    }
}

Test cases

package test;

import com.company.ConnectRopes;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;
/**
 * Created by sangar on 23.9.18.
 */
public class ConnectRopeTest {

    ConnectRopes tester = new ConnectRopes();

    @Test
    public void minimumCostTest() {

        int[] a = {5,2,3,9};

        assertEquals(24, tester.getMinimumCost(a));
    }
    @Test
    public void minimumCostOneRopeTest() {

        int[] a = {5};

        assertEquals(0, tester.getMinimumCost(a));
    }
}


The complexity of this implementation is O(nlogn) (to create min heap out of an array in java Priority queue) + O(nlogn) (to fetch two minimum and re-heapify). However, initial complexity to build a heap from the array can be brought down to O(n) by using own implementation of min heap.

Please share if there is something wrong or missing. If you are preparing for interviews and want to receive a daily email with an interview question, please signup here

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]

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.

Minimum in sorted rotated array

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

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

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

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

minimum in rotated sorted array

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

Minimum in sorted rotated array and binary search algorithm

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

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

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

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

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

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

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

find minimum in rotated array

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

Algorithm to find minimum in sorted rotated array

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

Minimum in sorted rotated array implementation

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

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

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

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

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