Segregate 0s and 1s in an array

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

segregate 0s and 1s in an array

The output will be as shown below.

segregate 0s and 1s in an array

This problem is very similar to Dutch national flag problem

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

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

package com.company;

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

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

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

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

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

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

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

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

segregate 0s and 1s implementation

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

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

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

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

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

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

Test cases

package test;

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

import java.util.Arrays;

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

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

    SegregateZerosAndOnes tester = new SegregateZerosAndOnes();

    @Test
    public void segregateZerosAndOnesOptimizedTest() {

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

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

    }

    @Test
    public void segregateZerosAndOnesAllZerosOptimizedTest() {

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

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

    }

    @Test
    public void segregateZerosAndOnesAllOnesOptimizedTest() {

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

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

    }

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

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

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

        tester.segregateOptimized(null);
    }

}

Please share if you have any suggestion or queries. If you are interested in contributing to the website or have an interview experience to share, please contact us at communications@algorithmsandme.com.

Cycle in undirected graph using disjoint set

Cycle in undirected graph using disjoint set

In post disjoint set data structure, we discussed the basics of disjoint sets. One of the applications of that data structure is to find if there is a cycle in a directed graph.

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

For example, in the graph shown below, there is a cycle formed by path : 1->2->4->6->1.

detect cycle in undirected graph using disjoint set data structure

Disjoint-set data structure has two operations: union and find. Union operation merges two sets into one, whereas find operation finds the representative of the set a given element belongs to.

Using disjoint set to detect a cycle in directed grah

How can use the data structure and operations on it to find if a given directed graph contains a cycle or not?

We use an array A, which will store the parent of each node. Initialize the array with the element itself, that means to start with every node is the parent of itself.

Now, process each edge(u,v) in the graph and for each edge to the following: Get the root of both vertices u and v of the edge. If the roots of both nodes are different, update the root of u with the root of v. If roots are same, that means they belong to the same set and hence this edge creates a cycle.

How can we find the root of a vertex? As we know A[i] represents the parent of i; we start with i= u and go up till we find A[i] = i. It means there is no node parent of i and hence i is the root of the tree to which u belongs.

Let’s take an example and see how does it work. Below is the given directed graph and we have to if there is a cycle in it or not?

detect cycle in undirected graph using disjoint set data structure

To start with, we initialize array A with the elements themselves.

detect cycle in a graph

Now, we process each node of the graph one by one. First is edge(1,2). The root of node(1) is 1 and the root of node(2) is 2. Since the roots of two vertices are different, we update the parent of the root of 2 which is A[2] to the root of 1 which is 1.

Next, we process edge(2,3), here root of the node(2) is 1, whereas the root node(3) is 3. Again they differ, hence update A[root of 3] with root 2, i.e A[3] = 1;

Now, process edge(2,4), it will end up with A[4] = 1, can you deduce why? And similarly edge(4,6) will also lead to update A[6] = 1.

detect cycle in directed graph using disjoint sets

Now, we process the edge(6,1). Here, root of node(6) is 1 and also the root of node(1) is 1. Both the nodes have same root, that means there is a cycle in the directed graph.

detect a cycle in undirected graph

To detect a cycle in direct graph : Implementation

package com.company.Graphs;

import java.util.*;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyList {
    private Map<Integer, ArrayList<Integer>> G;
    private boolean isDirected;
    private int count;

    public AdjacencyList(boolean isDirected){
        this.G = new HashMap<>();
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){

        if(this.G.containsKey(start)){
            this.G.get(start).add(dest);
        }else{
            this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
        }

        if(!this.G.containsKey(dest)) {
            this.G.put(dest, new ArrayList<>());
        }
        //In case graph is undirected
        if(!this.isDirected) {
                this.G.get(dest).add(start);
        }
    }

    public boolean isEdge(int start, int dest){
        if(this.G.containsKey(start)){
            return this.G.get(start).contains(dest);
        }

        return false;
    }

    public boolean isCycleWithDisjointSet() {
        int[] parent = new int[this.G.size() + 1];

        for (int u = 1; u < this.G.size() + 1; u++) {
            //Process edge from each node.

            //Find root of u
            int i, j;

            //Worst complexity is O(V)
            for(i=u; i != parent[i]; i = parent[i]);

            /*This loop will run for O(E) times for all 
             the vertices combined. */
            for(int v: this.G.get(u)){
                for(j=v; j != parent[j]; j = parent[j]);

                if(i == j){
                    System.out.println("Cycle detected at 
                                        ("+ u + "," + v + ")");
                    return true;
                }

                parent[i] = j;
            }
        }
        return false;
    }
}

Test cases

package test.Graphs;

import com.company.Graphs.AdjacencyList;
import org.junit.jupiter.api.Test;

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

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyListTest {
    @Test
    public void detectCycleInDirectedGraphTest() {

        AdjacencyList tester = new AdjacencyList(false);

        tester.addEdge(1,5);
        tester.addEdge(3,4);
        tester.addEdge(2,4);
        tester.addEdge(1,3);
        tester.addEdge(3,5);
        tester.addEdge(5,2);

        assertEquals(true, tester.isEdge(3,4));
        assertEquals(false, tester.isEdge(1,4));

        assertEquals(true, tester.isCycleWithDisjointSet());

    }
}

Complexity of this algorithm is O(EV) where E is number of edges and V is vertices, where as union function in disjoint set can take linear time w.r.t to vertices and it may run for number of edge times.

Please share if there is something wrong or missing. If you are preparing for interview and interested in personalized coaching, please signup for free demo class.

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 there is the 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. 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(y) 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] as A[2] was the only element with a value equal to A[2].

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

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

Runway reservation system

Runway reservation system

Given an airport with a single runway, we have to design a runway reservation system of that airport. Add to details: each reservation request comes with requested landing time let’s say t. Landing can go through if there is no landing scheduled within k minutes of requested time, that means t can be added to the set of scheduling landings. K can vary and depends on external conditions. This system helps with reservations for the future landings.
Once the plane lands safely, we have to remove the plane for landing sets.

This is perfectly possible with airports with multiple runways where only one runway can be used because of weather conditions, maintenance etc. Also, one landing cannot follow another immediately due safety reasons, that’s why there has to be some minimum time before another landing takes place. We have to build this system with given constraints.

In nutshell, we have create a set of landings which are compatible with each other, i.e they do not violate the constraint put.  There are two operations to be performed on this set : insertion and removal. Insertion involves checking of constraints. 

Example: let’s say below is the timeline of all the landing currently scheduled and k = 3 min

reservation system

Now, if the new request comes for landing at 48.5, it should be added to the set as it does not violate the constraint of k mins. However, if a request comes for landing at 53, it cannot be added as it violates the constraint.
If a new request comes for 35, it is invalid as the request is in past.

Reservation system: thoughts

What is the most brute force solution which comes to mind? We can store all the incoming requests in an unsorted array.  Insertion should be O(1) operation as it is at the end. However, checking the constrain that it is satisfied will take O(n) because we have to scan through the entire array.
Same is true even if we use unsorted linked list. 

How about a sorted array? We can use a binary search algorithm to find the constraint, which will take O(log n) complexity. However, the insertion will still be O(n) as we have to move all the elements to the right from the position of insertion.

Sorted list solves the problem of insertion in O(1) but then search for the constraint will be O(n) complexity. It just moves the problem from one place to another.

Reservation system using binary search tree

We have to optimize two things : first check if the new request meets the constraints, second insert the new request into the set. 

Let’s think of binary search tree. To check a constraint, we have to check each node of the binary tree, but based on the relationship of the current node and the new request time, we can discard half of the tree. (Binary search tree property, where all the nodes on the left side are smaller than the root node and all the nodes on the right side are greater than the current node)

When a new request comes, we check with the root node and it does not violate the constraints, then we check if the requested time is less than the root. If yes, we go to left subtree and check there. If requested landing time is greater than the root node, we go to right subtree.
When we reach the leaf node, we add a new node with new landing time as the value of that node.

If at any given node, the constraint is violated, i.e not new landing time is within k minutes of time in the node, then we just return stating it is not possible to add new landing.

What will be complexity of checking the constraint? It will be O(h) where h is height of binary search tree. Insert is then O(1) operation.

Reservation system implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node Node;

void inoderTraversal(Node * root){
    if(!root) return;
	
    inoderTraversal(root->left);
    printf("%d ", root->value);
    inoderTraversal(root->right);
}

Node *createNode(int value){
    Node * newNode =  (Node *)malloc(sizeof(Node));
    
    newNode->value = value;
    newNode->right= NULL;
    newNode->left = NULL;
	
    return newNode;
}

Node *addNode(Node *node, int value, int K){
	if(!node)
        return createNode(value);
    
    if ( node->value + K > value && node->value - K < value ){
        return node;
    }
    if (node->value > value)
        node->left = addNode(node->left, value, K);
    else
        node->right = addNode(node->right, value, K);
    return node;
}

/* Driver program for the function written above */
int main(){
    Node *root = NULL;
	
    //Creating a binary tree
    root = addNode(root, 30, 3);
    root = addNode(root, 20, 3);
    root = addNode(root, 15, 3);
    root = addNode(root, 25, 3);
    root = addNode(root, 40, 3);
    root = addNode(root, 38, 3);
    root = addNode(root, 45, 3);
    inoderTraversal(root);
	
    return 0;
}

Let’s say a new requirement comes which is to find how many flights are scheduled till time t?

This problem can easily be solved using binary search tree, by keeping track of size of subtree at each node as shown in figure below.

runway reservation system

While inserting a new node, update counter of all the nodes on the nodes. When query is run, just return the count of node of that time or closest and smaller than that value of t. 

Please share if there is something wrong or missing. If you are preparing for an interview, please signup to receive free preparation material.

Prune nodes not on paths with given sum

Prune nodes not on paths with given sum

Prune nodes not on paths with given sum is a very commonly asked question in Amazon interviews. It involves two concepts in one problem. First, how to find a path with a given sum and then second, how to prune nodes from binary tree. The problem statement is:

Given a binary tree, prune nodes which are not paths with a given sum.

For example, given the below binary tree and given sum as 43, red nodes will be pruned as they are not the paths with sum 43.

Prune nodes not on path with given sum
Prune nodes not on path with given sum

Prune nodes in a binary tree: thoughts

To solve this problem, first, understand how to find paths with a given sum in a binary tree.  To prune all nodes which are not on these paths,  get all the nodes which are not part of any path and then delete those nodes one by one. It requires two traversals of the binary tree.
Is it possible to delete a node while calculating the path with a given sum? At what point we find that this is not the path with given sum? At the leaf node.
Once we know that this leaf node is not part of the path with given sum, we can safely delete it.  What happens to this leaf node? We directly cannot delete the parent node as there may be another subtree which leads to a path with the given sum. Hence for every node, the pruning is dependent on what comes up from its subtrees processing.

At the leaf node, we return to parent false if this leaf node cannot be part of the path and delete the leaf node. At parent node, we look for return values from both the subtrees. If both subtrees return false, it means this node is not part of the path with the given sum. If one of the subtrees returns true, it means the current node is part of a path with the given sum. It should not be deleted and should return true to its parent.

Prune nodes from a binary tree: implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

#define true 1
#define false 0

int prunePath(Node *node, int sum ){
	
	if( !node ) return true;
	
	int subSum =  sum - node->value;
	/* To check if left tree or right sub tree 
	contributes to total sum  */
	
	int leftVal = false, rightVal = false;
	
	/*Check if node is leaf node */
	int isLeaf = !( node->left || node->right );
	
	/* If node is leaf node and it is part of path with sum
	= given sum return true to parent node so tha parent node is
	not deleted */
	if(isLeaf && !subSum )
		return true;
		
	/* If node is leaf and it not part of path with sum 
	equals to given sum
    Return false to parent node */
    else if(isLeaf && subSum ){
    	free(node);
    	return false;
    }
    /* If node is not leaf and there is left child 
	Traverse to left subtree*/
    leftVal = prunePath(node->left, subSum);
    
    /* If node is not leaf and there is right child
	 Traverse to right subtree*/
    rightVal = prunePath(node->right, subSum);
    
    /* This is crux of algo.
    1. If both left sub tree and right sub tree cannot lead to
	path with given sum,Delete the node 
    2. If any one sub tree can lead to path with sum equal
	to given sum, do not delete the node */ 
    if(!(leftVal || rightVal) ){
    	free(node);
    	return false;
    }
    if(leftVal || rightVal ){
    	if(leftVal)
    		node->right = NULL;
    	if(rightVal)
    		node->left = NULL;
    	return true;
    }
    return true ;
}

void inoderTraversal(Node * root){
	if(!root)
		return;
	
	inoderTraversal(root->left);
	printf("%d ", root->value);
	inoderTraversal(root->right);
}
Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
	
	return newNode;
}
Node *addNode(Node *node, int value){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	inoderTraversal(root);	
	prunePath(root, 65);
	
	printf( "\n");
	if( root ){
		inoderTraversal(root);	
	}
	return 0;
}

The complexity of this algorithm to prune all nodes which are not on the path with a given sum is O(n).

Please share if there is something wrong or missing. If you are preparing for interviews, please signup for free interview material.

Print paths in a binary tree

Print paths in a binary tree

We learned various kind of traversals of a binary tree like inorder, preorder and postorder. Paths in a binary tree problem require traversal of a binary tree too like every other problem on a binary tree. The problem statement is:

Given a binary tree, print all paths in that binary tree

What is a path in a binary tree? A path is a collection of nodes from the root to any leaf of the tree. By definition, a leaf node is a node which does not have left or right child. For example, one of the paths in the binary tree below is 10,7,9.

paths in a binary tree
Paths in a binary tree

Paths in a binary tree: thoughts

It is clear from the problem statement that we have to start with root and go all the way to leaf nodes. Question is do we need to start with root from each access each path in binary tree? Well, no. Paths have common nodes in them. Once we reach the end of a path (leaf node), we just move upwards one node at a time and explore other paths from the parent node. Once all paths are explored, we go one level again and explore all paths from there. 

This is a typical postorder traversal of a binary tree, we finish the paths in the left subtree of a node before exploring paths on the right subtree We process the root before going into left or right subtree to check if it is the leaf node. We add the current node into the path till now. Once we have explored left and right subtree, the current node is removed from the path.

Let’s take an example and see how does it work. Below is the tree for each we have to print all the paths in it.

paths in a binary tree
Paths in binary tree

First of all our list of paths is empty. We have to create a current path, we start from the root node which is the node(10). Add node(10) to the current path. As node(10) is not a leaf node, we move towards the left subtree.

print paths in a binary tree

node(7) is added to the current path. Also, it is not a leaf node either, so we again go down the left subtree.

paths in binary search tree

node(8) is added to the current path and this time, it is a leaf node. We put the entire path into the list of paths or print the entire path based on how we want the output.

paths in a binary tree

At this point, we take outnode(8) from the current path and move up to node(7). As we have traversed the left subtree of,node(7) we will traverse right subtree of the node(7).

paths in binary search tree

node(9) is added now to the current path. It is also a leaf node, so again, put the path in the list of paths. node(9) is moved out of the current path.

Now, left and right subtrees of node(7) have been traversed, we remove node(7) from the current path too.

At this point, we have only one node in the current path which is the node(10) We have already traversed the left subtree of it. So, we will start traversing the right subtree, next we will visit node(15) and add it to the current path.

node(15) is not a leaf node, so we move down the left subtree. node(18) is added to the current path. node(18) is a leaf node too. So, add the entire path to the list of paths. Remove node(18) from the current path.

We go next to the right subtree of the node(15), which is the node(19). It is added to the current path. node(19) is also a leaf node, so the path is added to the list of paths.

Now, the left and right subtrees of the node(15) are traversed, it is removed from the current path and so is the node(10).

Print paths in a binary tree: implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 21.10.18.
 */
public class PrintPathInBST {
    public void printPath(BinarySearchTree tree){
        ArrayList<TreeNode> path  = new ArrayList<>();
        this.printPathRecursive(tree.getRoot(), path);
    }

    private void printPathRecursive(TreeNode root,
									ArrayList<TreeNode> path){
        if(root == null) return;

        path.add(root);

        //If node is leaf node
        if(root.getLeft() == null && root.getRight() == null){
            path.forEach(node -> System.out.print(" " 
							+ node.getValue()));
            path.remove(path.size()-1);
            System.out.println();
            return;
        }

        /*Not a leaf node, add this node to 
		path and continue traverse */
        printPathRecursive(root.getLeft(),path);
        printPathRecursive(root.getRight(), path);

		//Remove the root node from the path
        path.remove(path.size()-1);
    }
}

Test cases

package com.company.BST;
 
/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();
 
        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);
 
        binarySearchTree.printPath();
    }
}

Tree node definition

package com.company.BST;

/**
 * Created by sangar on 21.10.18.
 */
public class TreeNode<T> {
    private T value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(T value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public T getValue(){
        return this.value;
    }
    public TreeNode getRight(){
        return this.right;
    }
    public TreeNode getLeft(){
        return this.left;
    }

    public void setValue(T value){
        this.value = value;
    }

    public void setRight(TreeNode node){
        this.right = node;
    }

    public void setLeft(TreeNode node){
        this.left = node;
    }
}

Complexity of above algorithm to print all paths in a binary tree is O(n).

Please share if there is something wrong or missing. If you are preparing for Amazon, Microsoft or Google interviews, please signup for interview material for free.

First non repeated character in string

First non repeated character in string

Given a string, find first non repeated character in a stringFor example, string is abcbdbdebab, the first non repeating character would be c. Even though e is also non repeating in string, c is output as it is first non repeating character.

Non repeating character : thoughts

What does it mean to be non-repeating character? Well, the character should occur in string only once. How about we scan the string and find what is count for each character? Store character and count in map as key value pair.
Now, that we have <character, count> key value pair for all unique characters in string, how can we find first non repeating character? Refer back to original string; scan the string again and for each character, check the corresponding count and if it is 1 return the character.

package com.company;

import java.util.HashMap;

/**
 * Created by sangar on 4.10.18.
 */
public class FirstNonRepeatingChar {

    HashMap<Character, Integer> characterCount = new HashMap<>();

    public char firstNonRepeatingCharacter(String s){
        //Best to discuss it with interviewer, what should we return here?
        if(s == null) return ' ';

        if(s.length() == 0) return ' ';

        for (char c: s.toCharArray()){
            if(!characterCount.containsKey(c)){
                characterCount.put(c,1);
            }
            else {
                characterCount.put(c, characterCount.get(c) + 1);
            }
        }
        for (char c: s.toCharArray()) {
            if(characterCount.get(c) == 1) return c;
        }

        return ' ';
    }
}
package test;

import com.company.FirstNonRepeatingChar;
import org.junit.jupiter.api.Test;

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

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

    FirstNonRepeatingChar tester = new FirstNonRepeatingChar();

    @Test
    public void firstNonRepeatingCharExists() {
        String s = "abcbcbcbcbad";
        assertEquals('d', tester.firstNonRepeatingCharacter(s));
    }

    @Test
    public void firstNonRepeatingCharDoesNotExists() {
        String s = "abcbcbcbcbadd";
        assertEquals(' ', tester.firstNonRepeatingCharacter(s));
    }

    @Test
    public void firstNonRepeatingCharWithEmptyString() {
        String s = "";
        assertEquals(' ', tester.firstNonRepeatingCharacter(s));
    }

    @Test
    public void firstNonRepeatingCharWithNull() {
        assertEquals(' ', tester.firstNonRepeatingCharacter(null));
    }
}

Complexity of this method to find first non-repeating character in a string is O(n) along with space complexity of O(1) to store the character to count map.

There is always some confusion about space complexity of above method, we think as 256 characters are used, should it not be counted as space complexity? Definitely. But in asymptotic notations, this space is independent of size of input, so space complexity remains O(1).

One more thing, even though time complexity is O(n), input string is scanned twice, first time to get count of characters and second time to find first non repeating character.

Optimization

Consider a case when string is too large with millions of characters, most of them repeated, above solution may turn slow in last where we look for character with count 1 in map.  How can we avoid scanning array second time?
How about we store some information with character in map along with count, so that we can figure out if the character is first non repeating or not.
Or we can have two maps, one stores the count and other stores the first index of character.

Once, we have created two maps as mentioned above, go through the first map and find the all characters with count 1. For each of these characters, check which one has the minimum index on second map and return that character.

Complexity of algorithm remains same, however, second scan of string is now not required. In other words, second scan is now independent of size of input as it depends on the size of first map, which is constant to 256 as that’s the number of unique 8 bit characters possible.

Find first non repeating character : Implementation

package com.company;

import java.util.HashMap;

/**
 * Created by sangar on 4.10.18.
 */
public class FirstNonRepeatingChar {
    public char firstNonRepeatingCharacterOptimized(String s){
        HashMap<Character, Integer> characterCount = new HashMap<>();
        HashMap<Character, Integer>characterIndex = new HashMap<>();
        //Best to discuss it with interviewer, what should we return here?
        if(s == null) return ' ';

        if(s.length() == 0) return ' ';

        for (int i=0; i<s.length(); i++){
            char c  = s.charAt(i);
            if(!characterCount.containsKey(c)){
                characterCount.put(c,1);
                characterIndex.put(c,i);
            }
            else {
                characterCount.put(c, characterCount.get(c) + 1);
            }
        }
        char nonRepeatedCharacter = ' ';
        int prevIndex = s.length();
        for (char c : characterCount.keySet()) {
            if(characterCount.get(c) == 1 
			&& characterIndex.get(c) < prevIndex){
                prevIndex = characterIndex.get(c);
                nonRepeatedCharacter = c;
            }
        }
        return nonRepeatedCharacter;
    }
}
package test;

import com.company.FirstNonRepeatingChar;
import org.junit.jupiter.api.Test;

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

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

    FirstNonRepeatingChar tester = new FirstNonRepeatingChar();

    @Test
    public void firstNonRepeatingOptimizedCharExists() {
        String s = "aebcbcbcbcbad";
        assertEquals('e', tester.firstNonRepeatingCharacterOptimized(s));
    }

    @Test
    public void firstNonRepeatingCharOptimizedDoesNotExists() {
        String s = "abcbcbcbcbadd";
        assertEquals(' ', tester.firstNonRepeatingCharacterOptimized(s));
    }

    @Test
    public void firstNonRepeatingCharOptimizedWithEmptyString() {
        String s = "";
        assertEquals(' ', tester.firstNonRepeatingCharacterOptimized(s));
    }

    @Test
    public void firstNonRepeatingCharOptimizedWithNull() {
        assertEquals(' ', tester.firstNonRepeatingCharacterOptimized(null));
    }
}

Please share if there is anything wrong or missing. If you are interested in taking personalized coaching sessions by our expert teachers, please signup to website and get first session free.