Lucky Numbers in a Matrix - Solution & Explanation

Problem Overview: You receive an m x n matrix and must return all lucky numbers. A lucky number is an element that is the minimum in its row and the maximum in its column. The task is to scan the matrix efficiently and identify elements that satisfy both conditions.

Approach 1: Iterative Row Minimum Check (O(m * (n + m)) time, O(1) space)

Iterate through each row and find the minimum value along with its column index. Once you have the row minimum, scan that column to verify whether the same value is also the maximum element in that column. The logic is straightforward: a lucky number must survive both checks. This approach uses simple iteration over the array representation of the matrix and avoids extra memory. Time complexity becomes O(m * (n + m)) because each row scan costs O(n) and the column validation costs O(m). Space complexity remains O(1).

Approach 2: Mathematical Intersection (O(m * n) time, O(m + n) space)

A lucky number must belong to two sets: the set of all row minimums and the set of all column maximums. First compute an array of row minimum values and another array of column maximum values by scanning the matrix. Then iterate through the matrix again and check if matrix[i][j] == rowMin[i] and matrix[i][j] == colMax[j]. If both conditions hold, the value is a lucky number. The key insight is treating the problem as an intersection between two computed properties of the grid. The total runtime is O(m * n) because each element is processed a constant number of times, and the additional storage for row and column arrays is O(m + n).

Recommended for interviews: The iterative row-minimum check is usually the first solution interviewers expect because it demonstrates clear reasoning about matrix traversal. The intersection method is cleaner for larger matrices and shows you understand how to precompute properties to reduce repeated work. Both rely on basic array and matrix traversal patterns commonly tested in interviews.