Lucky Numbers in a Matrix - Practice Coding Problems

Lucky Numbers in a Matrix - Problem

Array Matrix Easy

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.

Input & Output

Example 1 — Basic Case with Lucky Number

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

› Output: [15]

💡 Note: 15 is the minimum in row 2 [15,16,17] and maximum in column 0 [3,9,15], making it a lucky number

Example 2 — No Lucky Numbers

$ Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]

› Output: []

💡 Note: No element satisfies both conditions: being minimum in its row AND maximum in its column

Example 3 — Single Element Matrix

$ Input: matrix = [[7]]

› Output: [7]

💡 Note: Single element is both minimum in its row and maximum in its column by definition

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ n, m ≤ 50
1 ≤ matrix[i][j] ≤ 10⁵
All elements in the matrix are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3x4 matrix with distinct integers

Check Conditions

Find elements that are row minimum AND column maximum

Lucky Numbers

Return all elements satisfying both conditions

Key Takeaway

🎯 Key Insight: An element can only be lucky if it's simultaneously the smallest in its row and largest in its column

Asked in

a Amazon 25 M Microsoft 18

The key insight is that a lucky number must simultaneously be the minimum in its row AND maximum in its column. The optimal approach precomputes row minimums and column maximums in O(mn) time, then finds intersections. Time: O(mn), Space: O(m+n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Precompute Row Min & Column Max	O(mn)	O(m+n)	Pre-calculate all row minimums and column maximums, then find intersections
Brute Force - Check Every Element	O(m²n²)	O(1)	For each element, verify if it's minimum in its row and maximum in its column

Optimized - Precompute Row Min & Column Max — Algorithm Steps

First pass: find minimum in each row
First pass: find maximum in each column
Second pass: check if element equals both row min and column max
Add matching elements to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute Row Minimums

Find minimum value in each row

Compute Column Maximums

Find maximum value in each column

Find Intersections

Elements that are both row min AND column max

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int* result = (int*)malloc(matrixSize * matrixColSize[0] * sizeof(int));
    *returnSize = 0;
    
    // Find minimum in each row
    int* rowMins = (int*)malloc(matrixSize * sizeof(int));
    for (int i = 0; i < matrixSize; i++) {
        rowMins[i] = matrix[i][0];
        for (int j = 1; j < matrixColSize[i]; j++) {
            if (matrix[i][j] < rowMins[i]) {
                rowMins[i] = matrix[i][j];
            }
        }
    }
    
    // Find maximum in each column
    int* colMaxs = (int*)malloc(matrixColSize[0] * sizeof(int));
    for (int j = 0; j < matrixColSize[0]; j++) {
        colMaxs[j] = matrix[0][j];
        for (int i = 1; i < matrixSize; i++) {
            if (matrix[i][j] > colMaxs[j]) {
                colMaxs[j] = matrix[i][j];
            }
        }
    }
    
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < matrixColSize[i]; j++) {
            if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j]) {
                result[(*returnSize)++] = matrix[i][j];
            }
        }
    }
    
    free(rowMins);
    free(colMaxs);
    return result;
}

int main() {
    int matrixSize = 3;
    int matrixColSize[] = {4, 4, 4};
    int** matrix = (int**)malloc(matrixSize * sizeof(int*));
    
    int returnSize;
    int* result = solution(matrix, matrixSize, matrixColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Two passes through matrix: first to compute row/column min/max, second to find lucky numbers

✓ Linear Growth

Space Complexity

O(m+n)

Arrays to store row minimums (size m) and column maximums (size n)

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Precompute Row Min & Column Max — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler