Skip to main content

Matrix

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

💡
Try it with yourself

Brute Force

Okay, so here's the thought process:

What comes to mind after reading the problem statement?
We need to identify elements in a matrix that satisfy two specific conditions: the smallest in their row and the largest in their column.
This immediately suggests that for each element, we need to perform two checks — one involving its row and another involving its column.

To achieve this, we can iterate through the matrix, iterating each element one by one and we need to verify whether it meets these criteria.

So how we will confirm whether the element is minimum in the row and maximum in their column?

Let's define two flags: isRowMin and isColMax initialized to track whether the element satisfies the rows and column condition.

Now, to check if the current element is the smallest in its row, go through all elements in that row one by one. If you find any element smaller than the current one, it means the current element is not the smallest. In that case, set isRowMin to false and stop checking further. This way, you only continue if the current element might still be the smallest.

Similarly, to check if the current element is the largest in its column, go through all the elements in that column one by one. If you find any element that is larger than the current element, it means the current element is not the largest.
In that case, set isColMax to false and stop checking further. This ensures you only continue if the current element might still be the largest in its column.

Let Understand with an Example

matrix = [ [3, 7, 8], [9, 11, 13], [15, 16, 17] ]

We aim to find the lucky numbers — elements that are the smallest in their row and the largest in their column.

Step 1: Process Row by Row

First Row: [3, 7, 8]

  • Element 3 at (0, 0):
    • Row Check: Is 3 the smallest in the row?
      • Compare 3 with the other elements in its row: 7 and 8.
      • Yes, 3 is the smallest (3 < 7 and 3 < 8).
    • Column Check: Is 3 the largest in its column?
      • Compare 3 with the other elements in its column: 9 and 15.
      • No, 3 is not the largest (15 > 3).
    • Result: 3 is not a lucky number.
  • Element 7 at (0, 1):
    • Row Check: Is 7 the smallest in the row?
      • Compare 7 with 3 and 8.
      • No, 7 is not the smallest (3 < 7).
    • Result: 7 is not a lucky number.
  • Element 8 at (0, 2):
    • Row Check: Is 8 the smallest in the row?
      • Compare 8 with 3 and 7.
      • No, 8 is not the smallest (3 < 8).
    • Result: 8 is not a lucky number.

Second Row: [9, 11, 13]

  • Element 9 at (1, 0):
    • Row Check: Is 9 the smallest in the row?
      • Compare 9 with 11 and 13.
      • Yes, 9 is the smallest (9 < 11 and 9 < 13).
    • Column Check: Is 9 the largest in its column?
      • Compare 9 with 3 and 15.
      • No, 9 is not the largest (15 > 9).
    • Result: 9 is not a lucky number.
  • Element 11 at (1, 1):
    • Row Check: Is 11 the smallest in the row?
      • Compare 11 with 9 and 13.
      • No, 11 is not the smallest (9 < 11).
    • Result: 11 is not a lucky number.
  • Element 13 at (1, 2):
    • Row Check: Is 13 the smallest in the row?
      • Compare 13 with 9 and 11.
      • No, 13 is not the smallest (9 < 13).
    • Result: 13 is not a lucky number.

Third Row: [15, 16, 17]

  • Element 15 at (2, 0):
    • Row Check: Is 15 the smallest in the row?
      • Compare 15 with 16 and 17.
      • Yes, 15 is the smallest (15 < 16 and 15 < 17).
    • Column Check: Is 15 the largest in its column?
      • Compare 15 with 3 and 9.
      • Yes, 15 is the largest (15 > 3 and 15 > 9).
    • Result: 15 is a lucky number.
  • Element 16 at (2, 1):
    • Row Check: Is 16 the smallest in the row?
      • Compare 16 with 15 and 17.
      • No, 16 is not the smallest (15 < 16).
    • Result: 16 is not a lucky number.
  • Element 17 at (2, 2):
    • Row Check: Is 17 the smallest in the row?
      • Compare 17 with 15 and 16.
      • No, 17 is not the smallest (15 < 17).
    • Result: 17 is not a lucky number.

Step 2: Collect the Lucky Numbers

After processing all rows and columns:

  • Only 15 satisfies both conditions:
    • It is the smallest in its row [15, 16, 17].
    • It is the largest in its column [3, 9, 15].

Final Output: [15]

Step to write code

Step 1: Initialize the Result Vector
Begin by creating a vector called luckyNumbers to store the lucky numbers identified in the matrix. This vector will be used to store elements that satisfy the required conditions and will be returned at the end of the function.

Step 2: Retrieve Matrix Dimensions
Determine the number of rows (m) and columns (n) in the given matrix. Use the size of the matrix to understand its structure:

  • m represents the total number of rows (matrix.size()).
  • n represents the total number of columns (matrix[0].size()).

Step 3: Traverse the Entire Matrix
Use nested loops to iterate through each element in the matrix:

  • The outer loop runs from i = 0 to i = m-1, iterating through all rows.
  • The inner loop runs from j = 0 to j = n-1, iterating through all columns for the current row.

Step 4: Process Each Element
For the current element matrix[i][j], assume it could be a lucky number. Store its value in a variable current.
Initialize two flags:

  • isRowMin: Assume the current element is the smallest in its row.
  • isColMax: Assume the current element is the largest in its column.

Step 5: Verify If the Current Element is the Smallest in its Row
Check all elements in row i:

  • Use a loop with an index k running from 0 to n-1.
  • Compare matrix[i][k] (all elements in the row) with current.
  • If any matrix[i][k] is smaller than current, set isRowMin to false and break the loop since current cannot be the smallest.

Step 6: Verify If the Current Element is the Largest in its Column
Check all elements in column j:

  • Use a loop with an index k running from 0 to m-1.
  • Compare matrix[k][j] (all elements in the column) with current.
  • If any matrix[k][j] is larger than current, set isColMax to false and break the loop since current cannot be the largest.

Step 6: Add to Result if Both Conditions are Met
After checking both the row and the column:

  • If isRowMin is true and isColMax is true, append current to the luckyNumbers vector.

Step 7: Return the Result
Once all elements in the matrix have been processed:

  • Return the luckyNumbers vector. It will contain all the elements that meet the criteria of being a lucky number.
  • If no such numbers are found, the vector will remain empty.
Code Implementation
C++ 


class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        // To store the lucky numbers found in the matrix
        vector<int> luckyNumbers; 

        // Number of rows in the matrix
        int m = matrix.size();

        // Number of columns in the matrix
        int n = matrix[0].size();

        // Iterate through each cell in the matrix
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // Current element being checked
                int current = matrix[i][j]; 

                // Flags to check if the current element is a lucky number
                bool isRowMin = true, isColMax = true; 

                // Check if the current element is the minimum in its row
                for (int k = 0; k < n; ++k) {
                    if (matrix[i][k] < current) {
                        // Current is not the minimum in its row
                        isRowMin = false;

                        // No need to check further in the row
                        break; 
                    }
                }

                // Check if the current element is the maximum in its column
                for (int k = 0; k < m; ++k) {
                    if (matrix[k][j] > current) {
                        // Current is not the maximum in its column
                        isColMax = false;

                        // No need to check further in the column
                        break; 
                    }
                }

                // If both conditions are met, it's a lucky number
                if (isRowMin && isColMax) {
                    // Add the lucky number to the result
                    luckyNumbers.push_back(current); 
                }
            }
        }

        // Return all found lucky numbers
        return luckyNumbers; 
    }
};

Java 
import java.util.*;

class Solution {
    public List<Integer> luckyNumbers(int[][] matrix) {
        // To store the lucky numbers found in the matrix
        List<Integer> luckyNumbers = new ArrayList<>();

        // Number of rows in the matrix
        int m = matrix.length;

        // Number of columns in the matrix
        int n = matrix[0].length;

        // Iterate through each cell in the matrix
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // Current element being checked
                int current = matrix[i][j];

                // Flags to check if the current element is a lucky number
                boolean isRowMin = true, isColMax = true;

                // Check if the current element is the minimum in its row
                for (int k = 0; k < n; ++k) {
                    if (matrix[i][k] < current) {
                        // Current is not the minimum in its row
                        isRowMin = false;

                        // No need to check further in the row
                        break;
                    }
                }

                // Check if the current element is the maximum in its column
                for (int k = 0; k < m; ++k) {
                    if (matrix[k][j] > current) {
                        // Current is not the maximum in its column
                        isColMax = false;

                        // No need to check further in the column
                        break;
                    }
                }

                // If both conditions are met, it's a lucky number
                if (isRowMin && isColMax) {
                    // Add the lucky number to the result
                    luckyNumbers.add(current);
                }
            }
        }

        // Return all found lucky numbers
        return luckyNumbers;
    }
}

Python 
class Solution(object):
    def luckyNumbers(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        # List to store the lucky numbers found in the matrix
        lucky_numbers = []

        # Number of rows in the matrix
        m = len(matrix)

        # Number of columns in the matrix
        n = len(matrix[0])

        # Iterate through each cell in the matrix
        for i in range(m):
            for j in range(n):
                # Current element being checked
                current = matrix[i][j]

                # Check if the current element is the minimum in its row
                is_row_min = all(matrix[i][k] >= current for k in range(n))

                # Check if the current element is the maximum in its column
                is_col_max = all(matrix[k][j] <= current for k in range(m))

                # If both conditions are met, it's a lucky number
                if is_row_min and is_col_max:
                    lucky_numbers.append(current)

        # Return all found lucky numbers
        return lucky_numbers

Javascript 
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var luckyNumbers = function(matrix) {
    // Array to store the lucky numbers found in the matrix
    const luckyNumbers = [];

    // Number of rows in the matrix
    const m = matrix.length;

    // Number of columns in the matrix
    const n = matrix[0].length;

    // Iterate through each cell in the matrix
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Current element being checked
            const current = matrix[i][j];

            // Check if the current element is the minimum in its row
            const isRowMin = matrix[i].every(value => value >= current);

            // Check if the current element is the maximum in its column
            const isColMax = matrix.every(row => row[j] <= current);

            // If both conditions are met, it's a lucky number
            if (isRowMin && isColMax) {
                luckyNumbers.push(current);
            }
        }
    }

    // Return all found lucky numbers
    return luckyNumbers;
};

Time Complexity: O(m * n * (m + n))

Step 1: Iterating through the entire matrix

The outer loop iterates over each row, and the inner loop iterates over each column in that row:

  • Outer loop: This loop runs m times, where m is the number of rows in the matrix (matrix.size()).
  • Inner loop: This loop runs n times, where n is the number of columns in the matrix (matrix[0].size()).

Thus, the total iterations for traversing each element in the matrix is m * n.

Step 2: Checking if the current element is the minimum in its row

For each element in the matrix, we check all elements in its row to see if it's the smallest:

  • This check involves looping through all n elements of the row.
  • Hence, this loop runs n times for each element.

Step 3: Checking if the current element is the largest in its column

Similarly, for each element in the matrix, we check all elements in its column to see if it's the largest:

  • This check involves looping through all m elements of the column.
  • Hence, this loop runs m times for each element.

Step 4: Time Complexity Calculation

  1. Outer loop: Runs m times (for rows).
  2. Inner loop: Runs n times (for columns).
  3. For each element, we perform:
    • An inner loop to check the row, which runs n times.
    • An inner loop to check the column, which runs m times.

Thus, for each element, the time complexity is O(n + m).

Since the matrix has m * n elements, the total time complexity is: O(m×n)×O(n+m)=O(m×n×(m+n))

The overall time complexity of the algorithm is O(m * n * (m + n))

Space Complexity: O(1)

Let's break down the space complexity of the given code:

  1. Input Matrix: The matrix matrix itself is provided as an input. It has dimensions m (rows) × n (columns). So, the space used by the input matrix is O(m * n).
  2. Output Vector: The result vector luckyNumbers stores the lucky numbers found in the matrix. The size of this vector can be at most min(m, n) (i.e., in the worst case, there could be one lucky number per row or per column). This vector does not significantly increase the space complexity beyond the already considered arrays.
  3. Auxiliary Variables: The auxiliary variables used in the algorithm (such as current, isRowMin, isColMax, and the loop counters) take constant space. These are O(1) in space complexity.

Total Space Complexity

The overall space complexity is dominated by the input matrix i.e. O(m*n) over luckyNumbers vector i.e. O(min(m, n)). Therefore, the total space complexity is: O(m*n)

Will this approach runs under given complexity?

Time Complexity Analysis:

  1. Outer Loop:
    • The outer loop iterates over each element in the matrix, so it runs m×n times.
    • Since m,n≤50, the maximum number of iterations is 50×50=2500, which is manageable.
  3. Row Check:
    • For each element, we check if it's the minimum in its row, which involves iterating through all the columns in the row, requiring n iterations. Since n≤50, this is at most 50 iterations.
  5. Column Check:
    • Similarly, for each element, we check if it's the largest in its column, which requires iterating through all the rows in the column, requiring m iterations. Since m≤50, this is also at most 50 iterations.

Thus, for each element, we perform two checks:

  • A row check that takes O(n) time.
  • A column check that takes O(m) time.

Therefore, the time complexity for each element is O(m + n), and with m×n elements, the total time complexity is:

O(m×n×(m+n))=O(50×50×(50+50))=O(50×50×100)=O(250000)

This is well within the acceptable range of operations for typical competitive programming time limits (which are usually on the order of 10^8).

When Will TLE Occur?

If the number of operations exceeds 10810^8108, the solution will likely give a TLE. Let's calculate the number of operations at larger values of mmm and nnn:

  1. If m=100 and n=100: O(100×100×(100+100))=O(100×100×200)=2,000,000 operations.
    This is still well within acceptable limits (since 2×10^6 is much less than 10^8).
  2. If m=200 and n=200: O(200×200×(200+200))=O(200×200×400)=16,000,000 
    operations. This is still below the threshold of 10^8.
  3. If m=500 and n=500: O(500×500×(500+500))=O(500×500×1000)=250,000,000 operations. This exceeds 10^8 operations, and you will likely get a TLE if the time limit is 1 or 2 seconds.

Conclusion:

  • For the current problem, m=50 and n=50 result in 250,000 operations, which is well within the time limit (typically 1-2 seconds).
  • TLE would occur if the number of operations exceeds around 10^8 operations, which would happen if the matrix dimensions are significantly larger (e.g., m=500 and n=500).

Can we optimize it?

Yes, in the previous approach, we used a time complexity of O(m×n×(m+n)), where m×n accounts for iterating through the entire matrix, and m+n is for checking the conditions for each element.

Now, Instead of repeatedly checking the conditions (minimum in a row and maximum in a column) for each element, we can precompute the minimum values for all rows and the maximum values for all columns.

So now, for each row, determine the smallest element and store it along with its row index in a vector named rowMins.

Now similarly for each column, determine the largest element and store it along with its column index in a vector named colMaxes.

After precomputing, compare the precomputed row minimums with the column maximums. If a row minimum matches the column maximum at the same position, it is a lucky number.

Now let's try to understand it with an example:

Example

Input Matrix: [[3, 7, 8], [9, 11, 13], [15, 16, 17]]

Step 1: Find the minimum value in each row
We iterate through each row and find the minimum value:

  • Row 1: [3, 7, 8] → Minimum value is 3.
  • Row 2: [9, 11, 13] → Minimum value is 9.
  • Row 3: [15, 16, 17] → Minimum value is 15.

Now, we have the rowMins array: [3, 9, 15]
Step 2: Find the maximum value in each column

Next, we iterate through each column and find the maximum value:

  • Column 1: [3, 9, 15] → Maximum value is 15.
  • Column 2: [7, 11, 16] → Maximum value is 16.
  • Column 3: [8, 13, 17] → Maximum value is 17.

Now, we have the colMaxes array: [15, 16, 17]
Step 3: Check for lucky numbers

Finally, we check if a number at position (i, j) in the matrix is equal to both:

  • The minimum value in its row rowMins[i].
  • The maximum value in its column colMaxes[j].

We iterate through each element of the matrix:

  • For (0, 0) → matrix[0][0] = 3
    • rowMins[0] = 3, colMaxes[0] = 15
    • 3 != 15, so this is not a lucky number.
  • For (0, 1) → matrix[0][1] = 7
    • rowMins[0] = 3, colMaxes[1] = 16
    • 7 != 16, so this is not a lucky number.
  • For (0, 2) → matrix[0][2] = 8
    • rowMins[0] = 3, colMaxes[2] = 17
    • 8 != 17, so this is not a lucky number.
  • For (1, 0) → matrix[1][0] = 9
    • rowMins[1] = 9, colMaxes[0] = 15
    • 9 != 15, so this is not a lucky number.
  • For (1, 1) → matrix[1][1] = 11
    • rowMins[1] = 9, colMaxes[1] = 16
    • 11 != 16, so this is not a lucky number.
  • For (1, 2) → matrix[1][2] = 13
    • rowMins[1] = 9, colMaxes[2] = 17
    • 13 != 17, so this is not a lucky number.
  • For (2, 0) → matrix[2][0] = 15
    • rowMins[2] = 15, colMaxes[0] = 15
    • 15 == 15 (this satisfies both conditions), so 15 is a lucky number.
  • For (2, 1) → matrix[2][1] = 16
    • rowMins[2] = 15, colMaxes[1] = 16
    • 16 != 15, so this is not a lucky number.
  • For (2, 2) → matrix[2][2] = 17
    • rowMins[2] = 15, colMaxes[2] = 17
    • 17 != 15, so this is not a lucky number.

The only lucky number found is 15, which is the minimum in its row and the maximum in its column.

Steps to write code

Step 1: Define the Problem and Understand the Input

  • You need to identify numbers that satisfy the following:
    • The number is the minimum value in its row.
    • The number is the maximum value in its column.

Step 2: Initialize Necessary Data Structures

  • To efficiently track the minimum values for each row and the maximum values for each column, create two arrays:
    • rowMins to store the minimum value of each row.
    • colMaxes to store the maximum value of each column.
  • You will need to iterate through the matrix to compute these values.

Step 3: Traverse the Matrix to Calculate Row Minimums

  • Iterate through each row of the matrix to find the minimum value in that row.
  • Store the minimum values in the rowMins array.

Step 4: Traverse the Matrix to Calculate Column Maximums

  • Iterate through each column of the matrix to find the maximum value in that column.
  • Store the maximum values in the colMaxes array.

Step 5: Identify the Lucky Numbers

  • After obtaining the rowMins and colMaxes, iterate over each element of the matrix.
  • For each element, check if it is equal to both the minimum value of its row (from rowMins) and the maximum value of its column (from colMaxes).
  • If both conditions are met, it is a lucky number.

Step 6: Return the Result

  • Store all lucky numbers in a vector and return the result at the end.
Code Implementation
C++ 
class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        // To store the lucky numbers found in the matrix
        vector<int> luckyNumbers;

        // Number of rows and columns
        int m = matrix.size();
        int n = matrix[0].size();

        // Step 1: Find the minimum value in each row
        vector<int> rowMins(m, INT_MAX);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rowMins[i] = min(rowMins[i], matrix[i][j]);
            }
        }

        // Step 2: Find the maximum value in each column
        vector<int> colMaxes(n, INT_MIN);
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                colMaxes[j] = max(colMaxes[j], matrix[i][j]);
            }
        }

        // Step 3: Check for lucky numbers
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxes[j]) {
                    luckyNumbers.push_back(matrix[i][j]);
                }
            }
        }

        // Return all found lucky numbers
        return luckyNumbers;
    }
};

Java 

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        // List to store the lucky numbers found in the matrix
        List<Integer> luckyNumbers = new ArrayList<>();

        // Number of rows and columns
        int m = matrix.length;
        int n = matrix[0].length;

        // Step 1: Find the minimum value in each row
        int[] rowMins = new int[m];
        Arrays.fill(rowMins, Integer.MAX_VALUE);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowMins[i] = Math.min(rowMins[i], matrix[i][j]);
            }
        }

        // Step 2: Find the maximum value in each column
        int[] colMaxes = new int[n];
        Arrays.fill(colMaxes, Integer.MIN_VALUE);
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colMaxes[j] = Math.max(colMaxes[j], matrix[i][j]);
            }
        }

        // Step 3: Check for lucky numbers
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxes[j]) {
                    luckyNumbers.add(matrix[i][j]);
                }
            }
        }

        // Return all found lucky numbers
        return luckyNumbers;
    }
}

Python 
class Solution:
    def luckyNumbers(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        # List to store the lucky numbers found in the matrix
        lucky_numbers = []

        # Step 1: Find the minimum value in each row
        row_mins = [min(row) for row in matrix]

        # Step 2: Find the maximum value in each column
        col_maxes = [max(col) for col in zip(*matrix)]

        # Step 3: Check for lucky numbers
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == row_mins[i] and matrix[i][j] == col_maxes[j]:
                    lucky_numbers.append(matrix[i][j])

        # Return all found lucky numbers
        return lucky_numbers

Javascript 
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var luckyNumbers = function(matrix) {
    // Array to store the lucky numbers found in the matrix
    const luckyNumbers = [];

    // Number of rows in the matrix
    const m = matrix.length;

    // Number of columns in the matrix
    const n = matrix[0].length;

    // Step 1: Find the minimum value in each row
    const rowMins = matrix.map(row => Math.min(...row));

    // Step 2: Find the maximum value in each column
    const colMaxes = Array(n).fill(Number.MIN_SAFE_INTEGER);
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < m; i++) {
            colMaxes[j] = Math.max(colMaxes[j], matrix[i][j]);
        }
    }

    // Step 3: Check for lucky numbers
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === rowMins[i] && matrix[i][j] === colMaxes[j]) {
                luckyNumbers.push(matrix[i][j]);
            }
        }
    }

    // Return all found lucky numbers
    return luckyNumbers;
};

Time Complexity: O(m×n)

Let's break down the time complexity of the given solution in detail.

1. Row Minimum Calculation:

We iterate over each element in the matrix to find the minimum value in each row:

  • Outer loop: We loop over each row, so we run the loop m times, where m is the number of rows.
  • Inner loop: For each row, we loop over all the columns, so the inner loop runs n times, where n is the number of columns.

Thus, the time complexity for finding the row minimums is: O(m×n)

This is because we are iterating through every element of the matrix once to find the minimum in each row.

2. Column Maximum Calculation:

Similarly, to find the maximum value in each column, we do the following:

  • Outer loop: We loop over each column, so the outer loop runs n times, where n is the number of columns.
  • Inner loop: For each column, we loop over all the rows, so the inner loop runs m times, where m is the number of rows.

Thus, the time complexity for finding the column maximums is: O(m×n)

This is because we are iterating through every element of the matrix once to find the maximum in each column.

3. Identifying Lucky Numbers:

After calculating the row minimums and column maximums, we need to check if an element in the matrix satisfies the "lucky number" condition, i.e., it must be the minimum value in its row and the maximum value in its column.

  • Outer loop: We loop over each row, so we run the loop m times.
  • Inner loop: For each row, we loop over all the columns, so the inner loop runs n times.

Thus, the time complexity for identifying lucky numbers is: O(m×n)

We check every element in the matrix once, and for each element, we check if it is equal to both the row minimum and column maximum.

Total Time Complexity:

Since each of the three steps (finding row minimums, finding column maximums, and identifying lucky numbers) takes O(m×n) time, the overall time complexity is the sum of these three steps. However, the time complexities of these steps are all independent, and we just add them up:

O(m×n)+O(m×n)+O(m×n)=O(3×m×n)

Since constants are ignored in big-O notation, the total time complexity simplifies to: O(m×n)

Space Complexity: O(m+n)

  1. Matrix Input:
    • The matrix is given as input, and its size is m x n, where m is the number of rows and n is the number of columns. This matrix is not part of the additional space used in the algorithm, as it is the input itself. We will not count this in the space complexity because it's provided beforehand.
  3. Auxiliary Arrays:
    • rowMins: This array is used to store the minimum value of each row. It has a size of m (one entry per row).
    • colMaxes: This array is used to store the maximum value of each column. It has a size of n (one entry per column).
      Thus, the total space used by these two arrays is: O(m+n)
  5. Other Variables:
    • A few other variables (like iterators in loops, a vector to store lucky numbers, and intermediate variables) are used. These do not grow with input size and take constant space, so their contribution to space complexity is O(1).
  7. luckyNumbers Vector:
    • The result vector luckyNumbers stores the lucky numbers found in the matrix. The size of this vector can be at most min(m, n) (i.e., in the worst case, there could be one lucky number per row or per column). This vector does not significantly increase the space complexity beyond the already considered arrays.

Final Space Complexity:

The space complexity is dominated by the two arrays: rowMins and colMaxes.

Thus, the overall space complexity is: O(m+n)

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Convert 1D array to 2D array

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.

The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.

Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

Reshape the Matrix

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.