Category: foundational_interview
-
LeetCode 994: Rotting Oranges
link We let rotting wavefronts emanate from all rotten oranges in each iteration of BFS. As soon as fresh orange count drops to zero we are done. Time: , space: .
-
LeetCode 1029: Two City Scheduling
link Brute force Try flying each person to city A and city B and take the minimum cost. Time: , space: . Greedy For a cost pair , when we decide to fly a person to city A, we are also deciding to not fly that person to city B. We have to optimize both…
-
LeetCode 22: Generate Parentheses
link Valid parentheses have two criteria: Recursive Time: , space: .
-
LeetCode 17: Letter Combinations of a Phone Number
link Recursive Letter combinations of “23” is the cartesian product of corresponding letter sets: {“a”, “b”, “c”} and {“d”, “e”, “f”}. Note, there can be at most four different letters for a digit. Time: , space: . Iterative For each possible letter for a new digit, we can append it to each of the earlier…
-
LeetCode 46: Permutations
link Recursive Time: , space: . Iterative For a new element , for each earlier permutations, we can insert in different positions to get more permutations. Time: , space: .
-
LeetCode 78: Subsets
link Take or skip: Recursion We skip or take each element. Time: , space: . Take or skip: Iterative Say we have subsets with (n-1) elements. For the n-th element, we can take it or we can skip it. Skipping n-th element is same as keeping the subsets with only (n-1) elements or the subsets…
-
LeetCode 2824: Count Pairs Whose Sum is Less than Target
Sort and two pointers In sorted order, if nums[i] + nums[j] < target, then with nums[i] as the first element there are (j-i) second elements that can make a valid pair. Time: , space: .
-
LeetCode 1337: The K Weakest Rows in a Matrix
link We want to find k-smallest strength row, so we use a size-limited max heap with count of ones as the primary key and row-index as the secondary key. Since in a row 0’s and 1’s are nicely separated, we can use binary search to find the index of the leftmost 0 which is the…
-
LeetCode 1802: Maximum Value at a Given Index in a Bounded Array
link Since all numbers in nums must be positive, bounded_sum(nums) must be at least n, so maxSum >= n. As we increase nums[index] the predicate bounded_sum(nums) > maxSum evaluates like: False, False, False, True, True, … In other words, once the predicate becomes true, it remains True. We want the value of nums[index] for the…
-
LeetCode 540: Single Element in a Sorted Array
link Bitwise If we xor all elements in the array, the single element remains. Time: , space: . Binary search Since nums is sorted, all repeated numbers appear consecutively. All numbers except one has duplicates so, len(nums) is odd. Also, removing a pair of (consecutive) duplicate numbers breaks nums into two halves: one half has…
unreasonably effective 