## Count of binary strings without consecutive 1’s

Given a positive integer N, find the count of distinct binary strings of length N that have no consecutive 1’s. For example,

```Input:
N = 2
Output:
3.
Explanation:
There are 3 possible strings: 00, 01, 10N=3There are 5 possible strings: 000, 001, 010, 100,101
```

## Thought process to find binary strings with consecutive 1s

This problem is an easier variation of digit DP problem. Since these are binary strings for every position in the string there are just two choices: 0 and 1. To form a string of length N, at any position –

1. We can choose 0 and then for the next position we again have two choices.
2. We can choose 1 but then for the next position we cannot choose 1 as we don’t want consecutive 1’s in the string. So once we choose 1, we are also setting next position to 0.

So in case (a), we set 0 at current position and the problem then reduces to count the number of strings having length N-1 with the given condition.

And in case (b), we set 1 at current position and 0 at next position, hence the problem reduces to count the number of strings having length N-2 with the given condition.

With this we can write

Count(n) = Count(n-1) + Count(n-2)

Does this formula ring a bell? Yes, it’s the same one that is is used to find Fibonacci numbers.

As Count(1) = 2, Count(2) = 3, Count(3) = 5, ……
and Fib(1) = 1,  Fib(2) = 1, Fib(3) = 2, Fib(3) = 3, Fib(4) = 5, ……

Hence we can observe that-
Count(n) = Fib(n+2)

Using the explanation for DP approach and the implementation in Find Nth Fibonacci number problem:

```#include <iostream>
#include <vector>
using namespace std;

long long int fib(int N)
{
vector<long long int> DPVec(N+1, 0);
DPVec[1] = 1; DPVec[2] = 1;
for (int i=3; i<=N; ++i)
{
DPVec[i] = DPVec[i-1] + DPVec[i-2];
}
return DPVec[N];
}

long long int Cnt_strings(int N)
{
return fib(N+2);
}

int main()
{
int n = 3;
cout<<Cnt_strings(n)<<endl;
return 0;
}
```
```public class Count_Strings
{
static int fib(int N)
{
int DPArr[] = new int[N+1];
DPArr[1] = 1; DPArr[2] = 1;
for (int i=3; i&lt;=N; ++i)
{
DPArr[i] = DPArr[i-1] + DPArr[i-2];
}
return DPArr[N];
}

static int Cnt_strings(int N)
{
return fib(N+2);
}

public static void main (String[] args)
{
int n = 4;
int num_strings = Cnt_strings(n);
System.out.println(num_strings);
}
}
```
The time complexity of the implementation is O(n) and space complexity is also O(n)

## 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,

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,

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 &lt; 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.

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.

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

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

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.

### Show me the implementation

```package AlgorithmsAndMe;

import java.util.List;

public class PlusOne {
int carry = 0;

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

}

ListNode returnedNode =

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 {

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

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

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
*/
List<List<Integer>> result = new ArrayList<List<Integer>> ();

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){
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){
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.

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 `leftLimit`contains 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,

The output will be as shown below.

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

}

```

## 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

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

/*
inherited from AbstractQueue where
it is implemented as a sequence of adds.
So complexity of this operation is O(nlogn)
*/

int totalLength = 0;

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

totalLength+=(len1 + len2);

}

}
}
```

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?

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.

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

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.

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.

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 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?

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.

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

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

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

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.

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 ?

}
}
```

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.