Given a 2D city blocks and a list of post offices coordinates. Calculate the minimum distance each block to the nearest post officies. BFS Initialize all cells to -1, meaning the distances all need to be determined. The core idea is to run BFS from each post office concurrently. This ensures that each cell will […]
Given a graph, determine whether the graph is bipartite. Bipartite is defined as a graph where nodes can be split into two halves and every edge connects between the two sets. DFS DFS traverse the graph and nodes must alternative between two sets. This file contains bidirectional Unicode text that may be interpreted or compiled […]
Given a list of bus routes. Each route is represented as a list of bus stops this route goes. Find the least amount of bus routes to get from starting stop and ending stop. BFS (ETL on Large Input) Build a map from each stop to all other stops it can reaches on the same […]
Given number of nodes and a list of undirected edges in a graph. Determine whether the graph is a valid tree. A valid tree is a tree that is 1) connected and 2) does not have cycles. How to work with undirected graph? Store graph in adjacent list. i.e. Map<Integer, Set> m; Store edges in […]
Given a matrix, where INF represents an empty room, -1 represents a wall/obstacle, and 0 represents a gate. Update the matrix and update the empty room to be the shortest distance to a nearby gate. Optimal BFS Start BFS from all the gate at the same time. If a room gets updated first time, it […]
Given a graph, return a deep clone of it. BFS Store a map from origin node to clone node in a hash map. Traverse the original graph using BFS. i.e. using a queue. Each time remove a node from queue to process, meaning create its clone in the map (if not exist), and clone all […]
Word Ladder I Given a start word and an end word, and a dictionary of words. Find the shortest path from start word to end word, where end word and words in the path must be in the dictionary. (start word does not have to). Two Ended BFS Run BFS starts from two ends using […]
Given a binary tree, traverse the tree and return values in zigzag level order. BFS Traverse the tree using BFS, using a queue. (Try not to use the two level alternating approach). Also keep track of current level, and if level % 2 != 0, we add items in reverse order. Time: O(n) Space: O(n) […]
Given a string with parentheses and letters. Remove the minimum number of parentheses so the string becomes valid. To check if a string is valid or not, we can maintain a counter. Walk through the string, if find a letter, move on. If find a left paren, increase the counter by 1, if find a […]
Think about DFS and BFS when dealing with paths in matrix. Maze I Given a maze represented as a matrix, where 0 is empty and 1 is a wall. Boarders are walls too. A ball starts from a starting position, and rolling, once the ball hits a wall, it will stop, and choose next direction […]
bilbo3000.wordpress.com 