Category: foundational_interview
-
LeetCode 1380: Lucky Numbers in a Matrix
link A lucky number is both a row min and a column max. We find the row mins and column maxes in one pass and return their overlap as the lucky numbers. Time: , space: . O(1) extra space: reuse matrix If modifying the matrix is feasible, we could use the first row to save…
-
LeetCode 1791: Find Center of Star Graph
link In-degree All edges of a star graph involves the center. Therefore, the center’s indegree = len(edges). Time: , space: . Overlapping vertex Any pair of edges must include the center. So, the center is the overlap between first two edges. Time: , space: . Or,
-
LeetCode 997: Find the Town Judge
link A town judge lacks even self-trust. So, in the trust graph, the town judge looks like a sink: in-degree = n-1 and out-degree = 0. And, there must be exactly one such sink vertex. Time: , space: . More concisely, we can define trustworthiness of a person as (indegree-outdegree). Then, a person with trustworthiness…
-
LeetCode 332: Reconstruct Itinerary
link Backtrack A valid itinerary uses each ticket exactly once and is lexicographically sorted. So, we build a directed graph where an edge is a ticket. Starting with “JFK” we backtrack to find a path that consumes all tickets. Each hop of the path consumes one available ticket. We use sorted edge-lists so that possible…
-
LeetCode 815: Bus Routes
link Change of routes is what we care about, bus-stops within a route can be abstracted away. We thus have an undirected graph where vertices are route indices and there is an edge if the two routes share a bus-stop. In this route graph, we want to find the shortest distance between two routes: one…
-
LeetCode 261: Graph Valid Tree
link A tree has barely enough edges to remain connected. So, with nodes there must be edges and all nodes must belong to a single connected component. We use DFS for the connected component part. Time: , space:
-
LeetCode 133: Clone Graph
link We can piggyback on DFS to clone the graph. We copy a node when we explore it. Note, if a shallow reference of exists in the map, we should grab that reference and deepen it. Otherwise, an earlier node storing ‘s reference in its neighbors list, will not be able to access the updated,…
-
LeetCode 2077: Paths in Maze That Lead to Same Room
link Backtrack A 3-cycle like below consists of a 3-room path () and an edge from the last room to the first room (). So, we consider each room as the head of a possible 3-cycle, generate 3-length path and check if there is an edge from last room to first. If largest number of…
-
LeetCode 743: Network Delay Time
link We use Dijkstra’s shortest path distance algorithm to find delays to all nodes from source. Max distance from source is the minimum time it would take for the signal to reach all nodes. heapq does not allow updating key, so we insert new entries like (d_v, v) whenever there is a better distance and…
-
LeetCode 20: Valid Parentheses
link Stack We match and pop matching pairs using a stack. If s is valid, in the end, the stack must be empty. Time: , space: same. Two pointers Like this problem, if we are allowed to modify the string s in-place, we need constant extra space. Time: , space: .
unreasonably effective 