Category: fine_tune_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 42: Trapping Rain Water
link A bar can hold some water atop if there are left and right supports for it. So, we can compute water on top of each bar and sum up. Time: , space: . We could pre-compute left and right support for each index. Time: , space: . With two pointers moving from two ends,…
-
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 79: Word Search
link We try finding the word one character at a time starting from every cell avoiding already visited cells. Say . Time: , space: . Follow up: Could you use search pruning to make your solution faster with a larger board? We start searching with a word character that appears the least in the board, in that…
unreasonably effective 