Intersection of two arrays

Given two unsorted arrays of integers, find intersection of these two arrays. Intersection means common elements in the given two arrays. For example, A = [1,4,3,2,5,6] B = [3,2,1,5,6,7,8,10] intersection of A and B is [ 1,3,2,5,6 ].

Sort array and then use binary search
As given arrays are unsorted, sort one of the arrays, preferably the larger one. Then search each element of another array in the sorted array using binary search. If the element is present, put it into the intersection array.

class Solution {
public int[] intersection(int[] nums1, int[] nums2) {

int len1 = nums1.length;
int len2 = nums2.length;
Set<Integer> result = new HashSet<>();

for(int i=0; i<len2; i++){
if(binarySearch(nums1, nums2[i]) != -1){
}
}
int i = 0;
int[] resultArray = new int[result.size()];
for(Integer num : result){
resultArray[i++] = num ;
}

return resultArray;
}

private int binarySearch(int[] a, int key) {

for(int i=0; i<a.length; i++){
if(a[i] == key) return i;
}

return -1;
}
}

The time complexity of binary search method to find intersection is O(nlogn) for sorting and then O(mlogn) for searching. Effective time complexity becomes O((n+m)logn) which is not optimal.

Sort and use merge to find common elements
Again in this method, sort two arrays first. Then use two pointers to scan both arrays simultaneously. (Please refer to merge part of merge sort ). The difference is we will put only common elements, instead of all.

The time complexity of merge sort method is O(nlogn) + O(mlogm) for sorting and then O(m+n) for scanning both arrays. It is worst than the binary search method.

Use hash
Create a hash with key as elements from the smaller array (saves space). Then scan through other array and see if the element is present in hash. If yes, put into intersection array else do not.

package AlgorithmsAndMe;

import com.sun.org.apache.xpath.internal.operations.Bool;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class IntersectionTwoArrays {

public List<Integer> findIntersecton(int[] a, int[] b) {
List<Integer> result = new ArrayList<>();
Map<Integer, Boolean> existingElements = new HashMap<>();

for (int i = 0; i < a.length; i++) {
existingElements.put(a[i], true);
}

for (int i = 0; i < b.length; i++) {
if (existingElements.containsKey(b[i])) {
}
}
return result;
}
}

Test case

package Test;

import AlgorithmsAndMe.DuplicatesInArray;
import AlgorithmsAndMe.IntersectionTwoArrays;

import java.util.List;
import java.util.Set;

public class IntersectonTwoArraysTest {

IntersectionTwoArrays intersectionTwoArrays
= new IntersectionTwoArrays();

@org.junit.Test
public void testIntersectionTwoArrays() {
int [] a = {1,6,3};
int [] b = {1,2,3};
List<Integer> result = intersectionTwoArrays.findIntersecton(a,b);

result.forEach(s -> System.out.println(s));
}
}

This method has the complexity of O(n) where n is the number of elements in the larger array and extra space complexity of O(m) where m is the number of elements in the smaller array.

These methods to find the intersection of two arrays do not work when there are duplicate elements in any of the array as they will be part of intersection array only once.

Please share if there is something wrong or missing. we would love to hear from you.

Number of occurrences of element

Given a sorted array and a key, find the number of occurrences of a key in that array. For example, in the below array, the number of occurrences of 3 is 3. Brute force method will be to scan through the array, find the first instance of an element and then find the last instance, then do the math. The complexity of that method is O(N). Can we do better than that?

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

occurrences = lastInstance - firstInstance + 1

Number of occurrences of element : Implementation.

package com.company;

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

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

return false;
}

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

return false;
}

private int findFirstOccurance(int[] nums, int target){
int start = 0;
int end = nums.length-1;

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

if(if(isGreaterThanEqualTo(nums, mid, target)){){
end = mid;
}
else{
start = mid+1;
}
}
return start < nums.length && nums[start] == target ? start : -1;
}

private int findLastOccurance(int[] nums, int target){
int start = 0;
int end = nums.length-1;

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

if(isLessThanEqualTo(nums, mid, target)){
start = mid+1;
}
else if(nums[mid] > target){
end = mid-1;
}
}
return end >= 0 && nums[end] == target ? end : -1;
}

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

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

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

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

}
}

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

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

Last occurrence of element

This problem is very similar to First occurrence of element with binary search. Given a sorted array and an element, find last occurrence of element in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find last index. For example, in given array, last occurrence of 4 is at index 4. Can you guess what is last occurrence of element 6? Brute force solution would be to scan entire array and compare each A[index] with key. If A[index] is equal to key and next element is not equal key, then return index. Worst case time complexity of brute force method is O(N). Can we do better than it?

Last occurrence of element : Thought process

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

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

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

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

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

Last occurrence of element in sorted array : Example

Let’s take an example and see how it works? Take an array as shown below and find last occurrence of element 2. Start with mid index and see if it is less than or equal to key, it is, so discard left subarray excluding mid.  New array to be searched is from index 3 to 7. Find new mid, element at new mid is less than or equal to key, in that case discard left subarray. Search space is reduced from index 5 to 7. Mid is 6 and Array is greater than key, so again discard right subarray. At this point, there is only one element left in candidate set. Is it equal to key? If yes, return the index. Can you please draw the execution flow to find 1 and say 10 (which does not exist in array)? Does algorithm work for those cases?

Last occurrence of element in sorted array : Implementation

package com.company;

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

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

return false;
}

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

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

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

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

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

Same method can be implemented recursively as follow

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

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

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

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

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

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

First occurrence of element 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 is equal to key, so again discard right subarray. Find mid again, which is 5. Array 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 communications@algorithmsandme.com

Minimum number of pages to read

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

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

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

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

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

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

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

Designing predicate function

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

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

Minimum number of pages to read  implementation

package com.company;

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

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

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

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

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

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

long [] pages = new long[books];

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

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

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

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

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

More problems on similar lines

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

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

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

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

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

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

long [] time = new long[tasks];

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

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

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

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

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

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

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

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

System.out.println(low);
}

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

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

Ceiling in sorted array

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 ?
"Element not found" : "Element found at : " + index);

}
}

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

high = mid;

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

low = mid+1;

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

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

Learnings

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

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

Binary search algorithm

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

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

Binary search algorithm : Thought process

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

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

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

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

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

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

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

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

Let’s take an example and see how it works! We have an array as shown below and we are looking for key 10: First, find mid of array, it is index 4 = 0+9/2 Next, is A[mid] is equal to key? Nope. Is key greater than A[mid]? Yes. What do we do? We focus on the right part of array from mid and discard left subarray. New start is index 5. Find mid of new reduced array, which will be 7 = ( 5 + 9 ) /2. Is A[mid] == key? No, is key greater than key? No, hence, discard right subarray and search in left subarray. New end of array is 6 and start is 5. Find new mid which is 5. Is A == key? No. Is key greater A[mid]? Yes, then discard left subarray and focus on right subarray. At this point, end = start = 6, hence mid = 6. Is A[mid] == key? Yes, hence return mid index.

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

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

Binary search algorithm implementation

package com.company;

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

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

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

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

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

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

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

}
}

Recursive implementation

package com.company;

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

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

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

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

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

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

}
}

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

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

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

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

Find element in sorted rotated array

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

Question which is very commonly asked in Amazon and Microsoft initial hacker round interviews or telephonic interviews : Given a sorted rotated array, find position of an element in that array. For example:

A = [2,3,4,1] Key = 4, Returns 2 which is position of 4 in array

A = [4,5,6,1,2,3] Key = 4 returns 0

Find element in sorted rotated array : Thought process

Before starting with any solution, it’s good to ask some standard questions about an array problem, for example, if duplicate elements are allowed or if negative numbers are allowed in array? It may or may not change the solution, however, it gives an impression that you are concerned about input range and type.

First thing to do in interview is come up with brute force solution, why? There are two reasons : first, it gives you confidence that you have something solved, it may not be optimal way but still you have something. Second, now that you have something written, you can start looking where it takes most of time or space and attack the problem there. It also, helps to identify what properties you are not using which are part of the problem and help your solution.

First thing first, what will be the brute force solution? Simple solution will be to scan through the array and find the key. This algorithm will have O(N) time complexity.

There is no fun in finding an element in sorted array in O(N) 🙂 It would have been the same even if array was not sorted. However, we already know that our array is sorted. It’s also rotated, but let’s forget about that for now. What do we do when we have to find an element in sorted array? Correct, we use binary search.

We split the array in middle and check if element at middle index is the key we are looking for? If yes, bingo! we are done.

If not, if A[mid] is less that or greater than key. If it is less, search in right subarray, and it is greater, search in left subarray. Any which way, our input array is reduced to half. Complexity of binary search algorithm is log (N). We are getting somewhere 🙂

Sorted rotated array

However, our input array in not a plain sorted array, it is rotated too. How does things change with that. First, comparing just middle index and discarding one half of array will not work. Still let’s split the array at middle and see what extra conditions come up?
If A[mid] is equal to key, return middle index.
There are two broad possibilities of rotation of array, either it is rotated more than half of elements or less than half of elements. Can you come up with examples and see how array looks like in both the cases?  If array is rotated by more than half of elements of array, elements from start to mid index will be a sorted.

If array is rotated by less than half of elements of array, elements from mid to end will be sorted.

Next question, how do you identify the case, where array is rotated by more or less than half of elements? Look at examples you come up with and see if there is some condition?

Yes, the condition is that if A[start] < A[mid], array is rotated more than half and if A[start] > A[mid], it is rotated by less than half elements.  Now, that we know, which part of array is sorted and which is not. Can we use that to our advantage?

Case 1 : When array from start to mid is sorted. We will check if key > A[start] and key < A[mid]. If that’s the case, search for key in A[start..mid]. Since, A[start..mid] is sorted, problem reduces to plain binary search. What if key is outside of start and middle bounds, then discard A[start..mid] and look for element in right subarray. Since, A[mid+1..right] is still a sorted rotated array, we follow the same process as we did for the original array.

Case 2 : When array from mid to end is sorted. We will check if key >A[mid] and key < A[end]. If that’s the case, search for key in A[mid+1..end]. Since, A[mid+1..end] is sorted, problem reduces to plain binary search. What if key is outside of mid and end bounds, then discard A[mid..end] and search for element in left subarray. Since, A[start..mid-1] is still a sorted rotated array, we follow the same process as we did for the original array.

Let’s take an example and go through the entire flow and then write concrete algorithm to find element in sorted rotated array.

Below is sorted rotated array given and key to be searched is 6. We know, A[start] > A[mid], hence check if searched key fall under range A[mid+1..end]. In this case, it does. Hence, we discard A[start..mid].

At this point, we have to options:  either fallback to traditional binary search algorithm or continue with same approach of discarding based on whether key falls in range of sorted array. Both methods work. Let’s continue with same method.

Again find middle of array from middle +1 to end. A[mid] is still not equal to key. However, A[start] < A[mid]; hence, array from A[start] to A[middle] is sorted. See if our key falls between A[start] and A[mid]? Yes, hence, we discard the right sub array A[mid..End]

Find the middle of remaining array, which is from start to old middle – 1. Is A[mid] equal to key? No. Since, A[start] is not less than A[mid], see if key falls under A[mid+1..end], it does, hence discard the left subarray.

Now, new middle is equal to key are searching for. Hence return the index. Similarly, we can find 11 in this array. Can you draw the execution flow that search?

Algorithm to find element in sorted rotated array

1. Find mid =  (start + end)/ 2
2. If A[mid] == key; return mid
3. Else, if A[start] < A[end]
• We know, left subarray is already sorted.
• If A[start] < key and A[mid] > key :
• Continue with new subarray with start and end = mid – 1
• Else:
• Continue with new subarray with start = mid + 1 and end
4. Else
• We know, right subarray is sorted.
• If A[mid] < key and A[end] > key :
• Continue with new subarray with start  = mid + 1 and end
• Else:
• Continue with new subarray with start and end = mid – 1

Find element in sorted rotated array : Implementation

package com.company;

/**
* Created by sangar on 22.3.18.
*/
public class SortedRotatedArray {

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

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

if(input[mid] == key) return mid;

else if(input[start] <= input[mid]){
/*Left sub array is sorted, check if
key is with A[start] and A[mid] */
if(input[start] <= key && input[mid] > key){
/*
Key lies with left sorted part of array
*/
return findElementRecursive(input, start, mid - 1, key);
}else{
/*
Key lies in right subarray
*/
return findElementRecursive(input, mid + 1, end, key);
}
}else {
/*
In this case, right subarray is already sorted and
check if key falls in range A[mid+1] and A[end]
*/
if(input[mid+1] <= key && input[end] > key){
/*
Key lies with right sorted part of array
*/
return findElementRecursive(input, mid + 1 , end, key);
}else{
/*
Key lies in left subarray
*/
return findElementRecursive(input, start, mid - 1, key);
}
}
}
return -1;
}

public static void main(String[] args) {
int[] input = {10,11,15,17,3,5,6,7,8,9};

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

}
}

Iterative implementation

package com.company;

/**
* Created by sangar on 22.3.18.
*/
public class SortedRotatedArray {

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

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

if (input[mid] == key) return mid;

else if (input[start] <= input[mid]) {
/*Left sub array is sorted, check if
key is with A[start] and A[mid] */
if (input[start] <= key && input[mid] > key) {
/*
Key lies with left sorted part of array
*/
end = mid - 1;
} else {
/*
Key lies in right subarray
*/
start  = mid + 1;
}
} else {
/*
In this case, right subarray is already sorted and
check if key falls in range A[mid+1] and A[end]
*/
if (input[mid + 1] <= key && input[end] > key) {
/*
Key lies with right sorted part of array
*/
start = mid + 1;
} else {
/*
Key lies in left subarray
*/
end  = mid - 1;
}
}
}
return -1;
}

public static void main(String[] args) {
int[] input = {10,11,15,17,3,5,6,7,8,9};

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

}
}

Complexity of above recursive and iterative algorithm to find an element in a rotated sorted array is O(log n). Recursive implementation has implicit space complexity of O(log n)

What did we learn today? We learned that it’s always better to come up with non-optimized solution first and then try to improve it. Also helps to correlate problem with similar and simpler problem like we understood first what is best way to find an element in sorted array and then extrapolated the solution with additional conditions for our problem.

I hope that this post helped you with this problem and many more similar problems you will see in interviews.

Please share if you have some questions or suggestions. Also, if you want to contribute on this learning process of others, please contact us.

Search element in sorted matrix

Given a sorted matrix, of N X M and element e, find the position (i,j) of e if it is present in the matrix. This problem is known as a search element in the sorted matrix.  When we say sorted matrix, it means that all elements in any row and column are in sorted order. For example,

[1,2,3,4,5
6,7,8,9,10
11,12,13,14,15
16,17,18,19,20
21,22,23,24,25]

is a sorted matrix. Now, concrete ask is to find element 18 in this matrix.

What information we have in this question? We already know that all rows and columns are individually sorted. And the challenge is to find an element. Does it ring a bell? Rule of thumb is that if you want to find an element in a sorted data set, think of binary search.  In the binary search, we tend to discard half of the input set and focus our search on the remaining data set.  It’s very intuitive in the one-dimensional array, how to formulate discarding rule in the two-dimensional matrix?

The first challenge is to find the pivot around which we will move. In this case, let’s start from the leftmost bottom cell, that is M[N-1].

The process is to check if searched element e is less than or greater than element at leftmost bottom cell i.e M[N-1].
Let’s say i= N-1, and j=0;
1. If  e < M[i][j], move up in same column. Why? As we know that all the element in this column on the right will be definitely greater than M[i][j] and hence, by extension, greater than e, hence we cannot have e in that column.
However, there is possibility of finding e in column above it. Hence, we discard the current row. Decrease i and repeat.
2. If   e > M[i][j] , then move right in same row. Why? Because, all element in the same column will be less than M[i][j] and hence by extension less than e. So we discard current column. Increase j and repeat.
3. If   e equal to M[i][j] , return i, j as answer.

How many comparisons will happen in the worst case and when it will happen? If e is at position M[N-1], then there will be M+N comparisons before we hit e. Hence, the complexity of the algorithm to search in row and column sorted matrix is O(N+M), where N is the number of rows and M is the number of columns.

Search in sorted matrix implementation using binary search

package com.company;

/**
* Created by sangar on 30.12.17.
*/
public class Search {

public static Position searchElement(int [][] M, int currentRow, int currentColumn,
int columns, int element){

//Check if we have a matrix to search in
if( currentRow < 0 || currentColumn > columns) return new Position(-1, -1);

//Check if the middle element is the searched element
if(M[currentRow][currentColumn] == element){
return new Position(currentRow,currentColumn);
}
else{
if(element > M[currentRow][currentColumn]){
return searchElement(M, currentRow, currentColumn+1, columns, element);
}
else{
return searchElement(M, currentRow -1, currentColumn, columns, element);
}
}
}

public static void main(String[] args) {
int[][] mat = new int[][] { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};

int rowcount = 4,colCount=4,key=20;
Position position = searchElement(mat, rowcount-1, 0, colCount, key);

System.out.println("Row: " + position.getRow() + ", Column: " + position.getColumn());
}
}

We can avoid recursion and implement the same function in an iterative way as shown below

package com.company;

/**
* Created by sangar on 30.12.17.
*/
public class Search {

public static Position searchElementIterative(int [][]M, int rows, int columns, int element){
int i = rows-1;
int j = 0;
while( i>=0 && j <columns){
if(M[i][j]== element){
return new Position(i,j);
}
else if(M[i][j] < element){
j++;
}
else{
i--;
}
}
return new Position(-1, -1);
}

public static void main(String[] args) {
int[][] mat = new int[][] { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};

int rowcount = 4,colCount=4,key=20;
Position position = searchElementIterative(mat, rowcount, colCount, key);

System.out.println("Row: " + position.getRow() + ", Column: " + position.getColumn());
}
}

We reduced the complexity of search from O(M x N) which quadratic to O(M+N), which is linear. Can we do something sub-linear?  Can we discard more than one column or row at a time?  How about changing our pivot element from the leftmost bottom element to the middle element of a matrix?  Thinking being, that is the only thing you can change, as matrix and element are already given to you and you cannot modify them. If you read optimizations on quicksort, this kind of thinking comes naturally, to vary the initial assumption of the solution to see if we can do better?

Search element in sorted matrix optimization

What if we take the middle element of the matrix, M[i][j] as a pivot to compare with element e, what can be said about four quadrants middle element divides it into?

All elements in the left top quadrant are less than M[i][j] for sure.
All elements in the right top may be less than or greater than the middle element. We cannot deduce anything for this quadrant and we need to dig deeper.

All elements in the right bottom are greater than the middle element.
All elements in the left bottom quadrant are either less or greater than middle element and hence as the rightmost top quadrant, nothing can be said about it.

Two quadrants which contain either all less than or all greater than middle element.  Based on the relationship between e and middle element M[i][j], we can eliminate one of two quadrants, hence reducing the problem to 3/4th of the original problem.

Case 1 :
If   M[i][j] < e , then we need to search in all quadrants which may contain elements greater than middle. Discard quadrant which contains all elements less than middle.

Case 2:
If   M[i][j] > e , then search in all quadrants which may contain elements less than M[i][j]. Discard quadrant which contains elements definitely greater than M[i][j].

Implementation note: Observe that we always end up searching in top right matrix no matter if the element is greater or less than the middle.
If we take that matrix separately and check always, rest part to be searched is either horizontal bottom matrix or vertical left matrix. The code is implemented keeping this in mind.

package com.company;

import com.company.Position;
public class Main {

public static Position searchElement(int [][] M, int rowStart, int rowEnd,
int columnStart, int columnEnd, int element){

//Check if we have a matrix to search in
if(rowStart > rowEnd || columnStart > columnEnd) return new Position(-1, -1);

int i = rowStart + (rowEnd-rowStart) / 2;
int j = columnStart + (columnEnd-columnStart) / 2;

//Check if the middle element is the searched element
if(M[i][j] == element){
return new Position(i,j);
}
else{
//Always search in topmost right matrix.
Position position = searchElement(M,
rowStart,
i,
j+1,
columnEnd,
element);

// If we found element in upper right matrix, return the position.
if(isFound(position)){ return position; }

else{
/*Based on condition, search either left the vertical matrix
or lower horizontal matrix */

if(element > M[i][j]){
//search lower horizontal matrix
return searchElement(M,
i+1,
rowEnd,
columnStart,
columnEnd,
element
);
}
else{
//Search in right vertical matrix
return searchElement(M,
rowStart,
rowEnd,
columnStart,
j-1,
element
);
}
}
}
}

private static boolean isFound(Position position){
return (position.getRow() != -1 &&
position.getColumn() != -1);
}

public static void main(String[] args) {
int[][] mat = new int[][] { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};

int rowcount = 4,colCount=4,key=48;
Position position = searchElement(mat,
0,
rowcount - 1,
0,
colCount - 1,
key
);
System.out.println("Row: " + position.getRow() + ", Column: " + position.getColumn());
}
}

Position can be defined as follows

package com.company;

/**
* Created by sangar on 30.12.17.
*/
public class Position {

private int i;
private int j;

public Position(int i, int j){
this.i = i;
this.j = j;
}

public int getRow(){
return i;
}
public int getColumn(){
return j;
}
}

The complexity of above code is less than O(N^1.58). Every time we will have 3 N/2 size submatrices.

Word of caution: Both solutions are recursive in nature, which has n extra overhead of space on the stack. If the recursion runs deep, this can be a problem and it is advised to use iterative solution. The recursive solution as usually no go in production.

Please share if you find something missing or wrong, or you have another idea to improve the website. We would love to hear from you.
If you believe that you can explain algorithms problems in an easier way to students and want to contribute to the platform, please reach out to us on communications@algorithmsandme.com and we will get back.

Peak in array

Given an unsorted array, find a peak in array. A peak is defined as an element which is not smaller than its immediate neighbors. In an unsorted array, there can be many such peaks, referred to as local Maxima. Mathematically, ith element is called as peak following property holds true:

A[i-1] <= A[i] >=A[i+1]

For first element and last elements of array, left and right neighbors respectively, are considered as negative infinity.

A = A[n] = -infinity

For example, peak in following array would be 6 or 7 Can you identify the peak in this array? What would be peak in sorted array? It will be the last element of array and similarly, for reverse sorted array, first element will be peak.

Peak  in array : Thought process

I recommend two things: First, get your pen and paper to practice this problem yourself. Second, try to come up with brute force solution as soon as possible. Why? Because it adds to your confidence, when you have some solution already in hand.

Brute force approach to find peak in an array of integers will be to scan through it and for each element, check if greater than it’s greater than previous and next element.  If it is, return index of that element. In worst case we would end up scanning whole array (in a sorted array), so worst case complexity of brute force solution is O(N)

Obviously, this would not have been an interview question, if expectation was to solve it in O(N) complexity, anyone with basic programming knowledge can solve it. There is no way to differentiate a good candidate from an average based on this question then. However, interviewer expects you to solve it in better than O(N) complexity and that’s where problem becomes interesting.

What if we do not go linear and randomly check index m for local maxima? If it is local maxima, we are good, return the index of that element. If it is not peak and given that array is unsorted, three situations possible at that index :
1. Array is rising toward right, that means, next element is greater than current and it’s previous element. 2.  Array is falling towards right, that means, next element is less than current and it’s previous element. 3.  It’s a valley, where current element is less than both previous and next element. In first situation, maximum should be on the right side of current index, why? In second situation, peak will be in left side of current index.

If A[m] < A[m+1], A[m] cannot be peak. However, if A[m+2] is less than A[m+1] is less than A[m+1], then A[m+1] can be a peak or some subsequent element can be. In worst case it would be the last element of array if whole A[m..end] is sorted.
If A[m] < A[m-1], in that case, either A[m-1] is peak or some element preceding it can surely be. In worst case, first element will be the peak.

Algorithm to find peak in array

Now question is how to select m? We want to minimize the worst case number of elements to check after splitting, which is possible by splitting the array in middle. Take mid as the starting point, this is classic case of divide and conquer  approach as we will discard half of the array based on certain condition.

1. Find mid = low + (high-low)/2
2. If A[mid-1] <= A[mid] =>A[mid+1], then return mid
3. If A[mid-1] > A[mid], high = mid-1
4. If A[mid+1] > A[mid], low = mid+1
5. Repeat step 1 to 4 till there are more than one element in array. Else return that last element.

Let’s take an example and see if this algorithm works. We have given array a as below Find mid and see if mid is peak we are looking for, in this case it is not as A[mid] is less than A[mid+1].We will discard left subarray and look for peak in right subarray starting from mid+1. New low and high are shown, we find new mid. Is new mid, local maxima? No, as it is less than previous and next element, it is valley. We will discard right subarray and look for peak in left subarray. Now, there is only one element, hence it should be peak in array. Peak in array : Implementation

package com.company;

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

public  static int findPeak(int[] a){
int low = 0;
int high = a.length-1;

while (low<high){
int mid = low + (high-low)/2;
if(mid == low ) return a[low] > a[high] ? low:high;

//If mid is local maxima, return it.
if(a[mid-1] <= a[mid]
&& a[mid] >= a[mid+1]) return mid;
else if(a[mid-1] > a[mid]) high = mid-1;
else low = mid+1;
}
return low;
}

public static void main(String[] args) {
int[] input = {1,2,6,5,3,7,4};

int index = findPeak(input);
System.out.print("Peak found at : " + index);
}
}

Always remember to check for array with two elements, that will catch almost all bugs regarding boundary overflow. Also, notice that since we are accessing mid+1 and mid-1 indices of array, make sure that these indices are within bounds of array. These two things are very important for a solution to be correct and acceptable in interview. Also, to understand more about binary search algorithm and how it works, please refer to Binary search algorithm

Complexity of divide and conquer algorithm to find peak in unsorted array is O(log n). Recurrence relation for this would be T(n) = T(n/2) + c

Please share if there is something wrong or missing. If you want to contribute to website and help others to learn, please reach out to us on communications@algorithmsandme.com