Practice
1. You are given a matrix of integers. You need to find all elements that are the smallest in their row and simultaneously the largest in their column. Which approach guarantees an optimal solution to this problem?
easy
Solution
Step 1: Understand problem constraints
The problem requires identifying elements that are simultaneously the minimum in their row and maximum in their column.Step 2: Evaluate approaches
Brute force (A) is correct but inefficient. DP (C) is unnecessary overhead. Greedy (D) can fail if multiple minimums exist in a row but only one is maximum in its column. Precomputing row minimums and column maximums (B) allows a single pass to find all lucky numbers efficiently.Final Answer:
Option B -> Option BQuick Check:
Precompute arrays then single pass -> optimal and correct [OK]
Hint: Precompute mins and maxes for single pass [OK]
Common Mistakes:
- Assuming greedy selection per row suffices
- Using DP unnecessarily
- Brute force is too slow
2. Consider the following Python code for finding lucky numbers in a matrix:
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]]
mat = [[3,7,8],[9,11,13],[15,16,17]]
print(luckyNumbers(mat))
easy
Solution
Step 1: Compute row minimums
Row 0 min = 3, Row 1 min = 9, Row 2 min = 15.Step 2: Compute column maximums
Col 0 max = max(3,9,15) = 15, Col 1 max = max(7,11,16) = 16, Col 2 max = max(8,13,17) = 17.Step 3: Find elements equal to both row min and column max
Check each element: - (2,0) = 15 equals row 2 min and col 0 max -> lucky number. No other elements satisfy both conditions.Final Answer:
Option A -> Option AQuick Check:
Only 15 matches both conditions -> output [15] [OK]
Hint: Check row mins and col maxs carefully [OK]
Common Mistakes:
- Confusing min and max
- Off-by-one indexing
- Returning all row mins or col maxs
3. You are given a square matrix and asked to transform it so that rows become columns and columns become rows without using extra space. Which approach guarantees an optimal in-place solution?
easy
Solution
Step 1: Understand the problem constraints
The problem requires an in-place transpose of a square matrix, meaning no extra matrix can be used.Step 2: Identify the correct approach
Swapping elements symmetrically across the diagonal once (upper triangle only) ensures each pair is swapped exactly once, achieving in-place transpose efficiently.Final Answer:
Option B -> Option BQuick Check:
Swapping only upper triangle elements avoids double swaps and extra space [OK]
Hint: Swap only upper triangle elements once [OK]
Common Mistakes:
- Using extra space unnecessarily
- Swapping elements twice by iterating entire matrix
- Ignoring diagonal symmetry leading to incorrect results
4. What is the time complexity of the optimal staircase search algorithm for counting negative numbers in an m x n sorted matrix, and why?
medium
Solution
Step 1: Analyze movement in matrix
The algorithm starts at top-right and moves left or down, never revisiting cells.Step 2: Count maximum moves
Maximum moves down = m, maximum moves left = n, total moves ≤ m + n.Final Answer:
Option D -> Option DQuick Check:
Linear traversal along edges, not full matrix scan [OK]
Hint: Moves only left or down once per step, total ≤ m+n [OK]
Common Mistakes:
- Confusing with brute force O(m*n)
- Assuming binary search per row
- Ignoring that each cell is visited once
5. Suppose the matrix is no longer sorted row-wise or column-wise but only each row is sorted independently. Which approach correctly counts negative numbers efficiently in this scenario?
hard
Solution
Step 1: Analyze sorting constraints
Only rows are sorted, columns are not, so staircase search relying on column sorting fails.Step 2: Choose correct approach
Binary search per row finds first negative efficiently in O(log n), total O(m log n), better than brute force.Final Answer:
Option C -> Option CQuick Check:
Row-wise binary search exploits partial sorting [OK]
Hint: When only rows sorted, binary search per row is optimal [OK]
Common Mistakes:
- Trying staircase search without column sorting
- Using brute force ignoring partial sorting
- Assuming DP is needed