Category: foundational_interview
-
LeetCode 2022: Convert 1D Array Into 2D Array
link If we cannot fit all elements of original in the grid, we return empty. Otherwise, say we have already copied elements from the original. Then the next element would be at index of the original. If we translate into grid coordinates, . In other words, original[k] corresponds to grid[count-copied-rows * row-width][count-copied-columns]. We can copy…
-
LeetCode 463: Island Perimeter
link A 1-cell has four sides and it can contribute at most 4 to the perimeter. If a side is shared with another 1-cell, that side does not contribute to perimeter. So, for each 1 cell in the grid, we count how many of its four sides are shared and then add (4 – shared_count)…
-
LeetCode 302: Smallest Rectangle Enclosing Black Pixels
link The bounding box’s width is determined by the leftmost and the rightmost occurrences of “1” across all rows. Similarly, the height is determined by the topmost and the bottom-most rows where ones appear. Linear search per row In each row we can linearly search for the leftmost and the rightmost columns having ones. Time:…
-
LeetCode 2814: Minimum Time Takes to Reach Destination Without Drowning
link The complexity comes from flood cells, which grow over time. Since Manhattan distance from a flood cell is the minimum time it would take for a cell to get flooded, it is not difficult to find out which of my four neighboring cells will get flooded next. However, presence of stones, source, and destination…
-
LeetCode 1351: Count Negative Numbers in a Sorted Matrix
link Per row binary search Since rows are sorted, for each row we find the would-be insert index of using binary-search which gives the negative count for that row. Time: , space: . Trace negative boundary Since the grid is sorted both row-wise and column-wise, at each coordinate we have two directions with “opposite” gradients:…
-
LeetCode 867: Transpose Matrix
link For a source matrix, we would create a transposed matrix. We copy each row of the source matrix into a column of transposed. Time: , space: .
-
LeetCode 1706: Where Will the Ball Fall
link The rules are local involving just two cells: current cell and the cell to its left or to its right. Moves can happen in three directions: down, left, and right. For an entry column, we start with row = -1, so first down move is valid. In the beginning of each iteration we maintain…
-
LeetCode 54: Spiral Matrix
link For a square we can define the spiral order in terms of concentric disks. But for rectangles it can be hard. Instead, we can find a robust, local definition: To be able to mark a visited cell, we can assign None. Time: , space: . If updating the matrix is not feasible, we can…
-
LeetCode 48: Rotate Image
link Rotation of the matrix is composed of smaller, independent rotations each of which takes constant extra space. The matrix can be thought of as a collection of concentric disks. Within each disk there are 4-element loops. We can rotate each loop with just one extra variable. The four transitions within a loop involve: row_min,…
-
LeetCode 73: Set Matrix Zeroes
link We cannot update the matrix in one pass. Because, the original zeroes will conflict with the filled-in zeroes. We need at least two passes. Time cannot be better than . We shall optimize for space. O(m+n) space In the first pass, for each encountered zero, we shall record its row and its column in…
unreasonably effective 