Jobs

Interviews

Discussions

Lucky Numbers in a Matrix

Easy

Cisco

4 views

Topics:

Arrays

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.

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]
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 coding it in LeetCode

Lucky Numbers in a Matrix

Easy

Cisco

4 views

Topics:

Arrays

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.

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]
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 coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the matrix (number of rows and columns)?
What is the range of possible integer values within the matrix? Could there be negative numbers or zeros?
If there are multiple 'lucky numbers' (i.e., multiple elements that satisfy the condition), should I return all of them, or just one? If only one, is there any preference as to which one to return?
What should I return if the matrix is empty or contains no lucky numbers? Should I return an empty list or null?
Are duplicate values allowed within a row or column, and if so, how does that affect identifying the minimum in a row or the maximum in a column?

Brute Force Solution

Approach

The brute force approach in this matrix problem is all about checking every single number to see if it's a 'lucky number'. We compare each number against all others in its row and column to confirm it meets the lucky number criteria. It's simple but can take a lot of time.

Here's how the algorithm would work step-by-step:

For each number in the matrix, we're going to do some checks.
First, find the smallest number in the row that number belongs to.
Then, find the largest number in the column that number belongs to.
If the number we're checking is both the smallest in its row AND the largest in its column, we've found a lucky number.
If it isn't, we move on to the next number in the matrix and repeat the process.
We continue until we've checked every single number in the entire matrix.

Code Implementation

def find_lucky_numbers_brute_force(matrix):
    lucky_numbers = []
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            element = matrix[row_index][column_index]

            # Find smallest in row
            is_smallest_in_row = True
            for column_check_index in range(number_of_columns):
                if matrix[row_index][column_check_index] < element:
                    is_smallest_in_row = False
                    break

            # Find largest in column
            is_largest_in_column = True
            for row_check_index in range(number_of_rows):
                if matrix[row_check_index][column_index] > element:
                    is_largest_in_column = False
                    break

            # Check if both conditions are met
            if is_smallest_in_row and is_largest_in_column:

                # Found a lucky number
                lucky_numbers.append(element)

    return lucky_numbers

Big(O) Analysis

Time Complexity

O(m*n*(m+n)) – Given an m x n matrix, the outer loops iterate through each of the m*n elements. For each element, we find the minimum in its row, which takes O(n) time, and the maximum in its column, which takes O(m) time. Thus, for each element, we perform O(n + m) operations. Since we do this for every element in the m x n matrix, the total time complexity is O(m*n*(m+n)).

Space Complexity

O(1) – The provided algorithm iterates through the matrix and compares each element to its row and column without creating any auxiliary data structures that scale with the input size. It only uses a constant number of variables for comparisons (finding min in row, max in column). Therefore, the auxiliary space required remains constant regardless of the matrix dimensions (number of rows and columns). Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find numbers that are both the smallest in their row and the largest in their column. We can do this efficiently by first finding the smallest number in each row and then checking if any of those are the largest in their respective columns.

Here's how the algorithm would work step-by-step:

First, for each row in the matrix, find the smallest number.
Next, for each of the numbers you found in the previous step, check if it is the largest number in its corresponding column.
If a number is both the smallest in its row and the largest in its column, then that number is a 'lucky number'.
Collect all such 'lucky numbers'.
Return the list of all the numbers you have collected.

Code Implementation

def luckyNumbers (matrix):
    lucky_numbers = []
    
    # Iterate through each row to find the minimum value
    for row in matrix:
        minimum_in_row = min(row)
        column_index = row.index(minimum_in_row)

        # Verify that the minimum in row is the maximum in column
        is_largest_in_column = True
        for i in range(len(matrix)):
            if matrix[i][column_index] > minimum_in_row:
                is_largest_in_column = False
                break

        # Add the lucky number to our list
        if is_largest_in_column:
            lucky_numbers.append(minimum_in_row)

    return lucky_numbers

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each row (m rows) to find the minimum element. This takes O(n) time per row, where n is the number of columns. Then, for each minimum element found (at most m), it checks if it's the maximum in its column, which again takes O(m) time. Therefore, the time complexity is driven by m iterations of the outer loop finding the row minimums which takes m*n operations. The column maximum check is also proportional to m*m which will be less than m*n operations, therefore, the overall complexity is O(m*n) where m is the number of rows and n is the number of columns in the matrix.

Space Complexity

O(min(M, N)) – The algorithm finds the minimum of each row, potentially storing these values. The maximum number of such minimums is equal to the number of rows, M. Similarly, we potentially store the lucky numbers we found. The maximum number of lucky numbers would be the number of rows, M. Then, the overall extra space used scales linearly with the number of rows M (or the number of columns N) in the matrix as we store minimums for each row and lucky numbers found, so the overall auxiliary space complexity is O(min(M, N)), where M is the number of rows and N is the number of columns.

Edge Cases

Case	How to Handle
Null or empty matrix	Return an empty list if the input matrix is null or has zero rows or columns.
Matrix with only one row or one column	The minimum element of the single row must be the maximum element of its column to be a lucky number, otherwise return empty list.
Matrix with all identical values	If the minimum value in each row is the same, and that value is the maximum in its column, return that value as a lucky number (might be duplicates).
Matrix with negative numbers	The algorithm should correctly identify lucky numbers even with negative values present, considering negative minimums and maximums.
Matrix with extremely large numbers (potential overflow)	Use appropriate data types (e.g., long) to avoid potential integer overflow when comparing numbers.
Matrix contains duplicate minimum values in a row	Consider all of the duplicate minimum values and check whether the column they are in is maximum for that column.
No lucky number exists in the matrix	Return an empty list if no element satisfies both the row-minimum and column-maximum conditions.
Large matrix dimensions (scaling concerns)	The algorithm should scale linearly with the size of the matrix (rows * cols), and avoid operations with higher complexities.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the dimensions of the matrix (number of rows and columns)?
What is the range of possible integer values within the matrix? Could there be negative numbers or zeros?
If there are multiple 'lucky numbers' (i.e., multiple elements that satisfy the condition), should I return all of them, or just one? If only one, is there any preference as to which one to return?
What should I return if the matrix is empty or contains no lucky numbers? Should I return an empty list or null?
Are duplicate values allowed within a row or column, and if so, how does that affect identifying the minimum in a row or the maximum in a column?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For each number in the matrix, we're going to do some checks.
First, find the smallest number in the row that number belongs to.
Then, find the largest number in the column that number belongs to.
If the number we're checking is both the smallest in its row AND the largest in its column, we've found a lucky number.
If it isn't, we move on to the next number in the matrix and repeat the process.
We continue until we've checked every single number in the entire matrix.

Code Implementation

def find_lucky_numbers_brute_force(matrix):
    lucky_numbers = []
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            element = matrix[row_index][column_index]

            # Find smallest in row
            is_smallest_in_row = True
            for column_check_index in range(number_of_columns):
                if matrix[row_index][column_check_index] < element:
                    is_smallest_in_row = False
                    break

            # Find largest in column
            is_largest_in_column = True
            for row_check_index in range(number_of_rows):
                if matrix[row_check_index][column_index] > element:
                    is_largest_in_column = False
                    break

            # Check if both conditions are met
            if is_smallest_in_row and is_largest_in_column:

                # Found a lucky number
                lucky_numbers.append(element)

    return lucky_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, for each row in the matrix, find the smallest number.
Next, for each of the numbers you found in the previous step, check if it is the largest number in its corresponding column.
If a number is both the smallest in its row and the largest in its column, then that number is a 'lucky number'.
Collect all such 'lucky numbers'.
Return the list of all the numbers you have collected.

Code Implementation

def luckyNumbers (matrix):
    lucky_numbers = []
    
    # Iterate through each row to find the minimum value
    for row in matrix:
        minimum_in_row = min(row)
        column_index = row.index(minimum_in_row)

        # Verify that the minimum in row is the maximum in column
        is_largest_in_column = True
        for i in range(len(matrix)):
            if matrix[i][column_index] > minimum_in_row:
                is_largest_in_column = False
                break

        # Add the lucky number to our list
        if is_largest_in_column:
            lucky_numbers.append(minimum_in_row)

    return lucky_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return an empty list if the input matrix is null or has zero rows or columns.
Matrix with only one row or one column	The minimum element of the single row must be the maximum element of its column to be a lucky number, otherwise return empty list.
Matrix with all identical values	If the minimum value in each row is the same, and that value is the maximum in its column, return that value as a lucky number (might be duplicates).
Matrix with negative numbers	The algorithm should correctly identify lucky numbers even with negative values present, considering negative minimums and maximums.
Matrix with extremely large numbers (potential overflow)	Use appropriate data types (e.g., long) to avoid potential integer overflow when comparing numbers.
Matrix contains duplicate minimum values in a row	Consider all of the duplicate minimum values and check whether the column they are in is maximum for that column.
No lucky number exists in the matrix	Return an empty list if no element satisfies both the row-minimum and column-maximum conditions.
Large matrix dimensions (scaling concerns)	The algorithm should scale linearly with the size of the matrix (rows * cols), and avoid operations with higher complexities.