Rectangular Matrix: Rotate, Transpose, and Search in a 2D Matrix Efficiently

Question

## Problem

Given an `m x n` matrix of integers sorted in ascending order both row-wise and column-wise, implement three operations: (1) search for a target in O(m+n), (2) rotate the matrix 90 degrees clockwise in-place (for square matrices), and (3) return all elements in spiral order.

```python
def search_matrix(matrix: list[list[int]], target: int) -> tuple[int, int] | None:
    # Start top-right; move left if too big, down if too small
    pass

def rotate_90(matrix: list[list[int]]) -> None:
    # In-place for square matrix
    pass

def spiral_order(matrix: list[list[int]]) -> list[int]:
    pass
```

**Example (search):**
```
matrix = [[1,4,7],[2,5,8],[3,6,9]], target=5
Output: (1, 1)

spiral_order([[1,2,3],[4,5,6],[7,8,9]])
-> [1,2,3,6,9,8,7,4,5]
```

## Follow-ups

1. Why does starting from the top-right corner give O(m+n) for search?
2. For in-place 90-degree rotation: what is the two-step approach (transpose then reverse)?
3. Extend spiral_order to work on non-square (rectangular) matrices.
4. How would you find the kth smallest element in a row-and-column sorted matrix?

Rectangular Matrix: Rotate, Transpose, and Search in a 2D Matrix Efficiently

Question Details

Full Details

Topics

More from Citadel