Cycle in a directed graph

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

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

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

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

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

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

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



Activity Selection Problem

Question 53. Given the start time and end time of N activities, find the maximum number of activities that can be performed (Activity Selection problem)


We can find the maximum number of activities using the greedy approach as indicated below

1. Sort the activities based on their end times so that an activity with a smaller end time is placed before an activity with a larger end time.

2. Traverse through the sorted list and choose the activities that can be completed without any conflicts (the start and end time of a chosen activity should not overlap with the start and end time of another chosen activity)

C/C++


/*Function for comparing two elements. This function used while sorting*/
int cmp_function(const void *p1, const void *p2)
{
	struct activity *x = (struct activity *)p1;
	struct activity *y = (struct activity *)p2;

	if (x->end_time < y->end_time)
		return -1;
	else if (x->end_time == y->end_time)
		return 0;
	else 
		return 1;
}


void sort(struct activity a[], int length)
{
	qsort(a, length, sizeof(struct activity), cmp_function);
}


/*
a: array of activities, where each activity has a start time and end time
num_activities: number of elements in the array. Should be >= 1
selected: the indexes of the selected activities 
Return value: Maximum number of activities that can be performed
*/
int activity_selection(struct activity a[],  int num_activities, int selected[])
{
	int i, count, cur_time; 

	/*Sort the activities in non-decreasing order of their end time*/
	sort(a, num_activities);

	/*Keep a track of the current time as we process the activities*/
	cur_time = 0;
	count = 0;
	for (i = 0; i < num_activities; ++i) {
		/*Pick the activity whose start time is on or after current time*/
		if (a[i].start_time >= cur_time) {
			selected[count] = i;
			count++;

			/*Update the current time to the end time of the activity*/
			cur_time = a[i].end_time;
		}
	}

	return count;
}



Java


/*This class is used for comparing two elements during sorting*/
class ActivityComparator implements Comparator<Activity> {
	public int compare(Activity a, Activity b)	{

		if (a.endTime > b.endTime)
			return 1;
		else if (a.endTime == b.endTime)
			return 0;
		else
			return -1;
	}
}


/*
a: array of activities, where each activity has a start time and end time
Returns: ArrayList having indexes of the selected activities 
*/
public static ArrayList<Integer> activitySelection(Activity[] a) {
	ArrayList<Integer> selected = new ArrayList<Integer>(); 

	/*Sort the activities in non-decreasing order of their end time*/
	Arrays.sort(a, new ActivityComparator());

	/*Keep a track of the current time as we process the activities*/
	int curTime = 0;
	int i = 0;
	for (Activity curActivity : a) {
		/*Pick the activity whose start time is on or after current time*/
		if (curActivity.startTime >= curTime) {
			selected.add(i);

			/*Update the current time to the end time of the activity*/
			curTime = curActivity.endTime;
		}
		++i;
	}

	return selected;
}



Python


#a: list of activities, where each activity has a start time and end time
#Return value: list having the index of the selected activities 
def activity_selection(a) :
	#Sort the activities in non-decreasing order of their end time
	a.sort(key = lambda x: x.end_time)

	selected = [] 

	#Keep a track of the current time as we process the activities
	cur_time = 0

	for  i, cur_activity in enumerate(a):
		#Pick the activity whose start time is on or after current time
		if (cur_activity.start_time >= cur_time) :
			selected.append(i)

			#Update the current time to the end time of the activity
			cur_time = cur_activity.end_time

	return selected



Maximum profit given stock prices

Question 52. Given a set of stock prices over a period of time, find the maximum profit possible by buying and selling the stocks. For instance, if the stock prices are 100, 90, 200, 20, 70, 150, 10 and 40, then the maximum profit = 150 – 20 = 130


If we use a brute force approach, then we will compare every pair of numbers to find the maximum profit possible. This requires O(n2) operations. However using the greedy approach we can solve the problem in O(n). The main idea of the greedy approach is that it is sufficient to maintain the minimum stock price that we have encountered so far as we traverse the stock prices.

The procedure is as follows: as we traverse the stock price list, subtract the minimum stock price seen so far from the current stock price to figure out the profit. If the profit is greater than the maximum profit so far, then update the maximum profit.

The working of the algorithm on the stock prices {100, 90, 200, 20, 70, 150, 10, 40} is given below. The minimum stock price is initialized to the first element 100. The max profit is initialized to 0. We start from the second stock price onwards.

C/C++


/*
stock_price: array of stock price values
n: number of elements in the array
Return value: maximum profit possible
*/
int find_max_profit(int stock_price[], int n)
{
	int i, min_stock_price, cur_profit, max_profit;

	max_profit = 0;
	if (n <= 1)
		return max_profit;

	min_stock_price = stock_price[0];

	for (i = 1; i < n; ++i) {
		
		cur_profit = stock_price[i] - min_stock_price;

		if (cur_profit > max_profit)
			max_profit = cur_profit;

		if (stock_price[i] < min_stock_price)
			min_stock_price = stock_price[i];
	}

	return max_profit;
}



Java


/*
stockPrice: array of stock price values
Return value: maximum profit possible
*/
public static int findMaxProfit(int[] stockPrice) {
	int n = stockPrice.length;

	int maxProfit = 0;
	if (n <= 1)
		return maxProfit;

	int minStockPrice = stockPrice[0];

	for (int i = 1; i < n; ++i) {
	
		int curProfit = stockPrice[i] - minStockPrice;

		if (curProfit > maxProfit)
			maxProfit = curProfit;

		if (stockPrice[i] < minStockPrice)
			minStockPrice = stockPrice[i];
	}

	return maxProfit;
}



Python


#stock_price: list of stock price values
#Return value: maximum profit possible
def find_max_profit(stock_price) :
	n = len(stock_price)

	max_profit = 0
	if (n <= 1):
		return max_profit

	min_stock_price = stock_price[0]

	for  i in range(1, n):
		cur_profit = stock_price[i] - min_stock_price

		if (cur_profit > max_profit):
			max_profit = cur_profit

		if (stock_price[i] < min_stock_price):
			min_stock_price = stock_price[i]
	
	return max_profit