Lucky Numbers in a Matrix

Lucky Numbers in a Matrix

What is this problem about?

The Lucky Numbers in a Matrix problem provides an m x n matrix of distinct numbers. A "lucky number" is defined as an element that is simultaneously the minimum element in its row and the maximum element in its column. Your task is to find and return all lucky numbers present in the matrix.

Why is this asked in interviews?

This is a straightforward Matrix traversal and Precomputation problem. Interviewers use it as an early-stage screening question to test basic 2D array manipulation. It evaluates whether a candidate can avoid redundant inner loops by storing intermediate states, showing a solid grasp of basic time-space trade-offs.

Algorithmic pattern used

This problem relies on Array Traversal and Precomputation (State Storage). To avoid checking the entire row and column for every single cell (which would be $O(M \times N \times (M + N))$), you should precompute the minimum of each row and store it in an array of size M, and compute the maximum of each column and store it in an array of size N. Then, you do a final pass through the matrix: if matrix[i][j] == row_mins[i] AND matrix[i][j] == col_maxes[j], it's a lucky number!

Example explanation

Matrix:

3   7  8
9  11 13
15 16 17

1. Find Row Minimums:
   • Row 0: min(3, 7, 8) = 3
   • Row 1: min(9, 11, 13) = 9
   • Row 2: min(15, 16, 17) = 15
2. Find Column Maximums:
   • Col 0: max(3, 9, 15) = 15
   • Col 1: max(7, 11, 16) = 16
   • Col 2: max(8, 13, 17) = 17
3. Check for overlap: Is there any value that is both its row's min and its col's max?
   • The number 15 is the minimum in Row 2, and it is the maximum in Col 0!
   • 15 is a lucky number.

Common mistakes candidates make

A frequent mistake is not isolating the two conditions. Candidates will find the minimum of a row, and then immediately run a while loop to verify if it's the maximum of its column. While this uses $O(1)$ extra space, it can be slightly less efficient. The precomputation method is generally preferred as it is strictly $O(M \times N)$ and highly readable. Another error is assuming there can be multiple lucky numbers in the same row or column, which is impossible since all matrix values are distinct.

Interview preparation tip

For the Lucky Numbers in a Matrix coding problem, demonstrating the precomputation strategy proves you understand optimization. Whenever a matrix problem asks you to validate cells based on whole-row and whole-column properties, always create 1D arrays to cache those row/col states first to ensure your solution remains strictly linear with respect to the total number of cells.