Solution: Lucky Numbers in a Matrix

Let’s solve the Lucky Numbers in a Matrix problem using the Graphs pattern.

We'll cover the following

Statement

Given an m×nm \times n matrix of distinct numbers, return the lucky number in the matrix.

A lucky number is an element of the matrix such that it is the smallest element in its row and largest in its column.

Constraints:

  • m=m = matrix.length

  • n=n = matrix[i].length

  • 1≤n1 \leq n, m≤50m \leq 50

  • 1≤1 \leq matrix[i][j] ≤105\leq 10^5

  • All elements in the matrix are distinct.

Solution

The core idea behind the solution is to recognize that there can be, at most, one lucky number in the matrix. This is proven by contradiction, as having two such numbers would violate the unique conditions for being a lucky number.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.