Print all k–colorable configurations of a graph (Vertex coloring of a graph)
Given a graph, find if it is k–colorable or not and print all possible configurations of assignment of colors to its vertices.
Tag: Medium
Find the total number of unique paths in a maze from source to destination
Find the total number of unique paths that the robot can take in a given maze to reach a given destination from a given source.
Find the path from source to destination in a matrix that satisfies given constraints
Given an N × N matrix of positive integers, find a path from the first cell of the matrix to its last cell.
Find the longest possible route in a matrix
Given a rectangular path in the form of a binary matrix, find the length of the longest possible route from source to destination by moving to only non-zero adjacent positions.
Find the shortest path in a maze
Given a maze in the form of the binary rectangular matrix, find the shortest path’s length in a maze from a given source to a given destination.
Find common elements present in all rows of a matrix
Given an M × N matrix, find the common elements present in all rows of the matrix. The solution should traverse the matrix once and print the common elements in O(M × N) time.
Find minimum product among all combinations of triplets in an array
Given an integer array, find the minimum product among all combinations of triplets in the array.
Generate the power set of a given set
Given a set S, generate all subsets of it, i.e., find the power set of set S. A power set of any set S is the set of all subsets of S, including the empty set and S itself.
Find duplicate parenthesis in an expression
Given a balanced expression that can contain opening and closing parenthesis, check if the expression contains any duplicate parenthesis or not.
Find k’th smallest element in an array
Given an array and a positive integer k, find k’th smallest element in the array… We can easily solve this problem in O(n.log(k)) time by using a max-heap.
Sort a k-sorted array
Given a k–sorted array that is almost sorted such that each of the n elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.
Find k’th largest element in an array
Given an array and positive integer k, find k’th largest element in the array.