Find combinations which add up to a number

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, same candidate can occur in the combination as 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. 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 which 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 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 exhaustive search and backtracking paradigm of problem-solving where you search the entire input set to see to find the answer. However, in this case, we can prune the search path as soon as we know that the current set of candidates add up more than the target.

Combination sum : implementation

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

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

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

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

Maximum area rectangle in a histogram

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

maximum area rectangle in histogram

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

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

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

Maximum area rectangle: thoughts

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

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

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

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

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

        return maxArea;
    }

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

        return j;
    }

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

        return j;
    }
}

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

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

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

        int maxArea = Integer.MIN_VALUE;

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

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

        return maxArea;
    }

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

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

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

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

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

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

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

Largest area rectangle: stack-based solution

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

So the idea is that:

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

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

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

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

Minimizing maximum lateness

Minimizing maximum lateness : Greedy algorithm

Since we have chosen the greed, let continue with it for one more post at least. Today’s problem is to minimize maximum lateness of a task. Let me clarify the problem: given a processor which processes one process at a time and as always given a list of processes to be scheduled on that processor, with the intention that maximum late process should be minimized. Contrary to previous problems, this time, we are not provided with start time and end time, but we are given length of time ti process will run and deadline it has to meet di, fi is actual finish time of process completion.

Lateness of a process is defined as
li = max{0, fi − di}, i.e. the length of time past its deadline that it finishes.
Goal here to schedule all tasks to minimize maximum lateness L = max li For example:

minimize maximum lateness

Minimizing maximum lateness : algorithm

Let’s decide our optimization strategy. There is some order in which jobs can be decided: shortest job first, earliest deadline first, least slack time first.

Let’s see if any of the above strategies work for the optimal solution. For shortest processing time first, consider example P1 = (1,100) P2 = (10, 10). If we schedule the shortest job first as in order (P1, P2), lateness will be 91, but if we take them as (P2, P1), lateness will be 0. So, clearly taking the shortest process first does not give us an optimal solution.

Check for the smallest slack time approach. See if you can come up with some counterexample that it does not work.

That leaves us with only one option, take the process which has the most pressing deadline, that is the one with the smallest deadline and yet not scheduled. If you have noticed, the example given for the problem statement is solved using this method. So, we know it works.

  1. Sort all job in ascending order of deadlines
  2. Start with time t = 0
  3. For each job in the list
    1. Schedule the job at time t
    2. Finish time = t + processing time of job
    3. t = finish time
  4. Return (start time, finish time) for each job

Minimizing maximum lateness : implementation

from operator import itemgetter

jobs = [(1, 3, 6), (2, 2, 9), (3, 1, 8), (4, 4, 9), 
        (5, 3, 14), (6, 2, 15)] 

def get_minimum_lateness():
	schedule =[];
	max_lateness = 0
	t = 0;
	
	sorted_jobs = sorted(jobs,key=itemgetter(2))
	
	for job in sorted_jobs:
		job_start_time = t
		job_finish_time = t + job[1]

		t = job_finish_time
		if(job_finish_time > job[2]):
			max_lateness =  max (max_lateness, (job_finish_time - job[2]))
		schedule.append((job_start_time, job_finish_time))

	return max_lateness, schedule

max_lateness, sc = get_minimum_lateness();
print "Maximum lateness will be :" + str(max_lateness)
for t in sc:
	print t[0], t[1]

The complexity of implementation is dominated by sort function, which is O(nlogn), rest of processing takes O(n).

Please share your suggestions or if you find something is wrong in comments. We would love to hear what you have to say. If you find this post interesting, please feel free to share or like.

Coin change problem : Greedy algorithm

Coin change problem : Greedy algorithm

Today, we will learn a very common problem which can be solved using the greedy algorithm. If you are not very familiar with a greedy algorithm, here is the gist: At every step of the algorithm, you take the best available option and hope that everything turns optimal at the end which usually does. The problem at hand is coin change problem, which goes like given coins of denominations 1,5,10,25,100; find out a way to give a customer an amount with the fewest number of coins. For example, if I ask you to return me change for 30, there are more than two ways to do so like

 
Amount: 30
Solutions : 3 X 10  ( 3 coins ) 
            6 X 5   ( 6 coins ) 
            1 X 25 + 5 X 1 ( 6 coins )
            1 X 25 + 1 X 5 ( 2 coins )

The last solution is the optimal one as it gives us a change of amount only with 2 coins, where as all other solutions provide it in more than two coins.

Solution for coin change problem using greedy algorithm is very intuitive and called as cashier’s algorithm. Basic principle is : At every iteration in search of a coin, take the largest coin which can fit into remaining amount we need change for at the instance. At the end you will have optimal solution.

Coin change problem : Algorithm

1. Sort n denomination coins in increasing order of value.
2. Initialize set of coins as empty. S = {}
3. While amount is not zero:
3.1 Ck is largest coin such that amount > Ck
3.1.1 If there is no such coin return “no viable solution”
3.1.2 Else include the coin in the solution S.
3.1.3 Decrease the remaining amount = amount – Ck

Coin change problem : implementation

#include <stdio.h>
 
int coins[] = { 1,5,10,25,100 };
 
int findMaxCoin(int amount, int size){
	for(int i=0; i<size; i++){
	    if(amount < coins[i]) return i-1;
	}
	return -1;
}

int findMinimumCoinsForAmount(int amount, int change[]){
 
	int numOfCoins = sizeof(coins)/sizeof(coins[0]);
	int count = 0;
	while(amount){
	    int k = findMaxCoin(amount, numOfCoins);
	    if(k == -1)
                printf("No viable solution");
	    else{
                amount-= coins[k];
		change[count++] = coins[k];
            }
	}
	return count;
}
 
int main(void) {
	int change[10]; // This needs to be dynamic
	int amount = 34;
	int count = findMinimumCoinsForAmount(amount, change);
 
	printf("\n Number of coins for change of %d : %d", amount, count);
	printf("\n Coins : ");
	for(int i=0; i<count; i++){
		printf("%d ", change[i]);
	}
	return 0;
}

What will the time complexity of the implementation? First of all, we are sorting the array of coins of size n, hence complexity with O(nlogn). While loop, the worst case is O(amount). If all we have is the coin with 1-denomination. Overall complexity for coin change problem becomes O(n log n) + O(amount).

Will this algorithm work for all sort of denominations? The answer is no. It will not give any solution if there is no coin with denomination 1. So be careful while applying this algorithm.

Please share if you have any suggestion or if you want me to write on a specific topic. If you liked the post, share it!

Disjoint set data structure

Disjoint set data structure

A disjoint set data structure or union and find maintains a collection 𝑆 = { 𝑆1, 𝑆2, ⋯ , 𝑆𝑛 } of disjoint dynamic sets. Subsets are said to be disjoint if intersection between them is NULL. For example, set {1,2,3} and {4,5,6} are disjoint sets, but {1,2,3} and {1,3,5} are not as intersection is {1,3} which is not null. Another important thing about the disjoint set is that every set is represented by a member of that set called as representative.

Operations on this disjoint set data structure:
1. Make Set: Creates a new set with one element x, since the sets are disjoint, we require that x not already be in any of the existing sets.
2. Union: Merges two sets containing x and y let’s say Sx and Sy and destroys the original sets.
3.Find: Returns the representative of the set which element belongs to.

Let’s take an example and see how disjointed sets can be used to find the connected components of an undirected graph.

To start with, we will make a set for each vertex by using make-set operation.

for each vertex v in G(V)
    do makeSet(v)

Next process all the edges in the graph (u,v) and connect set(u) and set(v) if the representatives of the set which contains u and set which contains v are not same.

for each edge (u,v) in 𝐺(E)
    do if findSet(u) != findSet(v)
        then union(u, v)

Once above preprocessing steps have run, then we can easily find answer if two vertices u and v are part of same connected component or not?

boolean isSameComponent(u, v)
 if findSet(u)==findSet(v)
     return True
 else 
     return False

To find how many components are there, we can look at how many disjoint sets are there and that will give us the number of connected components in a graph. Let’s take an example and see how it works.

disjoint set data structure

Below table shows the processing of each edge in the graph show figure above.

disjoint sets

Now, how can we implement sets and quickly do union and find operations? There are two ways to do it.

Disjoint set representation using an array

Simple implementation of disjoint set is using an array which maintains their representative of element i in A[i]. To this implementation to work, it is must that all the element in the set are in range 0 to N-1 where N is size of the array.

Initially, in makeSet() operation, set A[i]=i, for each i between 0 and N-1 and create the initial versions of the sets.

disjoint set data structure representation of graph

for (int i=0; i<N; i++) A[i] = i;

Union operation for the sets that contain integers u and v, we scan the array A and change all the elements
that have the value A[u] to have the value A[v]. For example, we if want to connect an edge between 1 and 2 in the above set, the union operation will replace A[2] with A[1].

disjoint set data structure time complexity and implementation in java

Now, if want to add an edge between 3 and 1. In this case, u = 3 and v = 1. A[3] = 3 and A[1] = 1. So, we will replace all the indices of A where A[i] = 1. So final array looks like this.

disjoint set data structure java

Similarly, if want to add an edge from 6 to 7.
disjoint sets

//change all elements from A[u] to A[v].
void union(int A[], int u, int v){
    int temp = A[u];
    for(int i=0; i<A.length; i++){
        if(A[i] == temp)
            A[i] = A[v]; 
    }
}

findSet(v) operation returns the value of A[v].

int findSet(int A[], int v){
    return A[v]
}

The complexity of makeSet() operation is O(n) as it initializes the entire array. Union operation take every time O(n) operations if we have to connect n nodes, then it will be O(n2) operations. FindSet() operation has constant time complexity.

We can represent a disjoint set using linked list too. In that case, each set will be a linked list, and head of the linked list will be the representative element. Each node contains two pointers, one to its next element it the set and other points to the representative of the set.

To initialize, each element will be added to a linked list. To union (u, v), we add the linked list which contains u to end of the linked list which contains v and change representation pointer of each node to point to the representation of list which contained v.

The complexity of union operation is again O(n). Also, find operation can be O(1) as it returns the representative of it.

Disjoint set forest

The disjoint-forests data structure is implemented by changing the interpretation of the meaning of the element of array A. Now each A[i] represents an element of a set and points to another element of that set. The root element points to itself. In short, A[i] now points to the parent of i.

Makeset operation does not change, as to start with each element will be the parent of itself.
Union operation will change, if we want to connect u and v with an edge, we update A[root of u] with the root of v. How to find the root of an element? As we have the relationship that A[i] is the parent of i, we can move up the chain until we find a case where A[i] == i, that case, i is the root of v.

//finding root of an element
int root(int A[],int i){
    while(A[i] != i){
        i = A[i];
    }
    return i;
}

/*Changed union function where we connect 
  the elements by changing the root of 
  one of the elements
*/

int union(int A[] ,int u ,int v){
    int rootU = root(A, u);       
    int rootV = root(A, v);  
    A[rootU] = rootV ; 
}

This implementation has a worst-case complexity of O(n) for union function. And also we made the worst complexity of findSet operation as O(n).

However, we can do some ranking on the size of trees which are being connected. We make sure that always root of smaller tree point to the root of the bigger tree.

void union(int[] A, int[] sz, u, v){

    //Finding roots
    for (int i = u; i != A[i]; i = A[i]) ;
    for (int j = v; j != A[j]; j = A[j]) ;

    if (i == j) return;
    //Comparing size of tree to put smaller tree root under 
    // bigger tree's root.
    if (sz[i] < sz[j]){
        A[i] = j;
        sz[j] += sz[i];
    }
    else {
        A[j] = i; 
        sz[i] += sz[j];
    }
}

In the next few posts, we will be discussing applications of this method to solve different problems on graphs.
Please share if there is something wrong or missing. If you are preparing for an interview, and want coaching sessions to prepare for it, please signup for free demo session.

Connect n ropes with minimum cost

Connect n ropes with minimum cost

There are given n ropes of different lengths, we need to connect these n ropes into one rope. The cost to connect two ropes is equal to the sum of their lengths. We need to connect the ropes with minimum cost.

For example, if there are 4 ropes of lengths 5, 2, 3 and 9. 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 lengths 5, 5 and 9. Next, connect the ropes of lengths 5 and 5. 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 length 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.

Minimum cost to connect n ropes: algorithm

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 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 is no ropes to add. It will always give us the optimal solution to connect ropes.

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

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

  1. Create a min heap 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
  5. Go back to step 2

Minimum cost to conenct ropes

package com.company;

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

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

    public int getMinimumCost(int[] ropeLength){

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

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

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

        int totalLength = 0;

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

            totalLength+=(len1 + len2);

            minHeap.add(len1+len2);
        }

        return totalLength;
    }
}

Test cases

package test;

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

    ConnectRopes tester = new ConnectRopes();

    @Test
    public void minimumCostTest() {

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

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

        int[] a = {5};

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

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

Please share if there is something wrong or missing.

Lowest common ancestor(LCA) using Range Minimum Query(RMQ)

Lowest common ancestor(LCA) using RMQ

We already have discussed lowest common ancestor and range minimum query. In this post, we will discuss how to use RMQ to find the lowest common ancestor of two given nodes in a binary tree or binary search tree. LCA of two nodes u and v is the node which is furthest from root and u and v are descendant of that node. For example, LCA node(5) and node(9) in below tree is node(2).

lowest common ancestor using RMQ

In earlier solutions, we scan the whole binary tree every time we have to find LCA of two nodes. This has a complexity of O(n) for each query. If this query if fired frequently, this operation may become a bottleneck of the algorithm. One way to avoid processing all nodes on each query is to preprocess binary tree and store precalculated information to find LCA of any two nodes in constant time.

This pattern is very similar to a range minimum query algorithm. Can we reduce the lowest common ancestor problem to range minimum query problem?

Reduction of lowest common ancestor problem to RMQ

Let’s revise what is RMQ: Given an array A of length n; RMQ(i,j) – returns the index of the minimum element in the subarray A[i..j].

lowest common ancestor using RMQ

Let’s find LCA of two nodes 5 and 8 manually in the above binary tree. We notice that LCA(u,v) is a shallowest common node (in terms of distance from root) which is visited when u and v are visited using the depth-first search of the tree. An important thing to note is that we are interested in shallowest, which is minimum depth, the node between u and v. Sounds like RMQ?

Implementation wise, the tree is traversed as Euler tour, which means we visit each node of tree, without lifting the pencil. This is very similar to a preorder traversal of a tree. At most, there can be 2n-1 nodes in Euler tour of a tree with n nodes, store this tour in an array E[1..2n-1].

As algorithm requires the shallowest node, closest to root, so we store the depth of each node while doing Euler tour, so we store the depth of each node in another array D[1..2n-1].

We should maintain the value when the node was visited for the first time. Why?

E[1..2n-1] – Store the nodes visited in a Euler tour of T. Euler[i] stores ith node visited in the tour.
D[1..2n-1] – Stores level of the nodes in tour. D[i] is the level of node at Euler[i]. (level is defined to be the distance from the root).
F[1..n] – F[i] will hold value when node is first visited.

For example of this graph, we start from node(1) and do Euler tour of the binary tree.

lowest common ancestor using rmq

Euler tour would be like

lca using rmq

Depth array is like

lca using rmq

First visit array looks like

lca using rmq

To compute LCA(u,v): All nodes in the Euler tour between the first visits to u and v are E[F[u]...F[v]] (assume F[u] is less than F[v] else, swap u and v). The shallowest node in this tour is at index RMQ D(F[u]..F[v]), since D[i] stores the depth of node at E[i].
RMQ function will return the index of the shallowest node between u and v, thus output node will be E[RMQ D(F[u], F[v])] as LCA(u,v)

Let’s take an example, find the lowest common ancestor of node(5) and node(8).

First of all, find the first visit to node(5) and node(8). It will be F[5] which is 2 and F[8] which is 7.

Now, all the nodes which come between visit of node(5) and node(8) are in E[2..7], we have to find the shallowest node out these nodes. This can be done by applying RMQ on array D with range 3 to 6.

lca using rmq

LCA will be E[RMQ( D(2,7)], in this case, RMQ(D[2..7]) is index 3. E[3] = 2, hence LCA(5,8) is node(2).

Lowest common ancestor using RMQ: Implementation

package com.company.BST;

import java.util.Arrays;

/**
 * Created by sangar on 1.1.19.
 */
public class LowestCommonAncestor {

    private int[] E;
    private int[] D;
    private int[] F;

    int[][] M;

    private int tourCount;

    public LowestCommonAncestor(BinarySearchTree tree){
        //Create Euler tour, Depth array and First Visited array
        E = new int[2*tree.getSize()];
        D = new int[2*tree.getSize()];
        F = new int[tree.getSize() + 1];

        M = new int[2 * tree.getSize()][2 * tree.getSize()];

        Arrays.fill(F, -1);
        getEulerTour(tree.getRoot(), E, D, F, 0);

        preProcess(D);
    }

    public int findLowestCommonAncestor(int u, int v){
        //This means node is not in tree
        if(u >= F.length || v >= F.length || F[u] == -1 || F[u] == -1)
            return -1 ;

        return E[rmq(D, F[u], F[v])];
    }

    /* This function does all the preprocessing on the tree and
       creates all required arrays for the algorithm.
    */
    private void getEulerTour(TreeNode node, int[] E, int[] D, int[] F,
                              int level){
        if(node == null) return;

        int val = (int)node.getValue();

        E[tourCount] = val; // add to tour
        D[tourCount] =  level; // store depth

        if(F[val] == -1) {
            F[(int) node.getValue()] = tourCount;
        }
        tourCount++;
        
        if(node.getLeft() != null ) {
            getEulerTour(node.getLeft(), E, D, F, level + 1);

            E[tourCount] = val;
            D[tourCount++] = level;
        }
        if(node.getRight() != null ) {
            getEulerTour(node.getRight(), E, D, F, level + 1);

            E[tourCount] = val;
            D[tourCount++] = level;
        }
    }

    /*
      This function preprocess the depth array to quickly find 
      RMQ which is used to find shallowest node.
     */
    void preProcess(int[] D) {

        for (int i = 0; i < D.length; i++)
            M[i][0] = i;

        for (int j = 1; 1 << j <D.length ; j++){
            for (int i = 0; i + (1 << j) - 1 < D.length; i++){
                if (D[M[i][j - 1]] < D[M[i + (1 << (j - 1))][j - 1]])
                    M[i][j] = M[i][j - 1];
                else
                    M[i][j] = M[i + (1 << (j - 1))][j - 1];
            }
        }
    }

    private int rmq(int a[], int start, int end){
        int j = (int)Math.floor(Math.log(end-start+1));

        if ( a[ M[start][j] ] <= a[M[end-(1<<j)+1][j]] )
            return M[start][j];

        else
            return M[end-(1<<j)+1][j];
    }
}

The beauty of this algorithm is that it can be used to find LCA of any tree, not just only binary tree or BST. The complexity of the algorithm to find a lowest common ancestor using range minimum query is (O(n), O(1)) with an additional space complexity of O(n).

Reference
Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free demo class to guide you through the process.

Range minimum query (RMQ)

Range minimum query RMQ

Given an array A[0..n], find the index of the element with the minimum value in a given range. This problem is known as Range Minimum Query or RMQ.
For example, if given array below, find the index of minimum value between index 2 and 7, RMQ answer would be 5, which is the index of element 1.

 RMQ range minimum query

Going by the brute force, every time a query is fired, we scan the range and find the minimum in a given range in the same way as we do for an entire array. The complexity of each query being answered is O(n) wherein the worst-case range is the entire array.

Can we preprocess our data, so that our query operations are less costly? If we do so, there are two parts to the solution now, first preprocessing and the second query. Let’s assume complexity of each step is f(n) and g(n) respectively, then the complexity of solution can be denoted as (f(n), g(n)).

What kind of preprocessing can be done? Basic idea is to calculate the minimum index of all the ranges possible in the array. How many ranges are possible for an array with n elements? It’s n2 ranges. Why?

So, to store the index of minimum value element of each range, O(n2) order space is required and time complexity goes to O(n3). However, complexity of query is O(1). So overall complexity of solution is ( O(n3), O(1) ).

#include <stdio.h>

int M[100][100];

int findMinimum(int a[], int start, int end, int size){
	if(start >= size || end >= size) return -1;
	int min = start;
	for(int i=start; i<=end; i++){
		if( a[i] < a[min] ){
			min = i;
		}
	}
	return min;
	
}
void preprocess(int a[], int size ){
    for(int i=0; i<size; i++){
        for(int j=0; j<size; j++){
            for(int k=i; k<=j; k++){
                M[i][j] = findMinimum(a,i,j,size); 
            }
        }
    }
}

int rmq(int start, int end){
	return M[start][end];
}

int main(void) {
	
	int a[] = { 2,3,1,5,9,7,10,5,6,3 };
	int size = sizeof(a)/sizeof(a[0]);
	
	//Preprocessing step
	preprocess(a, size);
	printf("\n Minimum index in range is : %d ", rmq(3,9) );
	printf("\n Minimum index in range is : %d ", rmq(2,7) );
	
	return 0;
}

With application of dynamic programming, the complexity of the preprocessing step can be reduced to O(n2).

#include <stdio.h>

int M[100][100];

void preprocess(int a[], int size)
{
	int i,j;
	for (i=0; i<size; i++)
		M[i][i] = i;
	
	for (i=0; i<size; i++){
		for (j=i+1; j<size; j++){
			if (a[M[i][j - 1]] < a[j])
				M[i][j] = M[i][j - 1];
			else
				M[i][j] = j;
		}
	}
}

int rmq(int start, int end){
	return M[start][end];
}

int main(void) {
	
	int a[] = { 2,3,1,5,9,7,10,5,6,3 };
	int size = sizeof(a)/sizeof(a[0]);
	
	//Preprocessing step
	preprocess(a, size);
	printf("\n Minimum index in range is : %d ", rmq(3,9) );
	printf("\n Minimum index in range is : %d ", rmq(2,7) );
	
	return 0;
}

Range minimum query with O(n), O(√n) complexity solution

Can we do better for preprocessing step while trading off query step? If we divide the array into smaller chunks and store index of minimum value element in those chunks, will it help? And what should be the size of chunks? How about we divide the array in √n parts, where √n is size of part.

RMQ or range minimum query based on square root partitioning

Now, find minimum element index in each of this chunk, and store it. Extra space required is (√n). Finding minimum for each chunk has a complexity of (√n * √n) as O(n).

To find minimum element index in the given range, follow three steps:
1. Find the index of the element with the minimum value in all chunks lying between the start and end of the given range. (Max √n operations if all chunks fall in the range)
2. Find minimum index in chunk where the start of the range lies. ( Max √n comparisons from start of the range to end of the chunk).
3. Find minimum index in chuck where end of the range lies from the start of chunk to end of the range.
4. Compare all these values and return the index of the minimum of them.

No matter, how big or small range is to find the index of an element with the minimum value, the worst case will be O(√n) as there are only 3*√n operations.

Let’s take an example and see how it works. Find minimum in range (2,7)

range minimum query or RMQ example

To get RMQ(2,7), what are the chunks with are lying within range? There is only one: chunk 1. Minimum index of chunk 1 is M[1] which is 5, so, minimum element in those chunks is A[5].

Find the index of the minimum value in chunk 0 where start of the range lies (starting from start of the range which 2). There is only one element, which is index 2, so element to compare is A[2].

Find minimum from the start of chunk where the end of the range lies. So, we will be comparing A[6] and A[7].

At the end, compare A[5] (minimum of all chunks between start and end of range ), A[2] (minimum in chunk where the start of the range lies) and A[6], A[7] (minimum in chunk where end of the range lies) and we have the answer as 5 as A[5] is the minimum of all these values.

Aggregating all things, we found a way to optimize solution of range minimum query with complexity as ((o(n), O(√n)).

RMQ using sparse table

Method 3 uses only O(√n) space, however, query time complexity is also O(√n). To reduce query time at the expense of space, there is another method called as sparse table method. This method uses features of method 2 (dynamic programming) and features of method 3 (find minimums of chunks).

In this approach, split input array into chunks of size 2j where j varies from 0 to log n and n is number of elements in array. There will be n log n such chunks and hence the space complexity becomes O(n log n).

After splitting, find the index of the minimum element in each chunk and store it in a lookup table. 

M[i][j] stores minimum in range from i with size 2j.

RMQ using sparse matrix table

For example, M[0][3] stores index of the minimum value between 0 and 7 (23 = 8 elements).

Now problem is how to create this lookup table? This table can be created using dynamic programming from bottom up. Specifically, we find index of the minimum value in a block of size 2j by comparing the two minima of its two constituent blocks of size 2j-1. More formally,

M[i,j] = M[i, j-1] if A[M[i, j-1]] >= A[M[i+2^j-1, j-1]] 
M[i,j] = M[i+2^j-1, j-1] otherwise.

How to find the index of the minimum value in a given range? Idea is to find two subranges which cover the entire range and then find the minimum of minimums of these two ranges.
For example, find RMQ(i,j). If 2k be size of largest block that fits into the range from i to j, then k = log(j – i + 1)

Now, we have two parts to look in from i to i+2k + 1 (already computed as M[i,k] ) and from j-2k+1 (already computed as M[j-2k+1, k]).

Formally,

    RMQ(i,j) =  M[i][k] if A[ M[i][k] ] >= A[M[j-2^k+1, k]]
    RMQ(i,j) =  M[j-2^k+1, k]

RMQ implementatio using sparse table

#include <stdio.h>
#include <math.h>

int M[100][100];

void preprocess(int a[], int size)
{
    int i, j;
	
    for (i = 0; i < size; i++)
        M[i][0] = i;
		
    for (j = 1; 1 << j <size ; j++){
        for (i = 0; i + (1 << j) - 1 < size; i++){
            if (a[M[i][j - 1]] < a[M[i + (1 << (j - 1))][j - 1]])
                M[i][j] = M[i][j - 1];
            else
                M[i][j] = M[i + (1 << (j - 1))][j - 1];
        }
    }
}  
  
int rmq(int a[], int start, int end){
    int j = floor(log(start-end+1));

    if ( a[M[start][j]] <= a[M[end-(1<<j)+1][j]] )
        return M[start][j];
    else 
        return M[end-(1<<j)+1][j];
}

int main(void) {
	
	int a[] = { 2,3,1,5,9,7,10,5,6,3 };
	int size = sizeof(a)/sizeof(a[0]);
	
	//Preprocessing step
	preprocess(a, size);
	printf("\n Minimum index in range is : %d ", rmq(a,3,9) );
	printf("\n Minimum index in range is : %d ", rmq(a,2,7) );
	
	return 0;
}

These two blocks entirely cover the range and since only once comparison required, the complexity of lookup will be O(1).

In this post, we discussed various ways to implement range minimum query based on space and time complexity tradeoff. In future posts, we will discuss applications of RMQ such as segmented trees and least common ancestor problem.

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

Breadth First traversal

Breadth First traversal

In the last post, we discussed depth first traversal of a graph. Today, we will discuss another way to traverse a graph, which is breadth first traversal. What is breadth first traversal? Unlike depth-first traversal, where we go deep before visiting neighbors, in breadth-first search, we visit all the neighbors of a node before moving a level down. For example, breadth first traversal of the graph shown below will be [1,2,5,3,4,6]

breadth first traversal

In breadth first search, we finish visiting all the nodes at a level before going further down the graph. For example, the graph used in the above example can be divided into three levels as shown.

breadth first search

We start with a node in level 1 which is node(1). Then visit all the nodes which are one level below node(1) which are node(2) and node(5). Then we visit all the node at level 3 which are node(3), node(4) and node(6).

Breadth First Traversal: algorithm

  1. Start with the given node u, put node u to queue
  2. While queue is not empty, repeat below steps:
    1. Dequeue fro queue and print node u.
    2. For each neighbor of u, node v
    3. If v is not visited already: add v to the queue
    4. mark v as visited

Let’s take an example and see how it works. Below is the graph and we have to find BFS for this graph.
breadth first traversal

We start from node(1), and put it in the queue.
breadth first traversal of graph

While the queue is not empty, we should pop from it and print the node. In this case, node(1) will be printed. Next, we go through all the neighbors of node(1) and put all the unvisited node on the queue. node(2) and node(5) will go on to the queue and marked as visited. Traversal = {1}

breadth first search

Again, we dequeue from the queue and this time we get node(2). We print it and go for all the neighbor node, node(3) and node(4) and mark them as visited. Traversal = {1,2}

node(5) is dequeued next and printed. Here, even though node(4) is a neighbor of node(5), it is already visited and hence not put on to the queue again. But node(6) is not yet visited, so put it on to the queue. Traversal = {1,2,5}

Now, we pop node(3) and print it, however, node(4) is already visited. Hence, nothing is added to the queue. Traversal = {1,2,5,3}

Next, node(4) is taken out from queue and printed, nothing goes on to queue. Traversal = {1,2,5,3,4}

Last, we pop node(6) and print it. Traversal = {1,2,5,3,4,6}.

At this point, the queue is empty and we stop traversal.

Breadth first traversal: implementation

public ArrayList<Integer> breadthFirstTraversal(){

        boolean[] visited = new boolean[this.G.length];
        ArrayList<Integer> traversal = new ArrayList<>();

        Queue<Integer> q = new LinkedList<>();

        //This is start node
        q.add(1);
        visited[1] = true;

        while(!q.isEmpty()){
            int u = (int)q.remove();
            traversal.add(u);

            for(int i=1; i< this.G[1].length; i++){
                if(this.G[u][i] && !visited[i]){
                    q.add(i);
                    visited[i]= true;
                }
            }
        }
        System.out.println(traversal);
        return traversal;

    }

The complexity of this code is O(V2) as at least V nodes will go in queue and for each nodes internal for loop runs V times.

Implementation of breadth-first search on graph represented by adjanceny list

  public ArrayList<Integer> breadthFirstTraversal(){

        boolean[] visited = new boolean[this.G.size()];
        ArrayList<Integer> traversal = new ArrayList<>();

        Queue<Integer> q = new LinkedList<>();

        //This is start node
        q.add(1);
        visited[1] = true;

        //This loop will run for V times, once for each node.
        while(!q.isEmpty()){
            int u = (int)q.remove();
            traversal.add(u);

            /*This loop has a worst-case complexity of O(V), where 
               node has an edge to every other node, but 
               the total number of times this loop will run is E times 
               where E number of edges.
             */
            for(int v : this.G.get(u)){
                if(!visited[v]){
                    q.add(v);
                    visited[v]= true;
                }
            }
        }
        System.out.println(traversal);
        return traversal;

    }

The complexity of Breadth First Search is O(V+E) where V is the number of vertices and E is the number of edges in the graph.

The complexity difference in BFS when implemented by Adjacency Lists and Matrix occurs due to this fact that in Adjacency Matrix, to tell which nodes are adjacent to a given vertex, we take O(|V|) time, irrespective of edges. Whereas, in Adjacency List, it is immediately available to us, takes time proportional to adjacent vertices itself, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives O(|V| + |E|).

StackOverflow

When a graph is strongly connected, O(V + E) is actually O(V2)

Applications of Breadth first traversal

  1. To find shortest path between two nodes u and v
  2. To test bipartite-ness of a graph
  3. To find all nodes within one connected component

Please share if there is something wrong or missing. If you are preparing for an interview and want a free coaching session to guide you through it, please reach out to us at communications@algorithmsandme.com

Difference between array and linked list

Difference between array and linked list

In last post : Linked list data structure, we discussed basics of linked list, where I promised to go in details what is difference between array and linked list. Before going into post, I want to make sure that you understand that there is no such thing called one data structure is better than other. Based on your requirements and use cases, you chose one or the other. It depends on what is most frequent operation your algorithm would perform in it’s lifetime. That’s why they have data structure round in interview process to understand if you can chose the correct one for the problem.

What is an array?
Array is linear, sequential and contiguous collection of elements which can be addressed using index.

What is a linked list?
Linked list is linear, sequential and non-contiguous collection of nodes, each node store the reference to next node. To understand more, please refer to Linked list data structure.

Difference between arrays and linked list

Static Vs dynamic size

Size of an array is defined statically at the compile time where as linked list grows dynamically at run time based on need. Consider a case where you know the maximum number of elements algorithm would ever have, then you can confidently declare it as array. However, if you do not know, the linked list is better. There is a catch : What if there is a rare chance that number of elements will reach maximum, most of the time it will be way less than maximum? In this case, we would unnecessary allocating extra memory for array which may or may not be used. 

Memory allocation

An array is given contiguous memory in system. So, if you know the address of any of the element in array, you can access other elements based position of the element.

linked list vs arrays
Statically allocated contiguous memory

Linked list are not store contiguous on memory, nodes are scattered around on memory. So you may traverse forward in linked list, given node (using next node reference), but you can not access nodes prior to it.

arrays vs linked list
Dynamically allocated non-contiguous memory

Contiguous allocation of memory required sufficient memory before hand for an array to be stored, for example if want to store 20 integers in an array, we would required 80 bytes contiguous memory chunk. However, with linked list we can start with 8 bytes and request more memory as when required, which may be wherever. Contiguous allocation of memory makes it difficult to resize an array too. We have to look for different chunk of memory, which fits the new size, move all existing elements to that location. Linked list on other hand are dynamically size and can grow much faster without relocating existing elements.

Memory requirement

It’s good to have non-contiguous memory then? It comes with a cost. Each node of linked list has to store reference to next node in memory. This leads to extra payload of 4 bytes in each node. On the other hand, array do not require this extra payload. You  have to trade off extra space with advantages you are getting. Also, sometime, spending extra space is better that have cumbersome operations like shifting, adding and deleting operation on array. Or value stored in node is big enough to make these 4 bytes negligible in analysis.

Operation efficiency

We do operations of data structure to get some output. There are four basic operations we should be consider : read, search, insert/update and delete.

Read on array is O(1) where you can directly access any element in array given it’s index. By O(1), read on array does not depend on size of array.
Whereas, time complexity of read on linked list is O(n) where n is number of nodes. So, if you have a problem, which requires more random reads, array will over-weigh linked list.

Given the contiguous memory allocation of array, there are optimized algorithms like binary search to search elements on array which has complexity of O(log n). Search on linked list on other hand requires O(n).

Insert on array is O(1) again, if we are writing within the size of array. In linked list, complexity of insert depends where do you want to write new element at. If insert happens at head, then it O(1), on the other hand if insert happens at end, it’s O(n).

Insert node at start of linked list
Insert node at the tail of linked list

Update means here, changing size of array or linked list by adding one more element. In array it is costly operation, as it will require reallocation of memory and copying all elements on to it. Does not matter if you add element at end or start, complexity remains O(1).
For linked list, it varies, to update at end it’s O(n), to update at head, it’s O(1). 
In same vain, delete on array requires movement of all elements, if first element is deleted, hence complexity of O(n). However, delete on linked list O(1), if it’s head, O(n) if it’s tail.

To see the difference between O(1) and O(n), below graph should be useful.

difference between array and linked list
Complexity analysis graph

Key difference between array and linked list are as follows

  • Arrays are really bad at insert and delete operation due to internal reallocation of memory.
  • Statically sized at the compile time
  • Memory allocation is contiguous,  which make access elements easy without any additional pointers. Can jump around the array without accessing all the elements in between.
  • Linked list almost have same complexity when insert and delete happens at the end, however no memory shuffling happens
  • Search on linked list is bad.=, usually require scan with O(n) complexity
  • Dynamically sized on run time.
  • Memory allocation is non-contiguous, additional pointer is required to store neighbor node reference. Cannot jump around in linked list.

Please share if there is something wrong or missing. If you wan to contribute to website, please reach out to us at communications@algorithmsandme.com