Lucky Numbers in a Matrix

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

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.

Examples:

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.

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.

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 == matrix.length
n == matrix[i].length
1 <= m, n <= 50
1 <= matrix[i][j] <= 10⁵
All elements in the matrix are distinct.

Editorial

Intuition:

A lucky number must be simultaneously the minimum in its row and the maximum in its column. Since all elements are distinct, we can independently compute the minimum value for each row and the maximum value for each column. Then, any element that equals both its row's minimum and its column's maximum is a lucky number.

Approach:

Compute the minimum value for each row and store in an array rowMin.
Compute the maximum value for each column and store in an array colMax.
Iterate through every matrix element. If matrix[i][j] equals both rowMin[i] and colMax[j], add it to the result list.
Return the collected lucky numbers (the order does not matter).

#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> rowMin(m, INT_MAX);
        vector<int> colMax(n, INT_MIN);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowMin[i] = min(rowMin[i], matrix[i][j]);
            }
        }

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colMax[j] = max(colMax[j], matrix[i][j]);
            }
        }

        vector<int> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                    result.push_back(matrix[i][j]);
                }
            }
        }
        return result;
    }
};
import java.util.*;

class Solution {
    public List<Integer> luckyNumbers(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] rowMin = new int[m];
        int[] colMax = new int[n];

        for (int i = 0; i < m; i++) {
            rowMin[i] = Integer.MAX_VALUE;
        }
        for (int j = 0; j < n; j++) {
            colMax[j] = Integer.MIN_VALUE;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowMin[i] = Math.min(rowMin[i], matrix[i][j]);
            }
        }

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colMax[j] = Math.max(colMax[j], matrix[i][j]);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                    result.add(matrix[i][j]);
                }
            }
        }
        return result;
    }
}
from typing import List

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        n = len(matrix[0])
        row_mins = [min(row) for row in matrix]
        col_maxs = [max(matrix[i][j] for i in range(m)) for j in range(n)]
        
        result = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == row_mins[i] and matrix[i][j] == col_maxs[j]:
                    result.append(matrix[i][j])
        return result
class Solution {
    luckyNumbers(matrix) {
        const m = matrix.length;
        const n = matrix[0].length;
        const rowMins = new Array(m).fill(Infinity);
        const colMaxs = new Array(n).fill(-Infinity);

        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                rowMins[i] = Math.min(rowMins[i], matrix[i][j]);
            }
        }

        for (let j = 0; j < n; j++) {
            for (let i = 0; i < m; i++) {
                colMaxs[j] = Math.max(colMaxs[j], matrix[i][j]);
            }
        }

        const result = [];
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (matrix[i][j] === rowMins[i] && matrix[i][j] === colMaxs[j]) {
                    result.push(matrix[i][j]);
                }
            }
        }
        return result;
    }
}

Complexity Analysis:

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. We iterate through the matrix three times: once for row minima, once for column maxima, and once to collect lucky numbers.

Space Complexity: O(m + n) for storing the rowMin and colMax arrays. The output list uses O(k) extra space, where k is the number of lucky numbers (at most min(m, n)).

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories