1380. Lucky Numbers in a Matrix

leetcode

Links

Problem: Lucky Numbers in a Matrix

A "lucky number" in a matrix is defined as an element that is the minimum element in its row and the maximum element in its column. Given a matrix of integers, the task is to find all lucky numbers in the matrix.

Solution Description:

To implement the problem, we need to follow these steps:

Identify Row Minimums: For each row in the matrix, we determine the minimum value.
Check Column Maximums: For each of the identified row minimums, we check if it is the maximum in its respective column.
Collect Lucky Numbers: If a number meets both conditions, it is added to the list of lucky numbers.

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns, as we traverse each element of the matrix at least once. The space complexity is O(k), where k is the number of lucky numbers, as we store them in a list.

Example:

Consider the matrix:

1 10 4 2
9 3 8 7
15 16 17 12

The minimum in the first row is 1, which is also the maximum in its column (1).
The minimum in the second row is 3, which is not the maximum in its column (9).
The minimum in the third row is 12, which is not the maximum in its column (17).

Thus, the only lucky number is `1`.

Setup:

We will set up the initial solution and testing framework in JavaScript.

// Helper functions will be defined here.

/**
 * Function to find lucky numbers in a matrix.
 * @param {number[][]} matrix - The input matrix of integers.
 * @return {number[]} - An array of lucky numbers.
 */
function findLuckyNumbers(matrix) {

    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    const numRows = matrix.length;
    const numCols = matrix[0].length;

    const rowMin = Array(numRows).fill(+Infinity);
    const colMax = Array(numCols).fill(-Infinity);

    for (let row = 0; row < numRows; row += 1) {
        for (let col = 0; col < numCols; col += 1) {
            rowMin[row] = Math.min(rowMin[row], matrix[row][col]);
            colMax[col] = Math.max(colMax[col], matrix[row][col]);
        }
    }

    log('rowMin');
    table(rowMin);

    log('colMax');
    table(colMax);

    const result = [];

    for (const el of colMax) {
        if (rowMin.indexOf(el) > -1) {
            result.push(el);
        }
    }

    return result;
}

// Test cases to check the function
const testCases = [
    { matrix:
      [
          [3,7,8],
          [9,11,13],
          [15,16,17]
      ], expected: [15] },
    { matrix: [[5]], expected: [5] },
];

testCases.forEach((test, index) => {
    const result = findLuckyNumbers(test.matrix);
    console.log(`Test Case ${index + 1}: ${result.toString() === test.expected.toString() ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});