Given an m x n matrix of distinct numbers, return all lucky numbers in the matrix in any order.
A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.
Example 1:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.
Example 2:
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] Output: [12] Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.
Example 3:
Input: matrix = [[7,8],[1,2]] Output: [7] Explanation: 7 is the only lucky number since it is the minimum in its row and the maximum in its column.
Constraints:
m == mat.lengthn == mat[i].length1 <= n, m <= 501 <= matrix[i][j] <= 105.This approach involves two main steps. First, find the minimum element in each row and keep track of the potential lucky numbers. Then, verify these potential numbers to check if they are the maximum in their respective columns.
This C program identifies lucky numbers by first finding the index of the minimum in each row. Then it checks those values across columns to ascertain if they're maximums within their respective columns.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix.
Space Complexity: O(m) for storing the minimum indices for each row.
This approach leverages set operations from mathematics to identify potential lucky numbers. We extract the row minimums and column maximums into separate sets and find the intersection of these sets for possible lucky numbers.
This C implementation performs a mathematical check for intersection by keeping potential lucky values in a temporary array, then validating if they appear within the maximums of their columns.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(n) for storing column maximums.
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix. |
| Mathematical Intersection | Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. |
Search a 2D Matrix - Leetcode 74 - Python • NeetCode • 206,302 views views
Watch 9 more video solutions →Practice Lucky Numbers in a Matrix with our built-in code editor and test cases.
Practice on FleetCode