Shady Fanous

Problem Statement Given a graph with N nodes and E edges, check whether the graph is bipartite or not. A bipartite graph is a graph where for each edge (u, v), either u belongs to U and v belong to V, or u belongs to V or v belongs to... [Read More]

Problem Statement Given a graph, color similarly-colored nodes/areas with the same color. See this Wikipedia article for an illustration. General Idea | \(O(V+E) \space or \space O(row+col)\) The general idea is to select a target/starting node, a target color and a replacement color. We then recursively loop over the starting... [Read More]

Problem Statement “Given an undirected graph G with edge weights, output all edges that are the heaviest edge in some cycle of G” Problem Link Thought Process Well, it’s a minimum spanning tree problem. Either Kruskal’s or Prim’s algorithm should work fine here (Kruskal’s is used below). Instead of printing... [Read More]

Problem Statement Given a graph with V vertices and E edges, find the number of connected components. Note: This is not the same as finding the number of strongly connected components General Idea | \(O(V+E)\) The general idea is to simply start traversing from any vertex (for simplicity, we start... [Read More]

Problem Statement Say we want to implement a circular array. Usually, circular arrays are implemented using the % operator. Now, let A be an array of length 4. Say we’re at A[3] and we want to circle back to A[0]. Well, that’s easy. Add 1 to our current index, 3,... [Read More]

Problem Statement Given a 2D array of positive and negative integers, find the sub-rectangle with the largest sum. General Idea Create another 2D array A, where A[i][j] is the sum of the sub-rectangle ranging from (0, 0) to (i, j) - \(O(n^2)\) Calculate the sum of each sub-rectangle - \(O(n^4)\)... [Read More]