We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lucky Numbers in a Matrix

Number: 1496

Difficulty: Easy

Paid? No

Companies: Cisco, Oracle

Problem Description

Given an m x n matrix of distinct numbers, find all lucky numbers in the matrix. A lucky number is defined as an element that is the minimum element in its row and simultaneously the maximum element in its column.

Key Insights

  • For each row, compute the minimum element and its column index.
  • For each candidate minimum element, verify if it is the maximum element in its column.
  • Because all numbers are distinct, there is at most one valid number per row.
  • A simple two-step approach yields an efficient solution.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(1) extra space (ignoring the output list).

Solution

The solution involves iterating through each row of the matrix to identify the minimum element along with its column index. Then, for each candidate lucky number, check its column to see if it is the maximum element. This approach uses basic loops and comparisons without requiring additional data structures beyond the output list. The algorithm is efficient given the constraints (m, n <= 50).

Code Solutions

# Python Solution
def luckyNumbers(matrix):
    lucky_numbers = []
    # Iterate over each row
    for row in matrix:
        # Find the minimum element and its column index in the current row
        min_val = min(row)
        col_idx = row.index(min_val)
        # Check if this min_val is the maximum in its column
        if all(min_val >= matrix[r][col_idx] for r in range(len(matrix))):
            lucky_numbers.append(min_val)
    return lucky_numbers

# Example usage:
print(luckyNumbers([[3,7,8],[9,11,13],[15,16,17]]))  # Output: [15]
← Back to All Questions