-
LeetCode 953: Verifying an Alien Dictionary
link Lexicographic order between two words can be thought of as comparing two same-length numbers with the shorter one padded with ‘s on the right. Since for three numbers , if and , then ; lexicographic order is transitive. Validating pairs of consecutive words is thus sufficient. With words, alphabet size , and the biggest…
-
LeetCode 269: Alien Dictionary
link We want to build a directed graph where vertex set is the alien alphabet and an edge represents: . A cycle in the graph signals and — a contradiction; so input is invalid. Otherwise, we emit the vertices in topological order. Single word Say words = [“confide”]. With a single word we do not…
-
Availability
Within a time period of units, if a system is down for units, then its availability for the time period is defined as . It usually is expressed as percentage. In other words, . We note that is a linear function of down time with a slope of . Therefore, if down time increases, availability…
-
Graph Traversal
Say a graph’s vertex set is and edge set is . We want to traverse the graph efficiently, therefore, we want to visit each vertex and each edge exactly once. An edge has two ends: a from and a to. In the edge we can consider as from and as to. The basic traversal strategy…
-
LeetCode 645: Set Mismatch
link Cyclic sort Cyclic sort to match nums with the reference sequence . The first mismatch is the answer. Time: , space: .
-
LeetCode 41: First Missing Positive
link Cyclic sort If nums only had positive numbers, we could cyclic sort it to match the sequence of positive integers and the first mismatch would have been the first missing positive number. To reduce the original problem to the above, simpler, all-positive case, we first sort around pivot 1. From the pivot index onwards,…
-
LeetCode 268: Missing Number
link Math Difference between expected sum and actual sum is the missing number. Time: , space: . Cyclic sort If we think about how nums would look like once sorted, there are two options: So, if we put each nums[i] in its expected index, there will be zero (first option) or one (second option) index…
-
LeetCode 70: Climbing Stairs
link Dynamic Programming Subproblem Let be the number of ways to climb stairs. Then: Time: , space: .
-
LeetCode 2539: Count the Number of Good Subsequences
link Brute force Checking all substrings will take time . Observations We can use divide-and-conquer in two ways to simplify the counting problem: Count of good subsequences with instances of each char-type is thus product . We add to the count for each char type to accommodate leaving that char-type altogether from the good subsequence.…
-
LeetCode 91: Decode Ways
link Decodings can be thought of as paths in a binary tree. So, we need to count the number of paths. Note, we do not need to keep track of already counted decodings. In the example above, the first decision at the root produced two branches: (1) starts with “2” having symbol “B” (2) starts…
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 