algoadvance

Leetcode 1380. Lucky Numbers in a Matrix

Problem Statement

You are given an m x n matrix of distinct numbers. A lucky number is defined as an element of the matrix that is the minimum element in its row and the maximum in its column.

You need to find all the lucky numbers in the matrix in any order.

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]

Clarifying Questions

  1. Can the matrix have negative numbers?
  2. Are there any constraints on the size of the matrix?
  3. Is it guaranteed that there will always be a lucky number in the matrix, or do I need to handle the case where there may not be one?
  4. Are matrix rows and columns guaranteed to be filled with distinct numbers?

Strategy

  1. Identify the minimum elements in each row and store them.
  2. Identify the maximum elements in each column and store them.
  3. Find the intersection of the minimum row elements and maximum column elements to determine the lucky numbers.

Code Solution

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

vector<int> luckyNumbers (vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<int> minRow(m, INT_MAX);
    vector<int> maxCol(n, INT_MIN);
    
    // Step 1: Find the minimum element in each row
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            minRow[i] = min(minRow[i], matrix[i][j]);
        }
    }
    
    // Step 2: Find the maximum element in each column
    for (int j = 0; j < n; ++j) {
        for (int i = 0; i < m; ++i) {
            maxCol[j] = max(maxCol[j], matrix[i][j]);
        }
    }
    
    // Step 3: Find intersections of these two sets
    vector<int> result;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == minRow[i] && matrix[i][j] == maxCol[j]) {
                result.push_back(matrix[i][j]);
            }
        }
    }
    
    return result;
}

Time Complexity

The overall time complexity is O(m * n), where m is the number of rows and n is the number of columns. This is efficient for a matrix of moderate size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI