Lucky Numbers in a Matrix

📋

Problem

Imagine you are analyzing a grid of numbers representing a game board, and you want to find special numbers that are the smallest in their row but the largest in their column - these are the 'lucky numbers' that stand out uniquely.

Given an m x n matrix of distinct integers, 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 the maximum in its column.

m == matrix.lengthn == matrix[i].length1 ≤ m, n ≤ 501 ≤ matrix[i][j] ≤ 10^5All elements in the matrix are distinct.

Edge cases: Matrix with only one element → that element is luckyMatrix where no element satisfies both conditions → empty outputMatrix with multiple lucky numbers → all should be returned

</>

IDE

def luckyNumbers(matrix: list[list[int]]) -> list[int]:public List<Integer> luckyNumbers(int[][] matrix)vector<int> luckyNumbers(vector<vector<int>>& matrix)function luckyNumbers(matrix)

def luckyNumbers(matrix):
    # Write your solution here
    pass

class Solution {
    public List<Integer> luckyNumbers(int[][] matrix) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> luckyNumbers(vector<vector<int>>& matrix) {
    // Write your solution here
    return {};
}

function luckyNumbers(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [9]Selecting maximum in row instead of minimum for lucky number condition.✅ Change row check to find minimum element (val <= all row elements), not maximum.

Wrong: [15, 16]Incorrectly including elements that are minimum in row but not maximum in column.✅ Add strict check that element is also maximum in its column (val >= all column elements).

Wrong: [42]Failing to handle single element matrix correctly or returning empty list incorrectly.✅ Ensure single element matrix returns that element as lucky number.

Wrong: [7]Off-by-one error in indexing rows or columns causing missed lucky numbers.✅ Carefully index matrix[i][j] and verify comparisons for row and column.

Wrong: Timeout or no outputUsing brute force O(m*n*(m+n)) approach causing TLE on large inputs.✅ Precompute row minimums and column maximums to achieve O(m*n) time complexity.

✓

Test Cases

Try testing your solution on smallest and no-solution cases to ensure robustness.

Consider tricky inputs that might cause greedy or indexing errors.

Focus on optimizing your solution to run efficiently on large inputs.

t1_01basic

Input{"matrix":[[3,7,8],[9,11,13],[15,16,17]]}

Expected[15]

⏱ Performance - must finish in 2000ms

15 is the minimum in its row (third row) and maximum in its column (first column).

💡 Check each element if it is the smallest in its row and largest in its column.

💡 Precompute row minimums and column maximums to optimize checks.

💡 Return all elements that satisfy both conditions as lucky numbers.

Why it failed: Failed to identify the lucky number 15; likely incorrect row minimum or column maximum check. Fix by ensuring you check val <= all row elements and val >= all column elements.

✓ Correctly identified the lucky number 15.

t1_02basic

Input{"matrix":[[1,10,4,2],[9,3,8,7],[15,16,17,12]]}

Expected[12]

⏱ Performance - must finish in 2000ms

12 is the minimum in its row (third row) and maximum in its column (fourth column).

💡 Remember to check both row minimum and column maximum conditions for each element.

💡 Use separate arrays to store row minimums and column maximums for efficiency.

💡 Return all elements that are row minimum and column maximum as lucky numbers.

Why it failed: Returned incorrect lucky numbers or missed 12; likely failed to check column maximum correctly. Fix by verifying val >= all elements in its column.

✓ Correctly identified the lucky number 12.

t2_01edge

Input{"matrix":[[42]]}

Expected[42]

⏱ Performance - must finish in 2000ms

Single element matrix; that element is trivially the minimum in its row and maximum in its column.

💡 Consider the smallest possible matrix size: 1x1.

💡 A single element is always a lucky number since it's the only element in its row and column.

💡 Return the single element as the lucky number.

Why it failed: Failed single element case; likely missing base case for 1x1 matrix. Fix by handling single element matrices explicitly or ensuring general logic covers it.

✓ Correctly handled single element matrix.

t2_02edge

Input{"matrix":[[5,7],[8,6]]}

Expected[]

⏱ Performance - must finish in 2000ms

No element is both minimum in its row and maximum in its column; result is empty.

💡 Test cases where no lucky numbers exist.

💡 Ensure your code returns an empty list if no elements satisfy both conditions.

💡 Check that you do not return any false positives.

Why it failed: Returned non-empty list when no lucky numbers exist; fix by verifying both conditions strictly before adding elements.

✓ Correctly returned empty list when no lucky numbers.

t2_03edge

Input{"matrix":[[1,2,3],[4,5,6],[7,8,9]]}

Expected[7]

⏱ Performance - must finish in 2000ms

7 is the minimum in its row (third row) and maximum in its column (first column).

💡 Check exact boundary conditions where minimum equals maximum in respective row and column.

💡 Verify that your comparisons use <= and >= correctly, not just < or >.

💡 Return all elements that meet the exact equality conditions.

Why it failed: Missed lucky number 7 due to strict inequality checks; fix by using <= for row minimum and >= for column maximum.

✓ Correctly identified lucky number at exact boundary.

t3_01corner

Input{"matrix":[[10,10,10],[10,10,10],[10,10,10]]}

Expected[]

⏱ Performance - must finish in 2000ms

All elements identical but distinctness violated; no lucky numbers since all elements are equal and distinctness is required.

💡 Check problem constraint that all elements are distinct.

💡 If input violates distinctness, your code should still handle gracefully.

💡 Return empty list if no element satisfies lucky number conditions.

Why it failed: Returned lucky numbers despite identical elements violating distinctness; fix by ensuring input validation or logic handles duplicates correctly.

✓ Handled identical elements input gracefully with empty output.

t3_02corner

Input{"matrix":[[5,1,4],[3,2,6],[7,8,9]]}

Expected[5]

⏱ Performance - must finish in 2000ms

5 is minimum in first row and maximum in first column; tests greedy trap of picking max in row instead of min.

💡 Beware of greedy mistakes: do not pick max in row, must pick minimum in row.

💡 Check both conditions independently for each element.

💡 Return elements that are minimum in row and maximum in column.

Why it failed: Returned 9 or other max in row instead of 5; fix by selecting minimum in row, not maximum.

✓ Correctly avoided greedy trap and identified lucky number 5.

t3_03corner

Input{"matrix":[[1,2,3],[4,5,6],[7,8,9]]}

Expected[7]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in indexing rows and columns; 7 is minimum in row 3 and maximum in column 1.

💡 Double-check indexing when comparing rows and columns.

💡 Ensure you compare the correct elements for row minimum and column maximum.

💡 Return all elements that satisfy both conditions.

Why it failed: Missed 7 due to off-by-one indexing errors; fix by carefully indexing matrix[i][j] in loops.

✓ Correctly handled indexing and found lucky number 7.

t4_01performance

Input{"_description":"n=50 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix size m=n=50; O(m*n) solution must complete within 2 seconds.

💡 Optimize by precomputing row minimums and column maximums.

💡 Avoid nested loops checking each element against entire row and column repeatedly.

💡 Use O(m*n) time and O(m+n) space approach for efficiency.

Why it failed: TLE due to O(m*n*(m+n)) brute force complexity; fix by precomputing row minimums and column maximums.

✓ Efficient O(m*n) solution confirmed by passing performance test.

Practice

1. Consider the following Python function that counts negative numbers in a sorted matrix. What is the returned value when the input matrix is [[3, 1, -1], [2, 0, -2], [1, -1, -3]]?

def countNegatives(grid):
    m, n = len(grid), len(grid[0])
    count = 0
    row, col = 0, n - 1
    while row < m and col >= 0:
        if grid[row][col] < 0:
            count += m - row
            col -= 1
        else:
            row += 1
    return count

easy

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Trace first iteration

   Start at (0,2): grid[0][2] = -1 < 0, count += 3 - 0 = 3, col = 1

2. Step 2: Trace subsequent iterations

   At (0,1): 1 >= 0, row = 1; At (1,1): 0 >= 0, row = 2; At (2,1): -1 < 0, count += 3 - 2 = 1, col = 0; At (2,0): 1 >= 0, row = 3 (end)

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counted negatives: 3 + 1 + 2 (from last col) = 6 [OK]

Hint: Count increments by rows below current on negative found [OK]

Common Mistakes:

• Off-by-one in counting rows below
• Incrementing row or col incorrectly
• Misreading matrix indices

2. You need to fill an n x n matrix with numbers from 1 to n² in a pattern that starts at the top-left corner and proceeds in a clockwise spiral moving outward. Which approach guarantees filling all cells correctly without revisiting or skipping any cell?

easy

A. Greedy approach filling rows and columns independently without tracking boundaries

B. Dynamic programming to store partial sums and fill matrix based on subproblems

C. Directional simulation with boundary shrinking and cycling through directions

D. Sorting all numbers and placing them diagonally from top-left to bottom-right

Solution

1. Step 1: Understand the problem constraints

   The matrix must be filled in a spiral order, visiting each cell exactly once in a clockwise manner.

2. Step 2: Identify the approach that tracks boundaries and direction

   Directional simulation with boundary shrinking ensures that after filling one side, boundaries are updated to avoid revisiting cells, and directions cycle through right, down, left, and up correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary shrinking prevents overwriting and ensures full coverage [OK]

Hint: Track boundaries and directions to avoid revisits [OK]

Common Mistakes:

• Assuming greedy row/column fills without boundary checks works
• Confusing DP with spiral traversal
• Ignoring direction cycling leads to incomplete fills

3. You are given a 2D matrix and asked to output all elements starting from the outermost layer and moving inward in a clockwise manner, visiting each element exactly once. Which algorithmic approach best guarantees an efficient and correct solution for this problem?

easy

A. Perform a depth-first search (DFS) starting from the top-left corner, marking visited cells to avoid repeats.

B. Use a greedy approach that picks the next available element in clockwise order without tracking boundaries.

C. Apply dynamic programming to store intermediate traversal states and build the spiral order iteratively.

D. Simulate the traversal by shrinking the boundaries inward after completing each outer layer, ensuring no element is revisited.

Solution

1. Step 1: Understand the problem constraints

   The problem requires visiting all elements in a matrix in a spiral order without repetition, moving layer by layer inward.

2. Step 2: Identify the approach that guarantees correctness and efficiency

   Simulating the traversal by shrinking boundaries after completing each layer ensures no element is revisited and the traversal is orderly and complete.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary shrinking matches the spiral traversal pattern perfectly [OK]

Hint: Boundary shrinking ensures no repeats and full coverage [OK]

Common Mistakes:

• Greedy approach misses boundary checks causing repeats
• DFS can revisit or miss elements without careful visited tracking
• DP is not suitable for traversal order problems

4. Suppose you want to extend diagonal traversal to handle matrices where elements can be updated dynamically and you need to output the diagonal traversal multiple times efficiently. Which modification to the algorithm is most appropriate?

hard

A. Precompute and store all diagonals in separate lists to allow O(1) retrieval per traversal.

B. Use the original traversal code each time since it is already optimal with O(m*n) time.

C. Flatten the matrix into a 1D array and sort it to simulate diagonal traversal.

D. Maintain a segment tree per diagonal to support dynamic updates and queries efficiently.

Solution

1. Step 1: Understand the requirement for dynamic updates

   Repeated diagonal traversals with updates require efficient update and query support.

2. Step 2: Evaluate options for dynamic support

   Precomputing diagonals (A) is fast for static data but inefficient for updates. Original code (B) recomputes fully each time. Flattening and sorting (D) loses diagonal order and is inefficient.

3. Step 3: Use segment trees per diagonal

   Segment trees allow efficient updates and queries on each diagonal, enabling fast repeated traversals.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Segment trees balance update and query efficiency for dynamic diagonal traversal [OK]

Hint: Dynamic updates require data structures supporting fast queries [OK]

Common Mistakes:

• Assuming original code is always optimal for dynamic queries

5. Suppose you need to transpose a non-square matrix (m x n) in-place, but the matrix is stored as a flat array in row-major order. Which approach correctly handles this scenario?

hard

A. Transpose in-place by swapping elements only in the upper triangle of the matrix.

B. Use the same in-place swapping approach as for square matrices, swapping elements symmetrically across the diagonal.

C. Create a new matrix of size n x m and copy elements accordingly, since in-place transpose is not possible for non-square matrices.

D. Use a recursive approach to swap elements in cycles to achieve in-place transpose.

Solution

1. Step 1: Understand matrix shape constraints

   In-place transpose by swapping only works for square matrices because indices map symmetrically.

2. Step 2: For non-square matrices, in-place transpose is not possible

   Because the shape changes from m x n to n x m, a new matrix must be created to hold the transposed data.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Non-square matrix transpose requires extra space due to dimension change [OK]

Hint: In-place transpose only works for square matrices [OK]

Common Mistakes:

• Trying to swap elements in-place for non-square matrices
• Assuming upper triangle swaps apply to rectangular matrices
• Ignoring dimension changes after transpose