Find the skyline of a group of buildings

admin / / Divide and Conquer

© Parineeth M R

Question 61. Find the skyline of a group of buildings

The skyline problem is pretty popular in coding interviews. Here we take an in depth look at how to solve the problem.

Consider the diagram below where there are 4 buildings: B1 (height = 20), B2 (height = 30), B3 (height = 40) and B4 (height = 10).

The resulting skyline of the buildings can be obtained by picking the height of the tallest building at each position. So for instance, at position = 1, the height of the tallest building is 20. At position = 2, the height of the tallest building is 40. The resulting skyline for the buildings is shown below

To solve the problem, let us first develop a notation for representing each building and a notation for representing the resulting skyline. Each building can be represented with its left position, right position and its height. So for instance in the diagram, building B1 can be represented as (left = 1, right = 4, height = 20).

Strip S1 is represented using point P1 (position = 1, height = 20).
Strip S2 is represented using point P2 (position = 2, height = 40).
Strip S3 is represented using point P3 (position = 6, height = 10).

When we indicate the point for the strip, it means that the strip starts at this point and the height of the strip continues till the next skyline point. So in the diagram above for strip S2 having point P2 (position = 2, height = 40), it means that the strip starts at position 2 and has a height of 40 till we reach the next point P3 at position 6

Note that the buildings given to us in the input need not be sorted based on the left position of the building. So for instance, the buildings can be input in the following order: B2, B4, B1, B3.
Brute force – In the brute force technique, we first start with a single building and compute the skyline of the first building. Then we go on adding one building at a time and re-compute the result skyline. This is similar to insertion sort. The result skyline will maintain the points in sorted order based on position. Each time we add a building, we have to find where we can insert it in the result skyline. This operation is O(n). Since we have to do this operation for n buildings, the time complexity is O(n2).

There is a more efficient solution that uses merge sort with time complexity O(nlogn). Given a group of unsorted buildings, we divide the group into two groups: G1 and G2. We then recursively find the skylines for the two groups and then merge the skylines of the two groups to get the result.

So in our example, as we recursively divide the group of buildings, we will finally reach the stage where we get individual buildings B1, B2, B3 and B4. Once we reach this stage, we can represent each building as a strip as shown in the diagram below

Each strip indicates the skyline for a single building. Now we need to recursively merge the skylines to get the final result. Each skyline formed during the merge can consist of one or more strips. The basic idea that we use to merge the skylines is to pick the maximum height of the two input skylines at all the positions. So we maintain two variables: H1 and H2. H1 is the current height of skyline of group 1 and H2 is the current height of skyline in group 2. H1 and H2 are initialized to 0

To merge the two skylines, traverse the two skylines, keep picking the left most point in the two skylines and perform the following
1. If the left most point lies in Group-1, then update the height H1 to the height of the left most point. The height of the result skyline at this point is H = max(H1, H2). Let the position of the left most point be P. Append a new point (P, H) to the result skyline. Then advance to the next point in Group-1.

2. If the left most point lies in Group-2, then update the height H2 to the height of the left most point. The height of the result skyline at this point is H = max(H1, H2). Let the position of the left most point be P. Append a new point (P, H) to the result skyline. Then advance to the next point in Group-2.

3. If the left most point in Group-1 is at the same position as the left most point in Group-2, then update H1 to the height of the left most point in Group-1 and H2 to the height of the left most point in Group-2. The height of the result skyline at this point is H = max(H1, H2). Let the position of the left most point be P. Append a new point (P, H) to the result skyline. Then advance to the next point in Group-1 and Group-2.
When appending a new point to the result skyline, we observe the following rules
– We will not maintain redundant strips in the result skyline. So if the height of new point being added to the result skyline is equal to the height of the last point in the result skyline, then there is no need to add the new point to the result skyline.

– There can’t be two points at the same position in the result skyline. So if the position of the new point being added to the result skyline is equal to the position of the last point in the result skyline, then pick maximum height of the new point and old point and store the maximum height at this position.

Consider the case where we are merging the skylines of building B1 and B2 to get the skyline R1.

At position P1, the height of building B1 is H1 = 20 and height of building B2 is H2 = 0. So max (H1, H2) = 20. So height of result skyline at P1 is 20.
At position P2, the height of B1 is H1 = 20 and height of B2 is H2 = 30. So max(H1, H2) = 30. So height of result skyline at P2 is 30.
At position P3, the height of B1 is H1 = 20 and height of B2 is H2 = 0. So max(H1, H2) = 20. So height of result skyline at P3 is 20.
At position P4, the height of B1 is H1 = 0 and height of B2 is H2 = 0. So max(H1, H2) = 0. So height of result skyline at P4 is 0.

The merging of the skylines B3 and B4 to get the skyline R2 is shown in the diagram below.

The merging of skyline R1 and R2 to get the final skyline result is shown below

The code for computing the skyline is given below

Python


#Main function for computing the skyline. This function is recursive.
#buildings: ArrayList containing information about the buildings. There should be 
#        at least one building. The input buildings need not be sorted
#low: smallest index of the group of building being processed
#high: largest index of the group of buildings being processed
def compute_skyline(buildings, low, high) :

    if (low == high) :
        #We have reached a single building. Create the result skyline
        result = []
        
        #Add the strip corresponding to left end of building to result
        left = buildings[low].left
        height = buildings[low].height
        cur_strip = Strip(left, height)
        result.append(cur_strip)

        #Add the strip corresponding to right end of building to result.
        #For the right end of the building, the height will be 0
        left = buildings[low].right
        height = 0
        cur_strip = Strip(left, height)
        result.append(cur_strip)
        
        #Terminate the recursion and return the result skyline
        return result
    

    #Recursively compute skyline1 for (low, mid) and skyline2 for 
    #(mid+1, high) and then merge the two skylines

    mid = (low + high) // 2
    
    skyline1 = compute_skyline(buildings, low, mid)
    skyline2 = compute_skyline(buildings, mid + 1, high) 

    result = merge(skyline1, skyline2)

    return result


#Helper function that adds the current strip into the end of the skyline
def append(skyline, cur_strip) :
    size = len(skyline)

    #If the current strip to be added and the last strip of the skyline have
    #the  same left position, then pick the max height of the two strips and 
    #update the height of the last strip in the skyline and return
    if (size > 0 and skyline[size - 1].left == cur_strip.left) :
        skyline[size - 1].height = max(skyline[size - 1].height, 
                                        cur_strip.height)
        return
    

    #The current strip to be added has the same height as the last strip in  
    #skyline. So no need to add the current strip since neighboring strips 
    #in skyline should have unique heights. So simply return
    if (size > 0 and skyline[size - 1].height == cur_strip.height) :
        return

    #The current strip to be added starts at a different position and has a 
    #different height than the last strip in the skyline. So add the current 
    #strip to the skyline
    skyline.append(cur_strip) 


#Helper function that merges skyline1 and skyline2 and returns the new merged
#skyline
def  merge(skyline1, skyline2):
                             
    result = []
    i = j = 0
    #h1 keeps track of the current height in skyline1 and h2 keeps track of the
    #current height in skyline2 as we traverse the two skylines
    h1 = h2 = 0

    while (i < len(skyline1) and j < len(skyline2)) :
        #Pick the strip which is leftmost in the two skylines
        if (skyline1[i].left < skyline2[j].left) :
            h1 = skyline1[i].height #update current height of skyline1

            #The height of the strip to be added to the result will have 
            #the maximum of the current heights of the two skylines
            left = skyline1[i].left
            height = max(h1, h2)
            cur_strip = Strip(left, height)
        
            append(result, cur_strip)
            i += 1
        elif (skyline1[i].left == skyline2[j].left):
            h1 = skyline1[i].height #update current height of the skylines
            h2 = skyline2[j].height

            #The height of the strip to be added to the result will have 
            #the maximum of the current heights of the two skylines
            left = skyline1[i].left
            height = max(h1, h2)
            cur_strip = Strip(left, height)
            
            append(result, cur_strip)
            i += 1
            j += 1
        else :
            h2 = skyline2[j].height #update current height of skyline2

            #The height of the strip to be added to the result will have 
            #the maximum of the current heights of the two skylines
            left = skyline2[j].left
            height = max(h1, h2)
            cur_strip = Strip(left, height)

            append(result, cur_strip)
            j += 1
        
    

    #Append the remaining strips in skyline1 to the result
    while (i <  len(skyline1)) :
        append(result, skyline1[i])
        i += 1
    

    #Append the remaining strips in skyline2 to the result
    while (j <  len(skyline2)) :
        append(result, skyline2[j])
        j += 1
    

    return result

C/C++


/*Main function for computing the skyline. This function is recursive.
buildings: vector containing information about the buildings. There should be 
        at least one building. The input buildings need not be sorted
low: smallest index of the group of building being processed
high: largest index of the group of buildings being processed*/
vector<strip> compute_skyline(vector<building_info>& buildings, 
                            int low, int high)
{

    if (low == high) {
        /*We have reached a single building. Create the result skyline*/
        vector<strip> result;
        strip cur_strip;

        /*Add the strip corresponding to left end of building to result*/
        cur_strip.left = buildings[low].left, 
        cur_strip.height = buildings[low].height;
        result.push_back(cur_strip);

        /*Add the strip corresponding to right end of building to result.
        For the right end of the building, the height will be 0*/
        cur_strip.left = buildings[low].right;
        cur_strip.height = 0;
        result.push_back(cur_strip);
        
        /*Terminate the recursion and return the result skyline*/
        return result;
    }

    /*Recursively compute skyline1 for (low, mid) and skyline2 for 
    (mid+1, high) and then merge the two skylines*/

    int mid = (low + high) / 2;
    
    vector<strip> skyline1 = compute_skyline(buildings, low, mid);
    vector<strip> skyline2 = compute_skyline(buildings, mid + 1, high); 

    vector<strip> result = merge(skyline1, skyline2);

    return result;
}

/*Helper function that adds the current strip into the end of the skyline*/
void append(vector<strip>& skyline, strip& cur_strip)
{
    int size = skyline.size();

    /*If the current strip to be added and the last strip of the skyline have
    the  same left position, then pick the max height of the two strips and 
    update the height of the last strip in the skyline and return*/
    if (size && skyline[size - 1].left == cur_strip.left) {
        skyline[size - 1].height = max(skyline[size - 1].height, 
                                        cur_strip.height);
        return;
    }

    /*The current strip to be added has the same height as the last strip in  
    skyline. So no need to add the current strip since neighboring strips 
    in skyline should have unique heights. So simply return*/
    if (size && skyline[size - 1].height == cur_strip.height) 
        return;

    /*The current strip to be added starts at a different position and has a 
    different height than the last strip in the skyline. So add the current 
    strip to the skyline*/
    skyline.push_back(cur_strip); 
}

/*Helper function that merges skyline1 and skyline2 and returns the new merged
skyline*/
vector<strip> merge(vector<strip>& skyline1, 
                            vector<strip>& skyline2)
{
    vector<strip> result;
    int i = 0, j = 0;
    /*h1 keeps track of the current height in skyline1 and h2 keeps track of the
    current height in skyline2 as we traverse the two skylines*/
    int h1 = 0, h2 = 0;
    strip cur_strip;

    while (i < skyline1.size() && j < skyline2.size()) {
        /*Pick the strip which is leftmost in the two skylines*/
        if (skyline1[i].left < skyline2[j].left) {
            h1 = skyline1[i].height; /*update current height of skyline1*/

            /*The height of the strip to be added to the result will have 
            the maximum of the current heights of the two skylines*/
            cur_strip.left = skyline1[i].left;
            cur_strip.height = max(h1, h2);
        
            append(result, cur_strip);
            ++i;
        } else if (skyline1[i].left == skyline2[j].left) {
            h1 = skyline1[i].height; /*update current height of the skylines*/
            h2 = skyline2[j].height;

            /*The height of the strip to be added to the result will have 
            the maximum of the current heights of the two skylines*/
            cur_strip.left = skyline1[i].left;
            cur_strip.height = max(h1, h2);
            
            append(result, cur_strip);
            ++i;
            ++j;
        } else {
            h2 = skyline2[j].height; /*update current height of skyline2*/

            /*The height of the strip to be added to the result will have 
            the maximum of the current heights of the two skylines*/
            cur_strip.left = skyline2[j].left;
            cur_strip.height = max(h1, h2);

            append(result, cur_strip);
            ++j;
        }
    }

    /*Append the remaining strips in skyline1 to the result*/
    while (i <  skyline1.size()) {
        append(result, skyline1[i]);
        ++i;
    }

    /*Append the remaining strips in skyline2 to the result*/
    while (j <  skyline2.size()) {
        append(result, skyline2[j]);
        ++j;
    }

    return result;
}

Java


/*Main function for computing the skyline. This function is recursive.
buildings: ArrayList containing information about the buildings. There should be 
		at least one building. The input buildings need not be sorted
low: smallest index of the group of building being processed
high: largest index of the group of buildings being processed*/
public static ArrayList<Strip>  computeSkyline(BuildingInfo [] buildings, 
							int low, int high) {

	if (low == high) {
		/*We have reached a single building. Create the result skyline*/
		ArrayList<Strip> result = new ArrayList<Strip>();

		/*Add the strip corresponding to left end of building to result*/
		Strip curStrip = new Strip();
		curStrip.left = buildings[low].left;
		curStrip.height = buildings[low].height;
		result.add(curStrip);

		/*Add the strip corresponding to right end of building to result.
		For the right end of the building, the height will be 0*/
		curStrip = new Strip();
		curStrip.left = buildings[low].right;
		curStrip.height = 0;
		result.add(curStrip);

		/*Terminate the recursion and return the result skyline*/
		return result;
	}

	/*Recursively compute skyline1 for (low, mid) and skyline2 for 
	(mid+1, high) and then merge the two skylines*/

	int mid = (low + high) / 2;

	ArrayList<Strip> skyline1 = computeSkyline(buildings, low, mid);
	ArrayList<Strip> skyline2 = computeSkyline(buildings, mid + 1, high); 

	ArrayList<Strip> result = merge(skyline1, skyline2);

	return result;
}

/*Helper function that adds the current strip into the end of the skyline*/
public static void append(ArrayList<Strip> skyline, Strip curStrip) {
	int size = skyline.size();

	/*If the current strip to be added and the last strip of the skyline have
	the  same left position, then pick the max height of the two strips and 
	update the height of the last strip in the skyline and return*/
	if (size > 0 && skyline.get(size - 1).left == curStrip.left) {
		skyline.get(size - 1).height = Math.max(skyline.get(size - 1).height, 
										curStrip.height);
		return;
	}

	/*The current strip to be added has the same height as the last strip in  
	skyline. So no need to add the current strip since neighboring strips 
	in skyline should have unique heights. So simply return*/
	if (size > 0 && skyline.get(size - 1).height == curStrip.height) 
		return;

	/*The current strip to be added starts at a different position and has a 
	different height than the last strip in the skyline. So add the current 
	strip to the skyline*/
	skyline.add(curStrip); 
}

/*Helper function that merges skyline1 and skyline2 and returns the new merged
skyline*/
public static ArrayList <Strip> merge(ArrayList<Strip> skyline1, 
							ArrayList<Strip> skyline2) {
	ArrayList <Strip> result = new ArrayList <Strip>();
	int i = 0, j = 0;
	/*h1 keeps track of the current height in skyline1 and h2 keeps track of the
	current height in skyline2 as we traverse the two skylines*/
	int h1 = 0, h2 = 0;
	Strip curStrip;

	while (i < skyline1.size() && j < skyline2.size()) {
		/*Pick the strip which is leftmost in the two skylines*/
		if (skyline1.get(i).left < skyline2.get(j).left) {
			h1 = skyline1.get(i).height; /*update current height of skyline1*/

			/*The height of the strip to be added to the result will have 
			the maximum of the current heights of the two skylines*/
			curStrip = new Strip();
			curStrip.left = skyline1.get(i).left;
			curStrip.height = Math.max(h1, h2);

			append(result, curStrip);
			++i;
		} else if (skyline1.get(i).left == skyline2.get(j).left) {
			h1 = skyline1.get(i).height; /*update current height of the skylines*/
			h2 = skyline2.get(j).height;

			/*The height of the strip to be added to the result will have 
			the maximum of the current heights of the two skylines*/
			curStrip = new Strip();
			curStrip.left = skyline1.get(i).left;
			curStrip.height = Math.max(h1, h2);

			append(result, curStrip);
			++i;
			++j;
		} else {
			h2 = skyline2.get(j).height; /*update current height of skyline2*/

			/*The height of the strip to be added to the result will have 
			the maximum of the current heights of the two skylines*/
			curStrip = new Strip();
			curStrip.left = skyline2.get(j).left;
			curStrip.height = Math.max(h1, h2);

			append(result, curStrip);
			++j;
		}
	}

	/*Append the remaining strips in skyline1 to the result*/
	while (i <  skyline1.size()) {
		append(result, skyline1.get(i));
		++i;
	}

	/*Append the remaining strips in skyline2 to the result*/
	while (j <  skyline2.size()) {
		append(result, skyline2.get(j));
		++j;
	}

	return result;
}

What could possibly be wrong with the C declaration char x;?

admin / / C

© Parineeth M R

Consider the code below:

C/C++



void f1()
{
    char x = -1;
    int y = 0;
    
    y = y + x;

    printf("%d\n", y);
}

We expect that the output printed is -1. However this is not true in all the platforms.

When we declare a variable as int x, we are sure that the variable x is a signed integer even if we don’t specify the “signed” keyword in the declaration. Similarly, we expect that the declaration char x is equivalent to the declaration signed char x.

“The C Programming Language” book by Kernighan & Ritchie states that “Whether plain chars are signed or unsigned is machine-dependent, but printable characters are always positive.” So if we declare char x, then the variable x can be treated as a signed char in some platforms whereas it can be treated as an unsigned char in some platforms. This can create portability problems.

So if char x is treated as a signed char by the platform, then the output is -1. You can confirm this by invoking the function below

C/C++

void f1()
{
    signed char x = -1;
    int y = 0;
    
    y = y + x;

    printf("%d\n", y);
}

However, if char x is treated as an unsigned char by the platform, then the output is 255. You can confirm this by invoking the function below

C/C++

void f1()
{
    unsigned char x = -1;
    int y = 0;
    
    y = y + x;

    printf("%d\n", y);
}

In most platforms, char x is treated as signed char x. However there is the occasional odd platform where char x is treated as unsigned char. I ran into one such platform in my career and started getting weird bugs in the code which took quite some time to debug.

So to keep the code truly portable, explicitly declare as signed char or unsigned char.

© Parineeth M R

Cycle in a directed graph

admin / / Algorithms, Graph Algorithms

© Parineeth M R

Question 60. Find if a directed graph has a cycle

Suppose we are given an undirected graph and asked to find a cycle in it, then all we need to do is the following

1. Initialize all nodes in the graph as unvisited.

2. Pick a node that has not been visited and recursively traverse its neighbors and their neighbors and so on using depth first search. Once we traverse a node, we will mark it as visited.

3. Repeat step 2 until all the nodes in the graph are visited.

While traversing the graph, if we encounter a node that has already been visited, then there is a cycle in the undirected graph.

We can’t apply the same procedure for a directed graph. Consider the diagram below

Suppose we start from node 0 and apply DFS. We first traverse the edge from node 0 to node 1. Then from node 1 we reach node 2. So nodes 0, 1 and 2 have been visited. Then we traverse the edge from 0 to 2. But node 2 has already been visited. Since we encounter a node that we have already visited, we conclude that there is a cycle in the directed graph. However this is incorrect since there is no directed cycle in this directed graph. If we had an edge from node 2 to node 0 instead of an edge from node 0 to node 2, then the graph has a directed cycle in it.

To overcome this problem, instead of just maintaining two states whether the node has been visited or not, we maintain 3 states that are identified using colors

– White: the node has not yet been processed

– Gray: the node is currently being processed. This means that the node’s neighbors and their neighbors and so on are still being expanded

– Black: the node has been completely processed. This means that all the nodes that are reachable from this node have been traversed

During depth first search, if we encounter a node whose color is already gray, then it means that there is a cycle in the directed graph.

Using this approach, let us traverse the above directed graph. Initially all nodes are white. When we start with node 0, we change the color of 0 to gray. From 0 we move to 1. So node 1 now becomes gray. From 1 we reach 2. The color of 2 becomes gray. From 2 we try to traverse further. But there are no nodes reachable from 2. So we have finished processing node 2 and change its color to black. Then we check if we can reach another node from node 1. There are no new nodes that we can reach from node 1. So we change color of 1 to black and come back to node 0. From node 0 we can reach node 2. The color of node 2 is black. If color of 2 was still grey, then it means that there is a loop in the graph. In this case, since color of 2 is black, there is no loop in the graph.

To simplify the implementation, the nodes in the graph will be represented by integers. For each node in the graph, we will be storing its neighboring nodes as shown in the table below:

C/C++


/* Helper function that performs depth first search on the graph
cur_node: the current node that we are searching
adjacency_table: an array of vectors. If there is an edge from node 0 to 
	node 5, then adjacency_table[0] is a vector which stores 5 in it
color: this array indicates the color assigned to the nodes
num_nodes: total number of nodes in the graph
Return value: true if cycle exists in directed graph, false otherwise
*/
bool dfs(int cur_node, vector<int> adjacency_table[], int color[], int num_nodes)
{
	bool does_cycle_exist = false;
	unsigned int j;
	vector<int>& neighbors = adjacency_table[cur_node];

	/*Assign the gray color to the node indicating that we have 
	started processing this node*/
	color[cur_node] = GRAY;

	for (j = 0; j < neighbors.size(); ++j) {
		int cur_neighbor = neighbors[j];

		/*If we find a neighboring node with the gray color, then we 
		have found a loop*/
		if (color[cur_neighbor] == GRAY) {
			return true;
		}

		/*If the neighboring node has a white color, then perform 
		DFS on it*/
		if (color[cur_neighbor] == WHITE) {
			does_cycle_exist = dfs(cur_neighbor, adjacency_table, 
						color, num_nodes);
			if (does_cycle_exist)
				return true;
		}
	}

	/*Assign the node the black color to indicate that we have finished 
	processing it*/
	color[cur_node] = BLACK;
	return false;	
}

 
/* Main function that checks if cycle is present or not
adjacency_table: an array of vectors. If there is an edge from node 0 
	to node 5, then adjacency_table[0] is a vector which stores 5 in it
num_nodes: total number of nodes in the graph
Return value: true if cycle is present in directed graph, false otherwise
*/
bool is_cycle_present(vector<int> adjacency_table[], int num_nodes)
{
	int *color = new int[num_nodes];
	int i; 
	bool does_cycle_exist = false;

	/*Assign the white color to all the nodes to indicate that we have 
	not started processing the nodes*/
	for (i = 0; i < num_nodes; ++i) 
		color[i] = WHITE;

	/*Go through all the nodes in the graph and perform DFS on the nodes 
	whose color is white*/
	for (i = 0; i < num_nodes; ++i) {
		if (color[i] == WHITE) {
			does_cycle_exist = dfs(i, adjacency_table, color, 
						num_nodes);
			if (does_cycle_exist) 
				break;
		}
	}

	delete [] color; 
	return does_cycle_exist;
}

Java


/*Helper function that performs depth first search on the graph
curNode: the current node that we are searching
adjacencyTable: an ArrayList of ArrayLists. If there is an edge between node 0
and node 5, then adjacencyTable[0] is an ArrayList which stores 5 in it.
color: this array indicates color assigned to the nodes
numNodes: total number of nodes in the graph
Return value: true if cycle exists in directed graph, false otherwise
*/
public static boolean dfs(int curNode, 
		ArrayList<ArrayList<Integer>> adjacencyTable, 
		int[] color, int numNodes) {
	boolean doesCycleExist = false;
	ArrayList<Integer> neighbors = adjacencyTable.get(curNode);

	/*Assign the gray color to the node indicating that we have 
	started processing this node*/
	color[curNode] = GRAY;

	for (int j = 0; j < neighbors.size(); ++j) {
		int curNeighbor = neighbors.get(j);

		/*If we find a neighboring node with the gray color, then we 
		have found a loop*/
		if (color[curNeighbor] == GRAY) {
			return true;
		}

		/*If the neighboring node has a white color, then perform 
		DFS on it*/
		if (color[curNeighbor] == WHITE) {
			doesCycleExist = dfs(curNeighbor, adjacencyTable, 
						color, numNodes);
			if (doesCycleExist)
				return true;
		}
	}

	/*Assign the node the black color to indicate that we have 
	finished processing it*/
	color[curNode] = BLACK;
	return false;	
}

 
/* Main function that checks if cycle is present or not
adjacencyTable: an ArrayList of ArrayLists. If there is an edge between node 0
and node 5, then adjacencyTable[0] is an ArrayList which stores 5 in it.
numNodes: total number of nodes in the graph
Return value: true if cycle is present in directed graph, false otherwise
*/
public static boolean isCyclePresent(
			ArrayList<ArrayList<Integer>> adjacencyTable, 
			int numNodes) {
	int[] color = new int[numNodes];
	boolean doesCycleExist = false;

	/*Assign the white color to all the nodes to indicate that we have not 
	started processing the nodes*/
	int i;
	for (i = 0; i < numNodes; ++i)
		color[i] = WHITE;

	/*Go through all the nodes in the graph and perform DFS on the 
	nodes whose color is white*/
	for (i = 0; i < numNodes; ++i) {
		if (color[i] == WHITE) {
			doesCycleExist = dfs(i, adjacencyTable, 
						color, numNodes);
			if (doesCycleExist) 
				break;
		}
	}

	return doesCycleExist;
}

Python


#Helper function that performs depth first search on the graph
#cur_node: the current node that we are searching
#adjacency_table: a list of lists. If there is an edge between node 0 and 
#	 node 5, then adjacency_table[0] is a list which stores 5 in it.
#color: this list indicates color assigned to the node
#num_nodes: total number of nodes in the graph
#Return value: True if cycle is present in directed graph, False otherwise
def dfs(cur_node, adjacency_table, color, num_nodes) :
	does_cycle_exist = False
	neighbors = adjacency_table[cur_node]

	#Assign the gray color to the node indicating that we have started 
	#processing this node
	color[cur_node] = GRAY

	for  j in range(0, len(neighbors)):
		cur_neighbor = neighbors[j]

		#If we find a neighboring node with the gray color, then we 
		#have found a loop
		if (color[cur_neighbor] == GRAY) :
			return True
		
		#If the neighboring node has a white color, then perform 
		#DFS on it
		if (color[cur_neighbor] == WHITE) :
			does_cycle_exist = dfs(cur_neighbor, adjacency_table, 
						color, num_nodes)
			if (does_cycle_exist):
				return True
	
	#Assign the node the black color to indicate that we have finished 
	#processing it
	color[cur_node] = BLACK
	return False


 
#Main function that checks if cycle is present or not
#adjacency_table: a list of lists. If there is an edge between node 0 and 
#	node 5, then adjacency_table[0] is a list which stores 5 in it.
#num_nodes: total number of nodes in the graph
#Return value: True if cycle is present in directed graph, False otherwise
def is_cycle_present(adjacency_table, num_nodes) :
	does_cycle_exist = False

	#Assign the white color to all the nodes to indicate that we have not 
	#started processing the nodes
	color = [WHITE] * num_nodes
	
	#Go through all the nodes in the graph and perform DFS on the 
	#nodes whose color is white
	for  i in range(0, num_nodes):
		if (color[i] == WHITE) :
			does_cycle_exist = dfs(i, adjacency_table, 
						color, num_nodes)
			if (does_cycle_exist) :
				break
			
	return does_cycle_exist

Find the number of islands in a matrix

admin / / Algorithms, Miscellaneous Algorithms

© Parineeth M R

Question 59. A 2-dimensional matrix consists of 0’s and 1’s. An island is defined as a contiguous occurrence of 1’s that are adjacent to each other. Find the number of islands in the matrix

If there are two adjacent cells (left-right neighbors, top-down neighbors, diagonally adjacent neighbors) with a value 1, then the two cells belong to the same island. In the matrix below there are 3 islands. The cells A0, B1, C0, D0 and E0 form one island. The cells A3, B3, C3 and B4 form one island. The cell E3 forms the remaining island.

To find the number of islands, we make use of recursion. Once we find a cell whose value is 1, we start with the neighbors of this cell and recursively visit all cells that are reachable from this cell. To prevent from going into loops, we keep track if a cell has been visited or not and once a cell has been visited, we don’t visit it again.

A similar problem is the flood fill problem. The color at each pixel of an image is stored in a 2 dimensional matrix. Given the starting pixel and the new color, we have to change the color of all adjacent pixels that have the same color as the starting pixel. So if the starting pixel A[2][3] is red and the new color is blue, then we have to recursively find all red cells that are reachable from A[2][3] and change their color to blue.

In some cases, diagonal neighbors may not be considered as adjacent. It is better to clarify this with the interviewer.

C/C++


/*
Helper function that indicates if we can enter the cell or not
*/
int can_enter_cell(int matrix[][MAX_NUM_COLS], int is_visited[][MAX_NUM_COLS], 
		int cur_row, int cur_col, int n_rows, int n_cols)
{
	/*If we are outside the bounds of the matrix or
	if the cell is already visited or if the value in cell is 0
	then we shouldn't enter the cell */
	if (cur_row < 0 || cur_row >= n_rows 
	    || cur_col < 0 || cur_col >= n_cols
	    || is_visited[cur_row][cur_col] 
	    || matrix[cur_row][cur_col] == 0) {
		return 0;
	}

	return 1;
}


/* Helper function to count the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's
is_visited: if cell (i, j) has been visited, is_visited[i][j] is set to 1
cur_row: row of the current cell being processed
cur_col: column of the current cell being processed
n_rows: number of rows in the matrix
n_cols: number of columns in the matrix 
*/
void expand_search(int matrix[][MAX_NUM_COLS], int is_visited[][MAX_NUM_COLS], 
	int cur_row, int cur_col, int n_rows, int n_cols)
{
	int i, j;

	is_visited[cur_row][cur_col] = 1;

	/*For the current cell, find out if we can continue the island of 1's
	with its neighbors. Each cell has 9 neighbors. The rows
	of neighbors will vary from cur_row - 1 to cur_row + 1
	The columns of the neighbors will vary from cur_col - 1
	to cur_col + 1*/
	for (i = -1; i <= 1; ++i) {
		for (j = -1; j <= 1; ++j) {
			int is_safe_cell = can_enter_cell(matrix, is_visited,  
					cur_row+i, cur_col+j, n_rows, n_cols);

			if (is_safe_cell) {
				expand_search(matrix, is_visited, cur_row+i, 
						cur_col+j, n_rows, n_cols);
			}
		}
	}
}


/* Main function to find the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's. Should not be empty
n_rows: number of rows in the matrix. Should be >= 1
n_cols: number of columns in the matrix. Should be >= 1 
*/
int find_islands(int matrix[][MAX_NUM_COLS], int n_rows, int n_cols)
{
	int is_visited[MAX_NUM_ROWS][MAX_NUM_COLS];
	int i, j, count;

	/*Initially all cells are not yet visited*/
	for (i = 0; i < n_rows; ++i)
		for (j = 0; j < n_cols; ++j) 
			is_visited[i][j] = 0;

	/*Search all the cells in matrix that are not yet visited*/
	count = 0;
	for (i = 0; i < n_rows; ++i) {
		for (j = 0; j < n_cols; ++j) {
			if (matrix[i][j] && !is_visited[i][j]) {
				/*We have found an island. Now expand the island 
				in all directions*/
				expand_search(matrix, is_visited, i, j, 
						n_rows, n_cols);
				++count;
			}
		}
	}
	return count;
}

Java


/* Helper function that indicates if we can enter the cell or not*/
public static boolean canEnterCell(int[][] matrix, boolean[][] isVisited, 
				int curRow, int curCol) {
	int nRows = matrix.length;
	int nCols = matrix[0].length;

	/*If we are outside the bounds of the matrix or
	if the cell is already visited or if the value in cell is 0
	then we shouldn't enter the cell */
	if (curRow < 0 || curRow >= nRows 
	    || curCol < 0 || curCol >= nCols
	    || isVisited[curRow][curCol] 
	    || matrix[curRow][curCol] == 0) {
		return false;
	}

	return true;
}


/* Helper function to count the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's
isVisited: if cell (i, j) has been visited, isVisited[i][j] is set to true
curRow: row of the current cell being processed
curCol: column of the current cell being processed
*/
public static void expandSearch(int[][] matrix, boolean[][] isVisited, int curRow, int curCol) {
	int nRows = matrix.length; 
	int nCols = matrix[0].length;

	isVisited[curRow][curCol] = true;

	/*For the current cell, find out if we can continue the island of 1's
	with its neighbors. Each cell has 9 neighbors. The rows
	of neighbors will vary from curRow - 1 to curRow + 1
	The columns of the neighbors will vary from curCol - 1
	to curCol + 1*/
	for (int i = -1; i <= 1; ++i) {
		for (int j = -1; j <= 1; ++j) {
			boolean isSafeCell = canEnterCell(matrix, isVisited, curRow+i, 
								curCol+j);

			if (isSafeCell) {
				expandSearch(matrix, isVisited, curRow+i, curCol+j);
			}
		}
	}
}

 
/* Main function to find the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's. Should not be empty
*/
public static int findIslands(int[][] matrix) {
	int nRows = matrix.length; 
	int nCols = matrix[0].length;
	boolean[][] isVisited = new boolean[nRows][nCols];

	/*Initially all cells are not yet visited*/
	int i, j;
	for (i = 0; i < nRows; ++i)
		for (j = 0; j < nCols; ++j) 
			isVisited[i][j] = false;

	/*Search all the cells in matrix that are not yet visited*/
	int count = 0;
	for (i = 0; i < nRows; ++i) {
		for (j = 0; j < nCols; ++j) {
			if (matrix[i][j] == 1 && !isVisited[i][j]) {
				/*We have found an island. Now expand the island 
				in all directions*/
				expandSearch(matrix, isVisited, i, j);
				++count;
			}
		}
	}
	return count;
}

Python


#Helper function that indicates if we can enter the cell or not
def can_enter_cell(matrix, is_visited, cur_row, cur_col) :
	n_rows = len(matrix)
	n_cols = len(matrix[0])

	#If we are outside the bounds of the matrix or
	#if the cell is already visited or if the value in cell is 0
	#then we shouldn't enter the cell
	if (cur_row < 0 or cur_row >= n_rows 
	    or cur_col < 0 or cur_col >= n_cols
	    or is_visited[cur_row][cur_col] 
	    or matrix[cur_row][cur_col] == 0) :
		return False
	

	return True


#Helper function to count the number of islands of 1's
#matrix: 2-D matrix consisting of 0's and 1's
#is_visited: if cell (i, j) has been visited, is_visited[i][j] is set to True
#cur_row: row of the current cell being processed
#cur_col: column of the current cell being processed
def expand_search(matrix, is_visited, cur_row, cur_col) :
	n_rows = len(matrix) 
	n_cols = len(matrix[0])

	is_visited[cur_row][cur_col] = True

	#For the current cell, find out if we can continue the island of 1's
	#with its neighbors. Each cell has 8 neighbors. The rows
	#of neighbors will vary from cur_row - 1 to cur_row + 1
	#The columns of the neighbors will vary from cur_col - 1
	#to cur_col + 1
	for  i in range(-1, 2):
		for  j in range(-1, 2):
			is_safe_cell = can_enter_cell(matrix, is_visited, cur_row+i, 
								cur_col+j)

			if (is_safe_cell) :
				expand_search(matrix, is_visited, cur_row+i, cur_col+j)

 
#Main function to find the number of islands of 1's
#matrix: 2-D matrix consisting of 0's and 1's. Should not be empty
def find_islands(matrix) :
	n_rows = len(matrix) 
	n_cols = len(matrix[0])
	is_visited = [ [False for x in range(n_cols)] for x in range(n_rows)]

	#Search all the cells in matrix that are not yet visited
	count = 0
	for  i in range(0, n_rows):
		for  j in range(0, n_cols):
			if (matrix[i][j] == 1 and not is_visited[i][j]) :
				#We have found an island. Now expand the island 
				#in all directions
				expand_search(matrix, is_visited, i, j)
				count += 1
			
	return count

Sudoku solver

admin / / Algorithms, Miscellaneous Algorithms

© Parineeth M R

Question 58. Implement a Sudoku solver

The Sudoku grid is square of size 9 * 9. The rules of Sudoku are as follows:

1. Each cell contains a number from 1 to 9

2. A number should not be repeated in the same row or the same column

3. The grid is further sub-divided into squares of 3*3 called boxes. A number should also not be repeated in the same box.

In the Sudoku puzzle, the puzzle writer fills up some of the cells with numbers and we have to fill up the remaining cells. To solve Sudoku, we make use of recursion and back-tracking. Given a cell, we recursively try out all possible numbers that can be filled up in the cell. So we fill a cell with a possible number and then move to the next cell. Suppose we hit a dead-end at a cell and can’t fill it with any number, then we back-track to the previous cell, try out the next possible number in the previous cell and proceed. To distinguish between the cells filled up by the puzzle writer and the other cells, we initialize the other cells with -1.

C/C++


 /* Helper function which checks if it is possible to place a number in a cell
grid: the 2d sudoku matrix
row_nr: row number of the cell we are checking
col_nr: column number of the cell we are checking
num: the number which we want to place in the cell
Returns: 1 if we can place num in the cell, 0 otherwise
*/
int can_fill_cell(int grid[][NUM_COLS], int row_nr, int col_nr, int num)
{
	int i, j;
	int region_start_row, region_start_col;

	/*Ensure that the number is not present in any row of requested column*/
	for (i = 0; i < NUM_ROWS; ++i)
		if (grid[i][col_nr] == num)
			return 0;

	/*Ensure that the number is not present in any column of requested row*/
	for (j = 0; j < NUM_COLS; ++j)
		if (grid[row_nr][j] == num)
			return 0;

	/*Ensure that the number is not present in the 3*3 box it belongs to*/
	region_start_row = (row_nr / 3) * 3;
	region_start_col = (col_nr / 3) * 3;

	for (i = region_start_row; i < region_start_row + 3; ++i)
		for (j = region_start_col; j < region_start_col + 3; ++j)
			if (grid[i][j] == num)
				return 0;

	return 1;
}

/*Main function for solving the sudoku puzzle
grid: the 2d sudoku matrix
row_nr: row number of the current cell being processed
col_nr: column number of the current cell being processed
*/
void solve_sudoku(int grid[][NUM_COLS], int row_nr, int col_nr)
{
	int next_row, next_col, num;

	if (row_nr >= NUM_ROWS) {
		/*We have found a solution. print the grid and
		terminate the recursion*/
		print_grid(grid, 1);
		return;
	}

	/*Pre-compute the row and column of the next cell*/
	next_row = row_nr;
	next_col = col_nr + 1;
	if (next_col >= NUM_COLS) {
		next_col = 0;
		next_row = row_nr + 1;
	}

	if (grid[row_nr][col_nr] == -1) {
		/*The puzzle writer has not assigned a number to this cell.
		So try assigning numbers 1-9 to the cell*/
		for (num = 1; num <= 9; ++num) {
			if (can_fill_cell(grid, row_nr, col_nr, num)) {
				grid[row_nr][col_nr] = num;
				solve_sudoku(grid, next_row, next_col);
			}
		}
		/*Once we are done trying all numbers from 1-9 assign the cell
		back to -1 to indicate puzzle writer has not assigned a number 
		to the cell*/
		grid[row_nr][col_nr] = -1;

	} else {
		/*The puzzle writer has already assigned a value to the cell. 
		So proceed to the next cell*/
		solve_sudoku(grid, next_row, next_col);
	}
}

Java


/* Helper function which checks if it is possible to place a number in a cell
grid: the 2d sudoku matrix
rowNr: row number of the cell we are checking
colNr: column number of the cell we are checking
num: the number which we want to place in the cell
Returns: true if we can place num in the cell, false otherwise
*/
public static boolean canFillCell(int[][] grid, int rowNr, int colNr, int num) {

	/*Ensure that the number is not present in any row of requested column*/
	int i, j;
	for (i = 0; i < NUM_ROWS; ++i)
		if (grid[i][colNr] == num)
			return false;

	/*Ensure that the number is not present in any column of requested row*/
	for (j = 0; j < NUM_COLS; ++j)
		if (grid[rowNr][j] == num)
			return false;

	/*Ensure that the number is not present in the 3*3 box it belongs to*/
	int regionStartRow = (rowNr / 3) * 3;
	int regionStartCol = (colNr / 3) * 3;
 
	for (i = regionStartRow; i < regionStartRow + 3; ++i)
		for (j = regionStartCol; j < regionStartCol + 3; ++j)
			if (grid[i][j] == num)
				return false;

	return true;
}

/*Main function for solving the sudoku puzzle
grid: the 2d sudoku matrix
rowNr: row number of the current cell being processed
colNr: column number of the current cell being processed
*/
public static void solveSudoku(int[][] grid, int rowNr, int colNr) {

	if (rowNr >= NUM_ROWS) {
		/*We have found a solution. print the grid and
		terminate the recursion*/
		printGrid(grid, true);
		return;
	}

	/*Pre-compute the row and column of the next cell*/
	int nextRow = rowNr;
	int nextCol = colNr + 1;
	if (nextCol >= NUM_COLS) {
		nextCol = 0;
		nextRow = rowNr + 1;
	}

	if (grid[rowNr][colNr] == -1) {
		/*The puzzle writer has not assigned a number to this cell.
		So try assigning numbers 1-9 to the cell*/
		for (int num = 1; num <= 9; ++num) {
			if (canFillCell(grid, rowNr, colNr, num)) {
				grid[rowNr][colNr] = num;
				solveSudoku(grid, nextRow, nextCol);
			}
		}
		/*Once we are done trying all numbers from 1-9 assign the cell
		back to -1 to indicate puzzle writer has not assigned a number 
		to the cell*/
		grid[rowNr][colNr] = -1;

	} else {
		/*The puzzle writer has already assigned a value to the cell. 
		So proceed to the next cell*/
		solveSudoku(grid, nextRow, nextCol);
	}
}

Python


#Helper function which checks if it is possible to place a number in a cell
#grid: the 2-D sudoku matrix
#row_nr: row number of the cell we are checking
#col_nr: column number of the cell we are checking
#num: the number which we want to place in the cell
#Returns: True if we can place num in the cell, False otherwise
def can_fill_cell(grid, row_nr, col_nr, num) :
	#Ensure that the number is not present in any row of requested column
	for  i in range(0, NUM_ROWS):
		if (grid[i][col_nr] == num):
			return False

	#Ensure that the number is not present in any column of requested row
	for  j in range(0, NUM_COLS):
		if (grid[row_nr][j] == num):
			return False

	#Ensure that the number is not present in the 3*3 box it belongs to
	region_start_row = (row_nr // 3) * 3
	region_start_col = (col_nr // 3) * 3
 
	for  i in range(region_start_row, region_start_row + 3):
		for  j in range(region_start_col, region_start_col + 3):
			if (grid[i][j] == num):
				return False

	return True


#Main function for solving the sudoku puzzle
#grid: the 2-D sudoku matrix
#row_nr: row number of the current cell being processed
#col_nr: column number of the current cell being processed
def solve_sudoku(grid, row_nr, col_nr) :
	if (row_nr >= NUM_ROWS) :
		#We have found a solution. print the grid and
		#terminate the recursion
		print_grid(grid, True)
		return
	
	#Pre-compute the row and column of the next cell
	next_row = row_nr
	next_col = col_nr + 1
	if (next_col >= NUM_COLS) :
		next_col = 0
		next_row = row_nr + 1
	
	if (grid[row_nr][col_nr] == -1) :
		#The puzzle writer has not assigned a number to this cell.
		#So try assigning numbers 1-9 to the cell
		for  num in range(1, 10):
			if (can_fill_cell(grid, row_nr, col_nr, num)) :
				grid[row_nr][col_nr] = num
				solve_sudoku(grid, next_row, next_col)
			
		#Once we are done trying all numbers from 1-9, assign the cell
		#back to -1 to indicate puzzle writer has not assigned a number 
		#to the cell
		grid[row_nr][col_nr] = -1

	else :
		#The puzzle writer has already assigned a value to the cell. 
		#So proceed to the next cell
		solve_sudoku(grid, next_row, next_col)

Snake and ladders game

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 57. Find the least number of dice throws needed to complete the snake and ladders game

To find the least number of dice throws, we use the following dynamic programming technique:

1. Initialize the least number of throws needed to reach the positions 1-6 on the board as 1 since we can reach these positions with a single dice throw of a 6-sided dice

2. For any remaining position, we can either reach it from
• any of the previous 6 positions with one dice throw. If there is a snake at a previous position, then we ignore that cell while calculating the least number of throws for the current position

• or we can reach it by a ladder if present from some previous position. If there is a ladder from position I to position P, and we need N throws to reach I, then we can reach P also in N throws.

So we use the formula below to calculate the least number of throws for positions greater than 6

3. The least number of throws to reach the final position of the board gives the least number of throws needed to complete the game

C/C++


/*is_snake: if there is a snake at position 20, then is_snake[20] is set to 1
ladder: if there is a ladder from position 30 to 44, then ladder[44] = 30.
	if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to 
	current position with least number of dice throws. If predecessor[100]   
	= 95, then we reached 100 from 95. It is computed and returned. 
Return value: least number of throws to reach the final position on the board
*/
int find_least_throws(int is_snake[], int ladder[], int predecessor[]) 
{
	/*for a particular position pos on the board, least_throws[pos] will store
	the least number of dice throws required to reach the position*/
	int least_throws[MAX_POSITIONS_ON_BOARD + 1];
	int min_throws, i;
	int pos, prev_pos, ladder_start_pos;

	/*Positions from 1 to 6 can be reached from a single dice throw*/
	for (pos = 1; pos <= 6; pos++) {
		least_throws[pos] = 1;
		predecessor[pos] = 0;
	}

	for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
		min_throws = MAX_POSITIONS_ON_BOARD;

		/*Find how many dice throws are needed to reach pos from any of 
		the 6 previous cells*/
		for (i = 1; i <= 6; ++i) {
			prev_pos = pos - i;

			if (is_snake[prev_pos])
				continue;

			/*Pick the minimum throws needed from the 6 previous cells*/
			if (least_throws[prev_pos] + 1 < min_throws) {
				min_throws = least_throws[prev_pos] + 1;
				predecessor[pos] = prev_pos;
			}
		}

		/*Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
		from 4 to 14. So number of dice throws needed to reach 14 = number of 
		dice throws needed to reach position 4*/
		ladder_start_pos = ladder[pos];
		if (ladder_start_pos != -1) {
			if (least_throws[ladder_start_pos] < min_throws) {
				min_throws = least_throws[ladder_start_pos];
				predecessor[pos] = ladder_start_pos;
			}
		}

		least_throws[pos] = min_throws;
	}
	return least_throws[MAX_POSITIONS_ON_BOARD];
}

Java


/*isSnake: if there is a snake at position 20, isSnake[20] is true
ladder: if there is a ladder from position 30 to 44, then ladder[44] = 30.
	if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to 
	current position with least number of dice throws. If predecessor[100]   
	= 95, then we reached 100 from 95. It is computed and returned. 
Return value: least number of throws to reach the final position on the board
*/
public static int findLeastThrows(boolean[] isSnake, int[] ladder, 
					int[] predecessor) {
	/*for a particular position pos on board, leastThrows[pos] will store
	the least number of dice throws required to reach the position*/
	int[] leastThrows = new int [MAX_POSITIONS_ON_BOARD + 1];

	/*All positions from 1 to 6 can be reached from a single dice throw*/
	int pos;
	for (pos = 1; pos <= 6; pos++) {
		leastThrows[pos] = 1;
		predecessor[pos] = 0;
	}

	for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
		int minThrows = MAX_POSITIONS_ON_BOARD;

		/*Find how many dice throws are needed to reach pos from any of
		the 6 previous cells*/
		for (int i = 1; i <= 6; ++i) {
			int prevPos = pos - i;

			if (isSnake[prevPos])
				continue;

			/*Pick minimum throws needed from the 6 previous cells*/
			if (leastThrows[prevPos] + 1 < minThrows) {
				minThrows = leastThrows[prevPos] + 1;
				predecessor[pos] = prevPos;
			}
		}

		/*Suppose we are at pos = 14 and ladder[14] = 4, then there is 
		a ladder from 4 to 14. So number of dice throws needed to reach 
		14 = number of dice throws needed to reach position 4*/
		int ladderStartPos = ladder[pos];
		if (ladderStartPos != -1) {
			if (leastThrows[ladderStartPos] < minThrows) {
				minThrows = leastThrows[ladderStartPos];
				predecessor[pos] = ladderStartPos;
			}
		}

		leastThrows[pos] = minThrows;
	}
	return leastThrows[MAX_POSITIONS_ON_BOARD];
}

Python


#is_snake: if there is a snake at position 20, is_snake[20] is set to True
#ladder:  if there is a ladder from position 30 to 44, then ladder[44] = 30.
#	if there is no ladder at location 90 then ladder[90] = -1
#Return value:  1. least number of throws to reach the position on the board
#		2. predecessor list
def find_least_throws(is_snake, ladder) :

	#for a particular position pos on the board, least_throws[pos] will store
	#the least number of dice throws required to reach the position
	least_throws = [0] * (MAX_POSITIONS_ON_BOARD + 1)

	#predecessor list has the previous board position from where we came to 
	#current position with least number of dice throws. If predecessor[100]   
	# = 95, then we reached 100 from 95.
	predecessor = [0] * (MAX_POSITIONS_ON_BOARD + 1) 

	#All positions from 1 to 6 can be reached from a single dice throw
	for  pos in range(1, 7):
		least_throws[pos] = 1
		predecessor[pos] = 0
	
	for  pos in range(7, MAX_POSITIONS_ON_BOARD+1):
		min_throws = MAX_POSITIONS_ON_BOARD

		#Find how many dice throws are needed to reach pos from any of 
		#the 6 previous cells
		for  i in range(1, 7):
			prev_pos = pos - i

			if (is_snake[prev_pos]):
				continue

			#Pick the minimum throws needed from the 6 previous cells
			if (least_throws[prev_pos] + 1 < min_throws) :
				min_throws = least_throws[prev_pos] + 1
				predecessor[pos] = prev_pos
			

		#Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
		#from 4 to 14. So number of dice throws needed to reach 14 = number of 
		#dice throws needed to reach position 4
		ladder_start_pos = ladder[pos]
		if (ladder_start_pos != -1) :
			if (least_throws[ladder_start_pos] < min_throws) :
				min_throws = least_throws[ladder_start_pos]
				predecessor[pos] = ladder_start_pos
			
		least_throws[pos] = min_throws

	return least_throws[MAX_POSITIONS_ON_BOARD], predecessor

Longest increasing subsequence

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 56. Find the longest increasing subsequence in an unsorted array of numbers

Consider the sequence A = {30, 40, 20, 70, 10}. The longest increasing subsequence is {30, 40, 70}. Here we are considering a strictly increasing longest subsequence and so a number can be present only once in the longest increasing subsequence even if it occurs several times in the original sequence. To solve the problem, we use dynamic programming as follows:

1.) We make use of an array called seq_length where seq_length[i] stores the length of the longest increasing subsequence ending at the position i. For instance seq_length[3] stores the length of longest subsequence from 0th to 3rd position, i.e. for the region {30, 40, 20, 70} in the above example. We initialize seq_length array with 1 at each position since each number itself forms a sequence of size 1 by itself.

2. We then compute the seq_length[i] from position 1 onwards using the formula:
seq_length[i] = 1 + max(seq_length[j]) where j < i and A[j] < A[i]

3. Once we have computed sequence lengths for all positions, then the maximum value in the seq_length array gives the length of the longest increasing subsequence. In our example, the maximum value in the seq_length array is 3. So length of longest increasing subsequence is 3.

The time complexity of this approach is O(n2).

C/C++


/*
a: array in which we need to find the longest increasing sequence
n: number of elements in the array. Should be >= 1
lis: the longest increasing sequence is returned in this array
Return value: length of the longest increasing sequence
*/
int find_lis(int a[], int n, int lis[])
{
	/*seq_length stores length of LIS for each position of array a*/
	int *seq_length = (int*) calloc(n, sizeof(int));

	/*prev_ix stores the index of previous element in the LIS sequence*/
	int *prev_ix = (int*) calloc(n, sizeof(int));

	int i, j, lis_length, lis_end;

	/*Each element by itself forms a sequence of length 1*/
	for (i = 0; i < n; ++i)
		seq_length[i] = 1;

	/*Find the LIS for each position in array a*/
	for (i = 1; i < n; ++i) {
		for (j = 0; j < i; ++j) {
			if ( a[j] < a[i] && seq_length[i] < seq_length[j] + 1 ) {
				seq_length[i] = seq_length[j] + 1;
				prev_ix[i] = j;
			}
		}
	}

	/*The longest LIS amongst all positions of array a will be the LIS  
	for the whole array*/
	lis_length = 1;
	lis_end = 0;
	for (i = 1; i < n; ++i) {
		if (lis_length < seq_length[i]) {
			lis_length = seq_length[i];
			lis_end = i;
		}
	}

	/*Use the prev_ix array to reconstruct the LIS for the whole array
	lis_end has the index of the last element in the LIS for whole array*/
	j = lis_end;
	for (i = lis_length - 1; i >= 0; --i) {
		lis[i] = a[j];
		j = prev_ix[j];
	}
	
	free(seq_length);
	free(prev_ix);

	return lis_length;
}

Java


/*a: array in which we need to find the longest increasing sequence.
	Should have atleast 1 element
Return value: array having the longest increasing sequence is returned
*/
public static int[] findLis(int[] a) {
	int n = a.length;

	/*seqLength stores length of LIS for each position of array a*/
	int[] seqLength = new int[n];

	/*prevIx stores the index of previous element in the LIS sequence*/
	int[] prevIx = new int[n];


	/*Each element by itself forms a sequence of length 1*/
	int i, j;
	for (i = 0; i < n; ++i)
		seqLength[i] = 1;

	/*Find the LIS for each position in array a*/
	for (i = 1; i < n; ++i) {
		for (j = 0; j < i; ++j) {
			if ( a[j] < a[i] && seqLength[i] < seqLength[j] + 1 ) {
				seqLength[i] = seqLength[j] + 1;
				prevIx[i] = j;
			}
		}
	}

	/*The longest LIS amongst all positions of array a will be the LIS
	for the whole array*/
	int lisLength = 1;
	int lisEnd = 0;
	for (i = 1; i < n; ++i) {
		if (lisLength < seqLength[i]) {
			lisLength = seqLength[i];
			lisEnd = i;
		}
	}

	
	int[] lis = new int[lisLength]; 

	/*Use the prevIx array to reconstruct the LIS for the whole array
	lisEnd has the index of the last element in the LIS for whole array*/
	j = lisEnd;
	for (i = lisLength - 1; i >= 0; --i) {
		lis[i] = a[j];
		j = prevIx[j];
	}

	return lis;
}

Python


#a: list in which we need to find the longest increasing sequence
#	should have at least 1 element
#Return value: list having the longest increasing sequence is returned
def find_lis(a) :
	n = len(a)

	#seq_length stores length of LIS for each position of list a
	#Each element by itself forms a sequence of length 1
	seq_length = [1 for i in range(0, n)]

	#prev_ix stores the index of previous element in the LIS sequence
	prev_ix = [0] * n

	#Find the LIS for each position in list a
	for  i in range(1, n):
		for  j in range(0, i):
			if ( a[j] < a[i] and seq_length[i] < seq_length[j] + 1 ) :
				seq_length[i] = seq_length[j] + 1
				prev_ix[i] = j
			
	#The longest LIS amongst all positions of list a will be the LIS 
	#for the whole list 
	lis_length = 1
	lis_end = 0
	for  i in range(1, n):
		if (lis_length < seq_length[i]) :
			lis_length = seq_length[i]
			lis_end = i
		
	lis = [0] * lis_length

	#Use the prev_ix list to reconstruct the LIS for the whole list
	#lis_end has the index of the last element in the LIS for whole list
	j = lis_end
	for  i in range(lis_length - 1, -1,-1):
		lis[i] = a[j]
		j = prev_ix[j]
	
	return lis

Coin change problem

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 55. Given a set of coin denominations, find the change for a given amount using the least number of coins. For instance, suppose the coin denominations are 4¢, 5¢ and 7¢, then to get 13¢ using the least number of coins, we need to pick two 4¢ coins and one 5¢ coin.

Let us say that coin denominations are 1¢, 5¢ and 25¢. We can use a greedy approach as follows – Pick the maximum number of coins with the highest denomination and then the maximum number of coins with the next highest denomination and so on. So if we have to pick the change for 58¢, we pick two 25¢, then one 5¢ and finally three 1¢. So we use a total of 6 coins. Greedy approach produces the optimal result for this set of coin denominations. However, given any arbitrary set of coin denominations, the greedy approach will fail for many cases. For instance let the denominations be 1¢, 3¢, 4¢ and 5¢. If we use the greedy approach to get 7¢, we use one 5¢ and two 1¢ thereby requiring three coins. However the optimal solution needs only two coins (one 3¢ and one 4¢).

To solve the problem for any possible coin denominations, we use dynamic programming. We first solve the minimum number of coins needed for the amount of 1¢, then for the amount of 2¢ and so on till we reach the required amount. To compute the minimum number of coins for a higher amount, we make use of the already computed minimum number of coins for lower amounts. The formula used is

If amount = 0, minNumCoins(0) = 0

If amount > 0, minNumCoins(amount) = minimum of { 1 + minNumCoins(amount – denomination)} for all denominations which are less than or equal to the amount

For instance, let the denominations be 1¢, 3¢, 4¢ and 5¢. Using the formula above, minNumCoins[0¢] = 0 coins. The table below shows how the calculation is done for minNumCoins for 1¢, 2¢ and 3¢

So minNumCoins(1¢) = 1, minNumCoins(2¢) = 2 and minNumCoins(3¢) = 1. Similarly we find that minNumCoins(4¢) = 1 and minNumCoins(5¢) = 1. The calculations for 6¢ and 7¢ are shown below

So the minimum number of coins for 7¢ is 2 coins. If the final amount is m and there are n denominations, the time complexity of this approach is O(mn).

C/C++


/*
denom: array having the coin denominations. Should have atleast 1 element
num_denom: number of denominations
final_amount: amount for which change has to be obtained
Return value: Minimum number of coins needed to represent final_amount
*/
int find_min_coins(int denom[], int num_denom, int final_amount) 
{
	/*Array for storing the minimum number of coins for an amount*/
	int *min_num_coins = (int*) malloc( (final_amount+1) * sizeof(int));
	
	/*Array for storing the coin denomination chosen for an amount*/
	int *chosen_denom = (int*) malloc( (final_amount+1) * sizeof(int));
	int i, cur_amt, smaller_amt, result;
		
	min_num_coins[0] = 0;
	for (cur_amt = 1; cur_amt <= final_amount; cur_amt++) {
		min_num_coins[cur_amt] = MAX_INT_VALUE;
		for (i = 0; i < num_denom; ++i) {
			if (denom[i] <= cur_amt) {
		
				smaller_amt = cur_amt - denom[i];

				if (1 + min_num_coins[smaller_amt] < 
						min_num_coins[cur_amt]) {
					min_num_coins[cur_amt] = 
						1 + min_num_coins[smaller_amt];
					chosen_denom[cur_amt] = denom[i];
				}
			}
		}
	}
	
	result = min_num_coins[final_amount];
	printf("Minimum number of coins = %d\n", result);

	/*print the chosen denominations to get the final amount*/
	cur_amt = final_amount;
	while (cur_amt > 0) {
		printf("%d ", chosen_denom[cur_amt]);
		cur_amt = cur_amt - chosen_denom[cur_amt];
	}
	printf(" = %d\n", final_amount);

	free(min_num_coins);
	free(chosen_denom);
	return result;
}

Java


/*denom: array having the coin denominations. Should have atleast 1 element
finalAmount: amount for which change has to be obtained
Return value: Minimum number of coins needed to represent finalAmount
*/
public static int findMinCoins(int[] denom, int finalAmount) {
	/*Array for storing the minimum number of coins for an amount*/
	int[] minNumCoins = new int[finalAmount + 1];

	/*Array for storing the coin denomination chosen for an amount*/
	int[] chosenDenom = new int[finalAmount + 1];

	minNumCoins[0] = 0;
	int curAmount;
	for (curAmount = 1; curAmount <= finalAmount; curAmount++) {
		minNumCoins[curAmount] = MAX_INT_VALUE;
		for (int curDenom : denom) {
			if (curDenom <= curAmount) {
				int smallerAmt = curAmount - curDenom;

				if (1 + minNumCoins[smallerAmt] < 
						minNumCoins[curAmount]) {
					minNumCoins[curAmount] = 
						1 + minNumCoins[smallerAmt];
					chosenDenom[curAmount] = curDenom;
				}
			}
		}
	}

	int result = minNumCoins[finalAmount];
	System.out.println("Minimum number of coins = " + result);

	/*print the chosen denominations to get the final amount*/
	curAmount = finalAmount;
	while (curAmount > 0) {
		System.out.print(chosenDenom[curAmount] + " ");
		curAmount = curAmount - chosenDenom[curAmount];
	}
	System.out.println(" = " + finalAmount);

	return result;
}

Python


#denom: list having the coin denominations. Should have at least 1 element
#final_amount: amount for which change has to be obtained
#Return value: Minimum number of coins needed to represent final_amount
def find_min_coins(denom, final_amount) :
	#List for storing the minimum number of coins for an amount
	min_num_coins = [0] * (final_amount + 1)

	#List for storing the coin denomination chosen for an amount
	chosen_denom = [0] * (final_amount + 1)
	
	min_num_coins[0] = 0
	for  cur_amt in range(1, final_amount+1):
		min_num_coins[cur_amt] = MAX_INT_VALUE
		for  cur_denom in denom:
			if (cur_denom <= cur_amt) :
	
				smaller_amt = cur_amt - cur_denom

				if (1 + min_num_coins[smaller_amt] < 
						min_num_coins[cur_amt]) :
					min_num_coins[cur_amt] = (1 + 
						min_num_coins[smaller_amt])
					chosen_denom[cur_amt] = cur_denom
	

	result = min_num_coins[final_amount]
	print('Minimum number of coins = {}'.format(result) )

	#print the chosen denominations to get the amount
	cur_amt = final_amount
	while (cur_amt > 0) :
		print('{} '.format(chosen_denom[cur_amt]) , end='')
		cur_amt = cur_amt - chosen_denom[cur_amt]
	print(' = {}'.format(final_amount) )

	return result

Maximum Continuous Sum

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 54. Find the maximum continuous sum in an array

An array can have positive and negative elements in it. We have to find a subset of contiguous elements in the array whose sum is the maximum. Let the maximum continuous sum be represented as MCS

In the brute force approach, we pick an element and then go on adding its right neighbors one by one to find the maximum contiguous sum starting at that element. We then repeat the process for all elements in the array to find the MCS across all elements. The time complexity of the brute force approach is O(n2).

However it is possible to find the MCS in O(n) time using kadane’s algorithm. This algorithm works for all cases (including the case where all the elements are negative). We maintain the variable max_local which will store the sum of the neighboring elements in the current window. The algorithm is described below:

1. Choose the first element and initialize max_local to the first element.

2. Traverse through the remaining elements. If the result of adding max_local to the current element is greater than current element, then add the current element to max_local and keep continuing the window. If however the result of adding max_local to the current element is less than the current element, then start a fresh window that starts at the current element and initialize max_local to the current element.

3. The maximum value of max_local across all elements will be the MCS of the array.

Let A = {4, -9, 5, 6 , 1} . max_local is initialized to 4. The remaining calculations are shown in the table below

C/C++


/* 
a: the array of numbers for which the MCS should be found,
length: number of elements. Should >= 1
mcs_start_pos: the starting array index of the MCS is returned here
mcs_end_pos: the ending array index of the MCS is returned here 
Return value: Maximum continous sum of the elements 
*/
int kadane_mcs(int a[], int length, int *mcs_start_pos, int *mcs_end_pos) {
	int i, max_local, max_global;
	int cur_start_pos;

	*mcs_start_pos = *mcs_end_pos = 0;
	cur_start_pos = 0; /*store the start position of the current window*/

	max_local = max_global = a[0];

	/*Traverse from the second element onwards*/
	for (i = 1; i < length; ++i) {
		max_local = max(a[i], a[i] + max_local);
		if (max_local == a[i])
			cur_start_pos = i; /*start a new window here*/

		/*Find the global maximum*/
		if (max_local > max_global) {
			max_global = max_local;
			*mcs_start_pos = cur_start_pos;
			*mcs_end_pos = i;
		}
	}

	return max_global;
}

Java


/* a: array of numbers for which MCS should be found. 
	At least 1 element should be present
mcsStartPos: the starting array index of the MCS is returned here
mcsEndPos: the ending array index of the MCS is returned here 
Return value: Maximum continous sum of the elements 
*/
public static int kadaneMcs(int[] a, Int mcsStartPos, Int mcsEndPos) {
	int length = a.length;
	int curStartPos = 0; /*store the start position of the current window*/
	int maxLocal = a[0], maxGlobal = a[0];
	mcsStartPos.value = mcsEndPos.value = 0;

	/*Traverse from the second element onwards*/
	for (int i = 1; i < length; ++i) {
		maxLocal = Math.max(a[i], a[i] + maxLocal);
		if (maxLocal == a[i])
			curStartPos = i;/*start a new window here*/

		/*Find the global maximum*/
		if (maxLocal > maxGlobal) {
			maxGlobal = maxLocal;
			mcsStartPos.value = curStartPos;
			mcsEndPos.value = i;
		}
	}

	return maxGlobal;
}

Python


#a: list of numbers for which MCS should be found. size of a >= 1
#Return value:  1. Maximum continuous sum of the elements , 
#		2. the starting list index of the MCS 
#		3. the ending list index of the MCS 
def kadane_mcs(a) :
	length = len(a)

	mcs_start_pos = mcs_end_pos = 0
	cur_start_pos = 0 #store the start position of the current window

	max_local = max_global = a[0]

	#Traverse from the second element onwards
	for  i in range(1, length):
		max_local = max(a[i], a[i] + max_local)
		if (max_local == a[i]):
			cur_start_pos = i #start a new window here

		#Find the global maximum
		if (max_local > max_global) :
			max_global = max_local
			mcs_start_pos = cur_start_pos
			mcs_end_pos = i

	return max_global, mcs_start_pos, mcs_end_pos