algoadvance

Leetcode 1380. Lucky Numbers in a Matrix

Problem Statement

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 that is the minimum element in its row and the maximum in its column.

Clarifying Questions

1. Input Constraints:
   • Can the matrix have any negative numbers?
   • What is the maximum size of the matrix?
   • Will the matrix always be non-empty?
2. Output Format:
   • Should the result be a list of integers?

For simplicity, let’s assume the matrix is always non-empty and contains only distinct integers.

Strategy

To find the lucky numbers, we’ll follow these steps:

1. Identify Minimums in Rows:
   • Traverse each row to find the minimum value in each row and store their positions (row, column).
2. Check Maximums in Columns:
   • For each position (row, column) identified as a minimum in its row, verify whether it’s the maximum in its respective column.
3. Compilation of Results:
   • Gather all the elements that satisfy both conditions and prepare the final result list.

Code

Let’s implement the strategy in Java:

import java.util.ArrayList;
import java.util.List;

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

        // Step 1: Identify the minimum elements in each row
        int[] minRow = new int[m];
        int[] minRowColIndex = new int[m];
        for (int i = 0; i < m; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] < min) {
                    min = matrix[i][j];
                    minRowColIndex[i] = j;
                }
            }
            minRow[i] = min;
        }

        // Step 2: Check if these minimum elements are the maximum in their respective columns
        for (int i = 0; i < m; i++) {
            int col = minRowColIndex[i];
            int minValue = minRow[i];
            boolean isMaxInCol = true;
            
            for (int k = 0; k < m; k++) {
                if (matrix[k][col] > minValue) {
                    isMaxInCol = false;
                    break;
                }
            }
            
            if (isMaxInCol) {
                luckyNumbers.add(minValue);
            }
        }

        return luckyNumbers;
    }
}

Time Complexity

• Finding minimums in each row: (O(m \times n))
• Checking maximum in columns: (O(m \times m)) for each row minimum. Since there are (m) rows, in the worst case we can decide all (m) rows, giving us (O(m \times n + m \times m) = O(m \times (n + m)))

Thus, the overall time complexity is (O(m \times (n + m))), which simplifies to (O(m \times n + m^2)). For large (m) and (n), this will be dominated by the (m \times n) term.

The space complexity is (O(m)), needed for storing the minimum elements and their column indexes.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?