-
LeetCode 1970: Last Day Where You Can Still Cross
link The grid can be considered as an undirected graph where land cells are the vertices and an edge exists between two vertices if the land cells are neighbors. DFS In the grid graph, for each day, we can check if there is a path from any of the sources (land cells on first row)…
-
LeetCode 128: Longest Consecutive Sequence
link Union-Find We can consider an undirected graph where the distinct numbers are the vertices and an edge between two distinct vertices u and v exists if u = v-1 or u = v+1. The largest connected component of this number graph will have the longest path having consecutive numbers. Using Union-Find we can determine…
-
LeetCode 947: Most Stones Removed with Same Row or Column
link The relation “shares-row-or-column-with” is an equivalence relation on the set of stones. In other words, there is an undirected graph where stones are the vertices and an edge between two stones exist if they share a row or a column. In this stone graph, we can remove all but one stones from each connected…
-
LeetCode 200: Number of Islands
link The grid can be considered as an undirected graph where cells are the vertices and an edge (u, v) means both cells have “1” in them and they are neighbor of each other. DFS Each island is a connected component (cc) in the grid graph. So, we can count the cc’s in one DFS.…
-
LeetCode 684: Redundant Connection
link Union-find With nodes we start building the tree. If we find two ends of an edge already connected, that edge is redundant. Operation Time Space UnionFind(n) is_connected connect
-
Union-Find
Say we have an equivalence relation on a set . So, partitions into equivalence classes which are disjoint subsets of . Now, given a pair where , we want to answer: Do and belong to the same equivalence class? As an example, we need to answer this question to build the minimum spanning tree of…
-
LeetCode 3016: Minimum Number of Pushes to Type Word II
link The more frequent a character is, the earlier in the mapping it should appear. There are only eight keys that can have character mapping. So, we keep assigning groups of eight characters to the eight keys in decreasing order of frequency. Say there are characters that need mapping with of them distinct. Time: ,…
-
LeetCode 383: Ransom Note
link We should find all characters of the ransomNote in the magazine. So, we use two passes: (1) For the magazine, build {char -> count} map (2) For each char in ransomNote, we try finding it in magazine. Say magazine has chars and ransomNote has chars. Time: , space: .
-
LeetCode 1010: Pairs of Songs With Total Durations Divisible by 60
link If , then . So, we keep track how many times we have seen . While considering , if we have seen before say times, then we have pairs with as the second element. Time: . Since there are only different remainders , space: .
-
LeetCode 1366: Rank Teams by Votes
link Say there are positions and represents the vote counts for at different positions. Like, got votes for position , got votes for position , etc. We can consider an extended pair: and sort these pairs by reverse-lexicographic of the first element and lexicographic of the second element. To have custom comparison while sorting we…
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 