Search in Matrix
Java coding interview problem for Matrix Problems: Search in Matrix.
Searching an element in a matrix is one of the most common matrix problems in coding interviews.
Unlike searching in a normal array, a matrix provides additional structure:
- Rows may be sorted.
- Columns may be sorted.
- The entire matrix may be sorted.
Understanding this structure allows us to optimize from:
O(m × n)
to:
O(log(m × n))
or:
O(m + n)
What is Searching in a Matrix?
Given a matrix and a target value, determine whether the target exists in the matrix.
Example:
Matrix:
1 3 5 7
10 11 16 20
23 30 34 60
Target:
16
Output:
Found
Understanding Matrix Search Problems
Matrix search problems are divided into different categories.
Type 1 — Unsorted Matrix
Example:
5 2 9
1 8 3
7 4 6
No ordering exists.
Only option:
Linear Search
Time:
O(m × n)
Type 2 — Row Sorted Matrix
Example:
1 4 7
2 5 8
3 6 9
Each row is sorted.
We can apply:
Binary Search on each row
Type 3 — Row and Column Sorted Matrix
Example:
1 4 7
2 5 8
3 6 9
Rows:
Left → Right increasing
Columns:
Top → Bottom increasing
Use:
Staircase Search
Type 4 — Fully Sorted Matrix
Example:
1 3 5
7 9 11
13 15 17
If viewed as a single array:
[1,3,5,7,9,11,13,15,17]
Use:
Binary Search
Why Is Matrix Search Asked in Interviews?
This problem tests:
1. Understanding Data Structure Properties
Can you identify:
sorted rows
sorted columns
fully sorted matrix
?
2. Algorithm Selection
Choosing the correct approach:
Linear Search
Binary Search
Staircase Search
3. Index Conversion
Can you convert:
1D index
into
2D coordinates
?
4. Optimization Skills
Can you reduce:
O(m × n)
to:
O(m+n)
or:
O(log(m×n))
?
Real-World Applications
Database Searching
Tables are often stored in sorted structures.
Searching optimized indexes uses similar concepts.
Image Processing
Pixels can be stored as matrices.
Searching patterns or values requires efficient traversal.
Machine Learning
Feature matrices contain millions of values.
Efficient lookup improves processing.
Spreadsheet Applications
Finding values in rows and columns uses matrix search techniques.
Problem Statement
Given an:
m × n matrix
and a target value:
target
return whether the target exists.
Example 1
Input:
matrix =
[
[1,4,7],
[2,5,8],
[3,6,9]
]
target = 6
Output:
true
Example 2
Input:
target = 10
Output:
false
Constraints
Example:
1 <= rows <= 1000
1 <= columns <= 1000
Matrix Visualization
Matrix:
1 4 7
2 5 8
3 6 9
Coordinates:
[0][0] [0][1] [0][2]
[1][0] [1][1] [1][2]
[2][0] [2][1] [2][2]
Approach 1 — Brute Force Search
The simplest solution:
Visit every cell and compare with target.
Algorithm
For every:
matrix[i][j]
Check:
matrix[i][j] == target
If found:
return true
Otherwise:
return false
Java Program
public class MatrixSearchBruteForce {
public static boolean search(
int[][] matrix,
int target) {
for (int i = 0;
i < matrix.length;
i++) {
for (int j = 0;
j < matrix[i].length;
j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
int[][] matrix =
{
{1,4,7},
{2,5,8},
{3,6,9}
};
System.out.println(
search(matrix,6));
}
}
Output
true
Step-by-Step Explanation
Input:
1 4 7
2 5 8
3 6 9
Target:
6
Check:
1
No.
Check:
4
No.
Continue:
3
6
Found.
Return:
true
Complexity Analysis
Every element may be visited.
For:
m × n
matrix:
Time:
O(m × n)
Space:
O(1)
Advantages
- Simple.
- Works for any matrix.
- No assumptions required.
Drawbacks
- Slow for large matrices.
- Does not use sorted properties.
Approach 2 — Binary Search on Each Row
If every row is sorted:
Example:
1 3 5 7
10 11 16 20
23 30 34 60
Search each row using binary search.
Algorithm
For every row:
- Apply binary search.
- If found, return true.
- Otherwise continue.
Binary Search Example
Row:
10 11 16 20
Target:
16
Middle:
11
Target greater.
Search right side:
16 20
Found.
Java Program
public class MatrixSearchRowBinary {
public static boolean search(
int[][] matrix,
int target) {
for (int[] row : matrix) {
int left = 0;
int right = row.length - 1;
while(left <= right) {
int mid =
left +
(right-left)/2;
if(row[mid] == target) {
return true;
}
else if(row[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return false;
}
}
Complexity Analysis
Number of rows:
m
Binary search per row:
log n
Total:
O(m log n)
Space:
O(1)
Advantages
- Faster than brute force.
- Uses sorted rows.
- Easy to implement.
Drawbacks
- Does not use column ordering.
- Not optimal for row + column sorted matrices.
Approach 3 — Staircase Search (Optimal for Row and Column Sorted Matrix)
The Staircase Search algorithm is the most efficient approach when:
- Every row is sorted left to right.
- Every column is sorted top to bottom.
Example:
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
Core Idea
Start from:
Top Right Corner
Why?
Because this position gives two possible decisions:
Current value > target
Move Left
Current value < target
Move Down
Algorithm
Start:
row = 0
column = number of columns - 1
Repeat:
Case 1
If:
matrix[row][column] == target
Return:
true
Case 2
If:
matrix[row][column] > target
Move left:
column--
Because all values below are larger.
Case 3
If:
matrix[row][column] < target
Move down:
row++
Because all values on the left are smaller.
Example Dry Run
Matrix:
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
Target:
9
Start:
row = 0
column = 3
Position:
11
Compare:
11 > 9
Move left.
Position:
7
Compare:
7 < 9
Move down.
Position:
8
Compare:
8 < 9
Move down.
Position:
9
Found.
Java Program — Staircase Search
public class MatrixStaircaseSearch {
public static boolean search(
int[][] matrix,
int target) {
if(matrix.length == 0) {
return false;
}
int row = 0;
int column =
matrix[0].length - 1;
while(row < matrix.length &&
column >= 0) {
int current =
matrix[row][column];
if(current == target) {
return true;
}
else if(current > target) {
column--;
}
else {
row++;
}
}
return false;
}
public static void main(String[] args) {
int[][] matrix =
{
{1,4,7,11},
{2,5,8,12},
{3,6,9,16},
{10,13,14,17}
};
System.out.println(
search(matrix,9));
}
}
Output
true
Step-by-Step Explanation
Matrix:
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
Target:
9
Start:
11
Since:
11 > 9
Move:
Left
Now:
7
Since:
7 < 9
Move:
Down
Now:
8
Since:
8 < 9
Move:
Down
Now:
9
Found.
Complexity Analysis
For an:
m × n
matrix:
Maximum movements:
m + n
because:
- Row only increases.
- Column only decreases.
Time:
O(m + n)
Space:
O(1)
Advantages
- Optimal for row and column sorted matrices.
- No extra memory.
- Very simple decision process.
- Faster than searching every row.
Drawbacks
- Requires sorted rows and columns.
- Cannot be used on random matrices.
Approach 4 — Binary Search in Fully Sorted Matrix
Some problems provide a matrix where:
- Each row is sorted.
- First element of every row is greater than the last element of previous row.
Example:
1 3 5 7
10 11 16 20
23 30 34 60
This matrix can be treated as a sorted one-dimensional array.
Flattened View
Matrix:
1 3 5 7
10 11 16 20
23 30 34 60
Becomes:
[1,3,5,7,10,11,16,20,23,30,34,60]
Index Mapping
For a matrix:
columns = n
Convert:
1D index → 2D index
Row:
index / columns
Column:
index % columns
Example:
Index:
6
Columns:
4
Row:
6 / 4 = 1
Column:
6 % 4 = 2
Position:
matrix[1][2]
Value:
16
Java Program
public class MatrixBinarySearch {
public static boolean search(
int[][] matrix,
int target) {
int rows =
matrix.length;
int cols =
matrix[0].length;
int left = 0;
int right =
rows * cols - 1;
while(left <= right) {
int mid =
left +
(right - left) / 2;
int value =
matrix[mid / cols]
[mid % cols];
if(value == target) {
return true;
}
else if(value < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return false;
}
}
Complexity Analysis
Binary search:
log(m × n)
Time:
O(log(m × n))
Space:
O(1)
Comparison of All Approaches
| Approach | Matrix Requirement | Time | Space |
|---|---|---|---|
| Brute Force | Any matrix | O(m×n) | O(1) |
| Binary Search Each Row | Rows sorted | O(m log n) | O(1) |
| Staircase Search | Rows + columns sorted | O(m+n) | O(1) |
| Flattened Binary Search | Fully sorted matrix | O(log(m×n)) | O(1) |
Java Streams Approach
Matrix searching is not a good fit for Streams.
Example:
Arrays.stream(matrix)
creates additional complexity because:
- Nested arrays need flattening.
- Index tracking becomes difficult.
- Early exit is harder.
Traditional loops are preferred.
Primitive vs Object Arrays
Primitive Matrix
Example:
int[][]
Advantages:
- Faster access.
- Less memory.
- Better performance.
Recommended for:
- Large matrices.
- Competitive programming.
Object Matrix
Example:
Integer[][]
Advantages:
- Works with collections.
- Supports null values.
Disadvantages:
- More memory usage.
Common Interview Mistakes
Mistake 1
Using staircase search without checking sorting conditions.
Mistake 2
Starting from the wrong corner.
Correct:
Top Right
or:
Bottom Left
Mistake 3
Confusing matrix types.
A row-sorted matrix is different from a fully sorted matrix.
Mistake 4
Wrong index conversion in flattened binary search.
Correct:
row = index / columns
column = index % columns
Edge Cases
| Input | Result |
|---|---|
| Empty matrix | false |
| Single element found | true |
| Single row matrix | works |
| Single column matrix | works |
| Target missing | false |
| Duplicate values | works |
Interview Follow-up Questions
Q1. Search in sorted matrix.
Q2. Search in row and column sorted matrix.
Q3. Find position of target.
Q4. Count occurrences of target.
Q5. Find minimum value in matrix.
Q6. Search matrix with duplicates.
Q7. Find kth smallest element in sorted matrix.
Related Problems
- Search a 2D Matrix
- Kth Smallest Element in Sorted Matrix
- Matrix Median
- Row With Maximum Ones
- Spiral Matrix
- Matrix Rotation
Key Takeaways
Matrix search depends on the matrix structure.
Decision flow:
Unsorted Matrix
|
|
Linear Search
Rows Sorted
|
|
Binary Search Rows
Rows + Columns Sorted
|
|
Staircase Search
Fully Sorted Matrix
|
|
Binary Search
Frequently Asked Interview Questions
Q1. What is staircase search?
A search technique that starts from the top-right corner and eliminates one row or column at every step.
Q2. Why start from top-right?
Because:
- Moving left decreases values.
- Moving down increases values.
Q3. Complexity of staircase search?
O(m+n)
Q4. Can binary search be applied to all matrices?
No.
Only when the matrix has required ordering.
Interview Tip
When asked:
"Search an element in matrix."
First identify the matrix property:
- Is it sorted?
- Are rows sorted?
- Are rows and columns sorted?
- Is the entire matrix sorted?
Then choose:
Any Matrix:
Brute Force
Row Sorted:
Binary Search
Row + Column Sorted:
Staircase Search
Fully Sorted:
Binary Search
This demonstrates strong understanding of matrix properties and algorithm optimization.