Lucky Numbers in a Matrix

🎯

Lucky Numbers in a Matrix

easyMATRIXAmazonGoogle

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.

💡 This problem is about understanding how to find elements in a matrix that satisfy two conditions simultaneously: being the minimum in their row and maximum in their column. Beginners often struggle because they try to check both conditions for every element naively, missing the opportunity to optimize by precomputing row minimums and column maximums.

📋

Problem Statement

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.

💡

Example

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

Output[15]

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

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

Output[12]

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

Input"[[7,8],[1,2]]"

Output[7]

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

• Matrix with only one element → that element is lucky
• Matrix where no element satisfies both conditions → empty output
• Matrix with multiple lucky numbers → all should be returned
• Matrix with minimum and maximum values at corners → verify correct identification

⚠️

Common Mistakes

Checking only row minimum or only column maximum

Incorrectly identifies elements that are not lucky numbers

✅ Ensure both conditions are checked simultaneously

Not handling empty matrix or single-element matrix

Runtime errors or incorrect output

✅ Add checks for matrix size and handle edge cases explicitly

Using nested loops without precomputation leading to timeouts

Solution is too slow for larger inputs

✅ Precompute row minimums and column maximums to optimize

Confusing minimum and maximum conditions

Wrong elements identified as lucky numbers

✅ Remember lucky number is minimum in row AND maximum in column

🧠

Brute Force (Check Each Element)

💡 This approach exists to build intuition by directly checking the lucky number condition for every element. It is simple but inefficient, helping beginners understand the problem's core before optimizing.

Intuition

For each element, check if it is the minimum in its row and maximum in its column by scanning the entire row and column.

Algorithm

1. For each element in the matrix:
2. Check if it is the minimum in its row by scanning all elements in that row.
3. Check if it is the maximum in its column by scanning all elements in that column.
4. If both conditions hold, add the element to the result list.

💡 The nested loops and repeated scanning make it hard to see efficiency, but it directly implements the problem definition.

</>

Code

from typing import List

def luckyNumbers(matrix: List[List[int]]) -> List[int]:
    m, n = len(matrix), len(matrix[0])
    result = []
    for i in range(m):
        for j in range(n):
            val = matrix[i][j]
            # Check row minimum
            if all(val <= matrix[i][k] for k in range(n)):
                # Check column maximum
                if all(val >= matrix[r][j] for r in range(m)):
                    result.append(val)
    return result

# Driver code
if __name__ == '__main__':
    mat = [[3,7,8],[9,11,13],[15,16,17]]
    print(luckyNumbers(mat))  # Output: [15]

Line Notes

m, n = len(matrix), len(matrix[0])Determine matrix dimensions for iteration limits

for i in range(m):Iterate over each row to check elements

if all(val <= matrix[i][k] for k in range(n))Verify val is minimum in its row by comparing with all row elements

if all(val >= matrix[r][j] for r in range(m))Verify val is maximum in its column by comparing with all column elements

import java.util.*;

public class LuckyNumbers {
    public static List<Integer> luckyNumbers (int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = matrix[i][j];
                boolean rowMin = true;
                for (int k = 0; k < n; k++) {
                    if (matrix[i][k] < val) {
                        rowMin = false;
                        break;
                    }
                }
                if (!rowMin) continue;
                boolean colMax = true;
                for (int r = 0; r < m; r++) {
                    if (matrix[r][j] > val) {
                        colMax = false;
                        break;
                    }
                }
                if (colMax) result.add(val);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] mat = {{3,7,8},{9,11,13},{15,16,17}};
        System.out.println(luckyNumbers(mat)); // Output: [15]
    }
}

Line Notes

int m = matrix.length, n = matrix[0].length;Get matrix dimensions for loops

for (int i = 0; i < m; i++)Outer loop over rows

if (matrix[i][k] < val)Check if any element in row is smaller than val

if (matrix[r][j] > val)Check if any element in column is greater than val

#include <iostream>
#include <vector>
using namespace std;

vector<int> luckyNumbers(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<int> result;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int val = matrix[i][j];
            bool rowMin = true;
            for (int k = 0; k < n; k++) {
                if (matrix[i][k] < val) {
                    rowMin = false;
                    break;
                }
            }
            if (!rowMin) continue;
            bool colMax = true;
            for (int r = 0; r < m; r++) {
                if (matrix[r][j] > val) {
                    colMax = false;
                    break;
                }
            }
            if (colMax) result.push_back(val);
        }
    }
    return result;
}

int main() {
    vector<vector<int>> mat = {{3,7,8},{9,11,13},{15,16,17}};
    vector<int> res = luckyNumbers(mat);
    for (int num : res) cout << num << " ";
    cout << endl; // Output: 15
    return 0;
}

Line Notes

int m = matrix.size(), n = matrix[0].size();Determine matrix dimensions for iteration

for (int i = 0; i < m; i++)Loop over each row

if (matrix[i][k] < val)Check if val is not minimum in row

if (matrix[r][j] > val)Check if val is not maximum in column

function luckyNumbers(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const result = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const val = matrix[i][j];
            let rowMin = true;
            for (let k = 0; k < n; k++) {
                if (matrix[i][k] < val) {
                    rowMin = false;
                    break;
                }
            }
            if (!rowMin) continue;
            let colMax = true;
            for (let r = 0; r < m; r++) {
                if (matrix[r][j] > val) {
                    colMax = false;
                    break;
                }
            }
            if (colMax) result.push(val);
        }
    }
    return result;
}

// Test
const mat = [[3,7,8],[9,11,13],[15,16,17]];
console.log(luckyNumbers(mat)); // Output: [15]

Line Notes

const m = matrix.length, n = matrix[0].length;Get matrix dimensions for loops

for (let i = 0; i < m; i++)Iterate over rows

if (matrix[i][k] < val)Check if val is minimum in row

if (matrix[r][j] > val)Check if val is maximum in column

⏱

Complexity

TimeO(m * n * (m + n))

SpaceO(1)

For each of the m*n elements, we scan its entire row (n elements) and column (m elements), resulting in O(m*n*(m+n)) time.

💡 For a 50x50 matrix, this means up to 50*50*(50+50) = 250,000 operations, which is slow but still manageable for small inputs.

Interview Verdict: Accepted but inefficient

This approach works correctly but is too slow for larger inputs, so we need to optimize.

🧠

Precompute Row Minimums and Column Maximums

💡 This approach improves efficiency by precomputing the minimum value in each row and the maximum value in each column, avoiding repeated scanning.

Intuition

If we know the minimum of each row and maximum of each column, a lucky number must be an element equal to both its row minimum and column maximum.

Algorithm

1. Compute an array of minimum values for each row.
2. Compute an array of maximum values for each column.
3. Iterate over the matrix and collect elements that equal both their row minimum and column maximum.

💡 Precomputing reduces repeated work, making the solution more efficient and easier to understand.

</>

Code

from typing import List

def luckyNumbers(matrix: List[List[int]]) -> List[int]:
    m, n = len(matrix), len(matrix[0])
    row_mins = [min(row) for row in matrix]
    col_maxs = [max(matrix[i][j] for i in range(m)) for j in range(n)]
    result = []
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == row_mins[i] and matrix[i][j] == col_maxs[j]:
                result.append(matrix[i][j])
    return result

# Driver code
if __name__ == '__main__':
    mat = [[3,7,8],[9,11,13],[15,16,17]]
    print(luckyNumbers(mat))  # Output: [15]

Line Notes

row_mins = [min(row) for row in matrix]Precompute minimum of each row once

col_maxs = [max(matrix[i][j] for i in range(m)) for j in range(n)]Precompute maximum of each column once

for i in range(m):Iterate over rows to check candidates

if matrix[i][j] == row_mins[i] and matrix[i][j] == col_maxs[j]Check if element matches both conditions

import java.util.*;

public class LuckyNumbers {
    public static List<Integer> luckyNumbers(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] rowMins = new int[m];
        int[] colMaxs = new int[n];
        Arrays.fill(rowMins, Integer.MAX_VALUE);
        Arrays.fill(colMaxs, Integer.MIN_VALUE);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowMins[i] = Math.min(rowMins[i], matrix[i][j]);
                colMaxs[j] = Math.max(colMaxs[j], matrix[i][j]);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j]) {
                    result.add(matrix[i][j]);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] mat = {{3,7,8},{9,11,13},{15,16,17}};
        System.out.println(luckyNumbers(mat)); // Output: [15]
    }
}

Line Notes

int[] rowMins = new int[m];Array to store minimums per row

Arrays.fill(rowMins, Integer.MAX_VALUE);Initialize row minimums to max value for comparison

rowMins[i] = Math.min(rowMins[i], matrix[i][j]);Update row minimum while scanning

if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j])Check if element is lucky number

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> luckyNumbers(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<int> rowMins(m, INT_MAX);
    vector<int> colMaxs(n, INT_MIN);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            rowMins[i] = min(rowMins[i], matrix[i][j]);
            colMaxs[j] = max(colMaxs[j], matrix[i][j]);
        }
    }
    vector<int> result;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j]) {
                result.push_back(matrix[i][j]);
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> mat = {{3,7,8},{9,11,13},{15,16,17}};
    vector<int> res = luckyNumbers(mat);
    for (int num : res) cout << num << " ";
    cout << endl; // Output: 15
    return 0;
}

Line Notes

vector<int> rowMins(m, INT_MAX);Initialize row minimums with max int

rowMins[i] = min(rowMins[i], matrix[i][j]);Update minimum for each row element

vector<int> colMaxs(n, INT_MIN);Initialize column maximums with min int

if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j])Check if element is lucky number

function luckyNumbers(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const rowMins = Array(m).fill(Infinity);
    const colMaxs = Array(n).fill(-Infinity);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            rowMins[i] = Math.min(rowMins[i], matrix[i][j]);
            colMaxs[j] = Math.max(colMaxs[j], matrix[i][j]);
        }
    }
    const result = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === rowMins[i] && matrix[i][j] === colMaxs[j]) {
                result.push(matrix[i][j]);
            }
        }
    }
    return result;
}

// Test
const mat = [[3,7,8],[9,11,13],[15,16,17]];
console.log(luckyNumbers(mat)); // Output: [15]

Line Notes

const rowMins = Array(m).fill(Infinity);Initialize row minimums to Infinity for comparison

rowMins[i] = Math.min(rowMins[i], matrix[i][j]);Update row minimum while scanning

const colMaxs = Array(n).fill(-Infinity);Initialize column maximums to -Infinity

if (matrix[i][j] === rowMins[i] && matrix[i][j] === colMaxs[j])Check if element is lucky number

⏱

Complexity

TimeO(m * n)

SpaceO(m + n)

We scan the matrix twice: once to compute row minimums and column maximums, and once to find lucky numbers, resulting in linear time relative to matrix size.

💡 For a 50x50 matrix, this means about 2 * 2500 = 5000 operations, which is efficient and fast.

Interview Verdict: Accepted and efficient

This approach is optimal for the problem constraints and is the recommended solution in interviews.

🧠

Single Pass with Precomputed Arrays

💡 This approach is a slight variation that combines precomputation with a single pass to identify lucky numbers, emphasizing clarity and minimal passes.

Intuition

After precomputing row minimums and column maximums, iterate once through the matrix to collect lucky numbers, avoiding multiple passes.

Algorithm

1. Compute minimum values for each row.
2. Compute maximum values for each column.
3. Iterate once through the matrix and add elements that match both precomputed values.

💡 This approach is similar to the previous but emphasizes a clean single pass for clarity.

</>

Code

from typing import List

def luckyNumbers(matrix: List[List[int]]) -> List[int]:
    m, n = len(matrix), len(matrix[0])
    row_mins = [min(row) for row in matrix]
    col_maxs = [max(matrix[i][j] for i in range(m)) for j in range(n)]
    return [matrix[i][j] for i in range(m) for j in range(n) if matrix[i][j] == row_mins[i] == col_maxs[j]]

# Driver code
if __name__ == '__main__':
    mat = [[3,7,8],[9,11,13],[15,16,17]]
    print(luckyNumbers(mat))  # Output: [15]

Line Notes

row_mins = [min(row) for row in matrix]Precompute minimums for each row

col_maxs = [max(matrix[i][j] for i in range(m)) for j in range(n)]Precompute maximums for each column

return [matrix[i][j] for i in range(m) for j in range(n) if matrix[i][j] == row_mins[i] == col_maxs[j]]Single pass to collect lucky numbers

import java.util.*;

public class LuckyNumbers {
    public static List<Integer> luckyNumbers(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] rowMins = new int[m];
        int[] colMaxs = new int[n];
        Arrays.fill(rowMins, Integer.MAX_VALUE);
        Arrays.fill(colMaxs, Integer.MIN_VALUE);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowMins[i] = Math.min(rowMins[i], matrix[i][j]);
                colMaxs[j] = Math.max(colMaxs[j], matrix[i][j]);
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j]) {
                    result.add(matrix[i][j]);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] mat = {{3,7,8},{9,11,13},{15,16,17}};
        System.out.println(luckyNumbers(mat)); // Output: [15]
    }
}

Line Notes

Arrays.fill(rowMins, Integer.MAX_VALUE);Initialize row minimums

Arrays.fill(colMaxs, Integer.MIN_VALUE);Initialize column maximums

rowMins[i] = Math.min(rowMins[i], matrix[i][j]);Update row minimum

if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j])Check lucky number condition

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> luckyNumbers(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<int> rowMins(m, INT_MAX);
    vector<int> colMaxs(n, INT_MIN);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            rowMins[i] = min(rowMins[i], matrix[i][j]);
            colMaxs[j] = max(colMaxs[j], matrix[i][j]);
        }
    }
    vector<int> result;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j]) {
                result.push_back(matrix[i][j]);
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> mat = {{3,7,8},{9,11,13},{15,16,17}};
    vector<int> res = luckyNumbers(mat);
    for (int num : res) cout << num << " ";
    cout << endl; // Output: 15
    return 0;
}

Line Notes

vector<int> rowMins(m, INT_MAX);Initialize row minimums

vector<int> colMaxs(n, INT_MIN);Initialize column maximums

rowMins[i] = min(rowMins[i], matrix[i][j]);Update row minimum

if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j])Check lucky number condition

function luckyNumbers(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const rowMins = Array(m).fill(Infinity);
    const colMaxs = Array(n).fill(-Infinity);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            rowMins[i] = Math.min(rowMins[i], matrix[i][j]);
            colMaxs[j] = Math.max(colMaxs[j], matrix[i][j]);
        }
    }
    const result = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === rowMins[i] && matrix[i][j] === colMaxs[j]) {
                result.push(matrix[i][j]);
            }
        }
    }
    return result;
}

// Test
const mat = [[3,7,8],[9,11,13],[15,16,17]];
console.log(luckyNumbers(mat)); // Output: [15]

Line Notes

const rowMins = Array(m).fill(Infinity);Initialize row minimums

const colMaxs = Array(n).fill(-Infinity);Initialize column maximums

rowMins[i] = Math.min(rowMins[i], matrix[i][j]);Update row minimum

if (matrix[i][j] === rowMins[i] && matrix[i][j] === colMaxs[j])Check lucky number condition

⏱

Complexity

TimeO(m * n)

SpaceO(m + n)

Same as previous approach, but emphasizes a single pass for clarity.

💡 This approach is clean and efficient, suitable for interviews.

Interview Verdict: Accepted and optimal

This is the recommended approach to implement in interviews for clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 or 3 is best to code because they balance clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m * n * (m + n))	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Precompute Row Minimums and Column Maximums	O(m * n)	O(m + n)	No	N/A	Code this for optimal and clear solution
3. Single Pass with Precomputed Arrays	O(m * n)	O(m + n)	No	N/A	Also optimal; good for clean code and explanation

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally present the optimized solution. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Explain the optimization using precomputed row minimums and column maximums.Step 4: Write clean, efficient code implementing the optimized approach.Step 5: Test your code with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to understand matrix traversal, optimize nested loops, and correctly implement condition checks. They also assess your communication and testing skills.

Common Follow-ups

• What if the matrix contains duplicate elements? → Adjust logic to handle duplicates carefully.
• Can you find lucky numbers without extra space? → Discuss trade-offs and possible in-place methods.

💡 These follow-ups test your adaptability and deeper understanding of the problem constraints.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to find elements that are simultaneously minimum in their row and maximum in their column in a matrix.

Signature Phrases

'minimum element in its row''maximum element in its column''lucky number'

NOT This Pattern When

Problems that require searching for global minimum or maximum without row/column constraints are different.

Similar Problems

Matrix Saddle Point - similar concept of row min and column max intersectionSpecial Positions in a Binary Matrix - finding unique positions with row and column constraints

Practice

1. You are given a square matrix and need to find the sum of all elements on both its main diagonal and secondary diagonal. Which approach guarantees the most optimal time complexity for this problem?

easy

A. Use a single loop to directly access and sum elements at indices (i, i) and (i, n-1-i).

B. Use a brute force nested loop to check every element and sum those on diagonals.

C. Use dynamic programming to store sums of submatrices and combine results.

D. Use a greedy approach to pick the largest elements from diagonals first.

Solution

1. Step 1: Understand the problem constraints

   The problem requires summing elements on the main and secondary diagonals of an n x n matrix.

2. Step 2: Identify the optimal approach

   Using a single loop from 0 to n-1, we can directly access mat[i][i] and mat[i][n-1-i] in O(n) time, avoiding unnecessary checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single loop with direct indexing is O(n) and minimal code [OK]

Hint: Direct indexing avoids nested loops [OK]

Common Mistakes:

• Using nested loops unnecessarily
• Trying DP for a simple sum
• Misapplying greedy selection

2. Consider the following code that transposes a square matrix in-place:

def transpose(matrix):
    n = len(matrix)
    if n == 1:
        return
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose(mat)
print(mat)

What is the value of mat[1][2] after the function call?

easy

A. 8

B. 6

C. 4

D. 5

Solution

1. Step 1: Trace swaps affecting mat[1][2]

   Initially, mat[1][2] = 6. The swap occurs when i=1, j=2 swapping mat[1][2] and mat[2][1]. mat[2][1] is 8.

2. Step 2: After swap, mat[1][2] becomes 8

   Thus, mat[1][2] = 8 after transpose.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping upper triangle elements swaps mat[1][2] with mat[2][1] correctly [OK]

Hint: Trace swaps only in upper triangle [OK]

Common Mistakes:

• Confusing indices i and j during swap
• Off-by-one errors in loops
• Assuming mat[1][2] remains unchanged

3. The following code attempts to rotate an n x n matrix by 90 degrees clockwise in-place. Identify the line containing the subtle bug that causes incorrect rotation.

medium

A. matrix[last][last - offset] = matrix[i][last]

B. matrix[last - offset][first] = matrix[last][last - offset]

C. matrix[i][last] = matrix[i][last]

D. matrix[first][i] = matrix[last - offset][first]

Solution

1. Step 1: Analyze the last assignment

   The last line should assign the saved top value to matrix[i][last], but it assigns matrix[i][last] to itself.

2. Step 2: Identify the fix

   Replace matrix[i][last] = matrix[i][last] with matrix[i][last] = top to complete the four-way swap correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect assignment leaves matrix partially unrotated [OK]

Hint: Last assignment must restore saved top element to complete rotation [OK]

Common Mistakes:

• Forgetting to assign saved top value
• Swapping elements twice causing corruption

4. What is the time complexity of the optimal in-place boundary shrinking approach to generate an n x n spiral matrix, and why?

medium

A. O(n²) because every cell in the matrix is visited exactly once

B. O(n) because each boundary shrinks linearly

C. O(n³) due to nested loops and repeated boundary checks

D. O(n log n) because of direction cycling and boundary updates

Solution

1. Step 1: Identify the number of cells to fill

   The matrix has n² cells, each must be assigned a value exactly once.

2. Step 2: Analyze loops and operations

   Each iteration fills one side of the current boundary, and boundaries shrink inward. The total number of assignments sums to n², so time complexity is O(n²).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Every cell visited once -> O(n²) time [OK]

Hint: Each cell visited once -> O(n²) time [OK]

Common Mistakes:

• Confusing boundary shrinking with linear time
• Assuming nested loops multiply to cubic time
• Ignoring that direction cycling is constant time

5. Suppose the problem changes: you want to find the top 3 maximum hourglass sums in the matrix instead of just the maximum. Which modification to the sliding window approach is correct and efficient?

hard

A. Store all hourglass sums in a list and sort it at the end to pick top 3.

B. Run the sliding window 3 times, each time removing the previously found max hourglass from the matrix.

C. Maintain a min-heap of size 3 to track top sums while sliding through the matrix.

D. Use dynamic programming to store maximum sums for all submatrices and pick top 3.

Solution

1. Step 1: Understand the need to track multiple top sums efficiently

   Storing all sums and sorting is inefficient for large matrices.

2. Step 2: Use a min-heap of fixed size 3

   Insert sums as you compute; if heap size exceeds 3, pop smallest. This keeps top 3 sums efficiently.

3. Step 3: Reject other options

   Sorting all sums (A) is costly; repeated removal (C) is complex and incorrect; DP (D) is unnecessary and inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Min-heap maintains top K sums in O(n*m*logK) time [OK]

Hint: Use min-heap to track top K sums efficiently [OK]

Common Mistakes:

• Sorting all sums after computation
• Repeatedly removing max sums from matrix
• Using DP unnecessarily