unreasonably effective

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:…

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…

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:…

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: .

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…

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…

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,…

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…