-
LeetCode 1146. Snapshot Array
link We keep the below three pieces of information: On get(), we may need to search through earlier snapshots to get the value at an index that has not changed for a while. Say snap‘s have been called. Operation Time Space __init__ set snap get
-
LeetCode 399: Evaluate Division
link All equations and valid queries are divisions. So, we can we can model a valid query, as a weighted path between and . We build a graph of variables where the edge has weight . We also get the edge with weight . As we build the adjacency list of the graph, we also…
-
LeetCode 218: The Skyline Problem
link For skyline, building roofs are important. Roofs are intervals at some height. If we jump from the end of a roof, we fall to the next higher roof or we fall to the ground. We can find the skyline points from the groups of heights at different locations — from each group, just take…
-
LeetCode 8: String to Integer (atoi)
link Python We use lstrip() to get rid of spaces from the beginning. In Python, the int does not overflow or underflow. So, if num is too big or too small, we just cap the magnitude at the 32-bit positive’s max () or negative’s max (). Time: , space: . Without lstrip, space would have…
-
LeetCode 3. Longest Substring Without Repeating Characters
link We use sliding window. Until we find a repeated character in the current window, we keep expanding. Say our current window is s[begin : end] and we see s[end] at index i, where i >= begin. Then our new window is: s[i+1 : end+1] — once again, the window has all unique characters. Time:…
-
LeetCode 1. Two Sum
link If we have seen target-nums[j] at index i, then [i, j] is a pair. Time: , space: .
-
LeetCode 924: Minimize Malware Spread
link Simulate with BFS For each node in the initial, with one BFS, we can simulate what the spread would have been if we removed that node. We want to find the node which if removed, would cause minimum spread. If there is a tie, we break in favor of smaller node id. Say len(initial)…
-
LeetCode 721: Accounts Merge
link UnionFind We can build an email graph where vertices are the unique emails and an edge between two vertices exists if the emails belong to the same person. We can use UnionFind to keep track of the connected components (cc) of this email graph. In the end, we emit the (sorted) cc’s along with…
-
LeetCode 959: Regions Cut By Slashes
link We need to count the connected components in the undirected grid graph. Since putting “/” in a cell divides the cell into two not-connected regions: [ / ], we shall consider each cell having left and right halves. We treat ” ” like “/”, only difference is for ” ” the two halves of…
-
LeetCode 1971: Find if Path Exists in Graph
There is a path between source and destination if and only if the two vertices belong to the same connected component (cc). With Union-Find, we start with connected components — one per vertex. As we union the two ends of edges, the number of connected components goes down. At the end, we check if source…
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 