Search a 2D Matrix Solution In C++/Java/Python/JS
Problem Description
You are given an m x n integer matrix matrix with the following two properties:
Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
Examples
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4
In this problem, we need to search for a target number in a 2D matrix where each row is sorted, and each first element is greater than the last of the previous row.
Before thinking of an optimized solution, let’s start with a simple brute force approach: check every element one by one to see if it matches the target.
Brute Force Approach
Intuition:
The problem asks us to find whether a given target exists in a matrix where each row is sorted in non-decreasing order, and the first element of each row is greater than the last of the previous row.
The simplest idea that comes to mind is to check every element one by one to see if it matches the target.
How do we do this?
We can use two nested loops:
– The outer loop iterates over each row of the matrix (from index 0 to m - 1).
– The inner loop iterates over each element in the current row (from index 0 to n - 1).
At each cell matrix[i][j], we check:
– If matrix[i][j] == target, we can directly return true.
– If no cell matches the target after checking all elements, we return false.
Although the matrix is sorted, this brute-force method doesn’t use that information; it simply scans every cell directly to find the target.
Approach
Step 1: Initialize the answer variable
Create a Boolean variable found to indicate whether the target is present in the matrix.
Set found = false initially.
Step 2: Loop over each row of the matrix
Use an outer loop where i ranges from 0 to m - 1 (where m is the number of rows).
This loop picks every row of the matrix one by one.
Step 3: Loop over each element of the current row
For each row i, use another loop where j ranges from 0 to n - 1 (where n is the number of columns).
This loop checks every element in that row.
Step 4: Check if the current element equals the target
For each cell matrix[i][j], check:
If matrix[i][j] == target, it means we found the target.
Step 5: Set found to true if target is found
If the condition is true, we can set found to true since we found the target and break.
Step 6: After all loops, return the Boolean found
Finally return found that indicates whether target exists in the matrix or not
Dry Run
Let’s do a detailed dry run of the brute-force approach using nested loops
for the input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
We want to find whether the target 13 exists in the matrix.
Step 1: Understand the matrix
Original matrix:
Row 0 → [1, 3, 5, 7]
Row 1 → [10, 11, 16, 20]
Row 2 → [23, 30, 34, 60]
Number of rows (m) = 3
Number of columns (n) = 4
Initialize found = false → this will store whether we found the target.
Step 2: Use nested loops to check every element
We will:
– Loop over each row index i from 0 to 2
– Inside each row, loop over each column index j from 0 to 3
– For each cell matrix[i][j], check if it equals target.
Iteration-Wise Dry Run
i = 0 (first row: [1, 3, 5, 7])
• j=0: matrix[0][0]=1 → not equal to 13 → found remains false
• j=1: matrix[0][1]=3 → not equal to 13 → found remains false
• j=2: matrix[0][2]=5 → not equal to 13 → found remains false
• j=3: matrix[0][3]=7 → not equal to 13 → found remains false
i = 1 (second row: [10, 11, 16, 20])
• j=0: matrix[1][0]=10 → not equal to 13 → found remains false
• j=1: matrix[1][1]=11 → not equal to 13 → found remains false
• j=2: matrix[1][2]=16 → not equal to 13 → found remains false
• j=3: matrix[1][3]=20 → not equal to 13 → found remains false
i = 2 (third row: [23, 30, 34, 60])
• j=0: matrix[2][0]=23 → not equal to 13 → found remains false
• j=1: matrix[2][1]=30 → not equal to 13 → found remains false
• j=2: matrix[2][2]=34 → not equal to 13 → found remains false
• j=3: matrix[2][3]=60 → not equal to 13 → found remains false
Final Result
After checking all cells, target = 13 is not found → return false.
Code for All Languages
C++
#include <iostream> // For input and output
#include <vector> // For using vector
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(); // Number of rows
int n = matrix[0].size(); // Number of columns
bool found = false; // Step 1: Initialize the answer variable
// Step 2: Loop over each row of the matrix
for (int i = 0; i < m; i++) {
// Step 3: Loop over each element of the current row
for (int j = 0; j < n; j++) {
// Step 4: Check if the current element equals the target
if (matrix[i][j] == target) {
// Step 5: Set found to true if target is found
found = true;
break; // Since we found the target, no need to continue in this row
}
}
// If found, no need to check remaining rows
if (found) {
break;
}
}
// Step 6: After all loops, return the Boolean found
return found;
}
};
int main() {
int m, n, target;
cin >> m >> n >> target; // Input number of rows, columns, and target
vector<vector<int>> matrix(m, vector<int>(n));
// Input the matrix elements
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
Solution sol;
bool result = sol.searchMatrix(matrix, target);
// Output the result
if (result) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
Java
import java.util.*; // For Scanner
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; // Number of rows
int n = matrix[0].length; // Number of columns
boolean found = false; // Step 1: Initialize the answer variable
// Step 2: Loop over each row of the matrix
for (int i = 0; i < m; i++) {
// Step 3: Loop over each element of the current row
for (int j = 0; j < n; j++) {
// Step 4: Check if the current element equals the target
if (matrix[i][j] == target) {
// Step 5: Set found to true if target is found
found = true;
break; // Since we found the target, break out of inner loop
}
}
// If found, break out of outer loop too
if (found) {
break;
}
}
// Step 6: After all loops, return the Boolean found
return found;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Input number of rows, columns, and target
int m = sc.nextInt();
int n = sc.nextInt();
int target = sc.nextInt();
int[][] matrix = new int[m][n];
// Input the matrix elements
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
Solution sol = new Solution();
boolean result = sol.searchMatrix(matrix, target);
// Output the result
System.out.println(result ? "true" : "false");
}
}
Python
from typing import List # For specifying the return type
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# Step 1: Initialize the answer variable
found = False # Create a variable found to indicate whether the target is present in the matrix
# Step 2: Loop over each row of the matrix
for i in range(len(matrix)):
row = matrix[i]
# Step 3: Loop over each element of the current row
for j in range(len(row)):
cell = row[j]
# Step 4: Check if the current element equals the target
if cell == target:
# Step 5: Set found to true if target is found
found = True
break # Break since we found the target
if found:
break # Break outer loop too if target is already found
# Step 6: Return found as the required value
return found # Final answer representing whether the target exists in the matrix
# Driver Code
if __name__ == "__main__":
m = int(input()) # Input the number of rows
n = int(input()) # Input the number of columns
target = int(input()) # Input the target value
matrix = []
for _ in range(m):
row = list(map(int, input().split())) # Input each row as space-separated integers
matrix.append(row)
sol = Solution()
ans = sol.searchMatrix(matrix, target)
print("true" if ans else "false") # Output whether the target exists in the matrix
Javascript
/**
* @param {number[][]} matrix - 2D array representing the matrix of numbers
* @param {number} target - The target number to search for
* @return {boolean} - Whether the target exists in the matrix
*/
var searchMatrix = function(matrix, target) {
// Step 1: Initialize the answer variable
let found = false; // Create a variable found to indicate whether the target is present in the matrix
// Step 2: Loop over each row of the matrix
for (let i = 0; i < matrix.length; i++) {
let row = matrix[i];
// Step 3: Loop over each element of the current row
for (let j = 0; j < row.length; j++) {
let cell = row[j];
// Step 4: Check if the current element equals the target
if (cell === target) {
// Step 5: Set found to true if target is found
found = true;
break; // Break since we found the target
}
}
if (found) {
break; // Break outer loop too if target is already found
}
}
// Step 6: Return found as the required value
return found; // Final answer representing whether the target exists in the matrix
};
// Driver code
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let inputs = [];
let m = 0, n = 0, target = 0, rowCount = 0;
rl.on("line", function(line) {
if (inputs.length === 0) {
m = parseInt(line.trim()); // Input the number of rows
inputs.push(m);
} else if (inputs.length === 1) {
n = parseInt(line.trim()); // Input the number of columns
inputs.push(n);
} else if (inputs.length === 2) {
target = parseInt(line.trim()); // Input the target number
inputs.push(target);
} else {
let row = line.trim().split(' ').map(Number); // Input each row as space-separated integers
inputs.push(row);
rowCount++;
if (rowCount === m) {
let matrix = inputs.slice(3); // Extract the matrix part
let ans = searchMatrix(matrix, target);
console.log(ans ? "true" : "false"); // Output whether the target exists in the matrix
rl.close();
}
}
});
Time Complexity: O(m × n)
Initialization:
– The variable found is initialized to false before starting the loops.
– Time complexity: O(1) (constant time).
Outer Loop Over Rows:
– The outer loop iterates over all m rows in the matrix.
– Time complexity for this loop: O(m).
Inner Loop Over Columns:
– For each row, the inner loop iterates over all n columns (elements in that row).
– Time complexity for each row: O(n).
Checking Each Element:
– Inside the inner loop, we check whether matrix[i][j] == target.
– Time complexity for each check: O(1).
Total:
– For each of the m rows, we do n operations.
– Therefore, the total time complexity becomes:
O(m) × O(n) = O(m × n).
Space Complexity: O(m × n)
Auxiliary Space Complexity:
– Definition: The extra space or temporary space used by the algorithm during its execution, excluding the input data.
– Code Analysis: The algorithm uses only a few variables:
– found to indicate whether the target is present in the matrix.
– Loop variables i, j, and possibly a temporary variable for each cell checked.
– All these variables require constant space regardless of the size of the input.
– Therefore, Auxiliary Space Complexity = O(1).
Total Space Complexity:
– The overall space used by the algorithm includes the input data and the auxiliary space.
– Input Data: The input matrix itself is a 2D array with m rows and n columns, which requires O(m × n) space.
– Auxiliary Space: As analyzed above, this is O(1).
– Combining:
– Total space complexity = O(m × n) + O(1) = O(m × n).
Is the brute force approach efficient?
Given the problem constraints where the matrix dimensions satisfy 1 ≤ m, n ≤ 100, the brute force approach is actually quite practical.
Even though the method checks each cell individually with time complexity O(m × n), the total number of operations becomes at most 100 × 100 = 10,000, which modern computers handle almost instantly.
Since m and n are relatively small, we don’t need to optimize further, and directly looping through every element is clear, easy to implement, and guaranteed to run within time limits.
Therefore, despite sounding inefficient in theory, the brute force solution is perfectly acceptable for this problem’s constraints and works reliably in practice.
We have seen the brute-force solution, which checks each element one by one to find the target. Although correct, it takes O(m × n) time. But since the matrix rows are sorted and each first element is greater than the last of the previous row, can we use these properties to search faster? Let’s see this in the better approach.
Better Approach
Intuition
We are given a grid where each row is sorted in non-decreasing order, and the first integer of each row is greater than the last integer of the previous row.
Let’s first understand what this means. A sorted row means the elements increase as we move left to right.
For example: [10, 11, 16, 20]
In this row:
– All elements are sorted in increasing order.
Because the first element of each row is greater than the last element of the previous row, the entire matrix behaves like one big sorted list from top-left to bottom-right.
Divide the matrix into logical parts
Observation: Since the first element of a row is greater than the last element of the previous row, the target must fall between matrix[i][0] and matrix[i][n - 1] if it exists in row i.
Key Observations
Finding the correct row:
Observation: We don’t need to search every row. We can first check if
target ≥ matrix[i][0] and target ≤ matrix[i][n - 1].
Explanation: If the target falls outside this range, it can’t be in that row because all elements before or after are strictly smaller or larger.
Binary Search inside the row:
Pick any index mid in the row. It will either:
– Match the target
– Be smaller than the target
– Be greater than the target
Case 1: mid element equals target
Example: matrix[i][mid] == target
Conclusion: We immediately return true, since we found the target.
Case 2: mid element is smaller than target
Example: matrix[i][mid] < target
Conclusion: Since the row is sorted in increasing order, the target must be to the right of mid.
We move binary search to the right half: mid + 1 to end.
Case 3: mid element is greater than target
Example: matrix[i][mid] > target
Conclusion: Since the row is sorted, the target must be to the left of mid.
We move binary search to the left half: start to mid - 1.
The key idea:
– Use the matrix structure to narrow down the possible rows.
– Apply binary search within each valid row to check if the target exists.
This avoids checking every cell and also avoids actually flattening the entire matrix.
So, this approach is efficient, clean, and uses the matrix’s properties smartly to search quickly. Isn’t it intuitive?
Approach
Step 1: Initialize the answer variable
Create a Boolean variable found to indicate whether the target is present in the matrix.
Initially set found = false.
Step 2: Loop over each row of the matrix
Use an outer loop i that ranges from 0 to m - 1 (where m is the number of rows).
Step 3: Check if the target could be in the current row
For row i, check if
target ≥ matrix[i][0] and target ≤ matrix[i][n - 1] (where n is the number of columns).
If not, skip to the next row.
Step 4: Apply binary search in the current row
If the target could be in this row, initialize two pointers: start = 0 and end = n - 1.
While start ≤ end, do the following:
Step 5: Compute the middle index
Compute mid = floor((start + end) / 2).
Step 6: Case 1 – If matrix[i][mid] == target
Observation: We found the target in this row.
Conclusion: Set found = true and break out of the loop.
Step 7: Case 2 – If matrix[i][mid] < target
Observation: mid element is smaller than target.
Conclusion: The target must be to the right of mid.
So, move start = mid + 1.
Step 8: Case 3 – If matrix[i][mid] > target
Observation: mid element is greater than target.
Conclusion: The target must be to the left of mid.
So, move end = mid - 1.
Step 9: After binary search, check if found is true
If found, return true immediately because the target exists in the matrix.
Step 10: After checking all rows, return the final answer
If we finish all rows and found is still false, return false to indicate the target does not exist in the matrix.
Let us understand this with a video,
Dry Run
Let’s do a detailed dry run of the binary search approach for the input:
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Number of rows (m) = 3
Number of columns (n) = 4
We need to check each row to see if it could contain the target, then apply binary search.
Initialize found = false → this will indicate whether the target is present.
Row-wise Dry Run
Row 0: [1, 3, 5, 7]
Check if target could be in this row:
target = 13, matrix[0][0] = 1, matrix[0][3] = 7
13 > 7 → target is greater than the last element, so skip this row.
Row 1: [10, 11, 16, 20]
Check if target could be in this row:
target = 13, matrix[1][0] = 10, matrix[1][3] = 20
13 ≥ 10 and 13 ≤ 20 → target could be here.
start = 0, end = 3
Iteration 1:
mid = floor((0+3)/2) = 1
matrix[1][1] = 11 < target
→ mid is smaller than target.
Move start = mid + 1 → start = 2
Iteration 2:
start = 2, end = 3
mid = floor((2+3)/2) = 2
matrix[1][2] = 16 > target
→ mid is greater than target.
Move end = mid - 1 → end = 1
Now start = 2, end = 1 → loop ends.
Did we find the target? No, found remains false.
Row 2: [23, 30, 34, 60]
Check if target could be in this row:
target = 13, matrix[2][0] = 23
13 < 23 → target is less than the first element, so skip this row.
Final Result
After checking all rows, found is still false → return false.
Conclusion: target=13 is not found in the matrix.
Code for All Languages
C++
#include <iostream> // For input and output
#include <vector> // For using vector
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(); // Number of rows
int n = matrix[0].size(); // Number of columns
bool found = false; // Step 1: Initialize the answer variable
// Create a Boolean variable found to indicate whether the target is present in the matrix.
// Initially set found = false.
// Step 2: Loop over each row of the matrix
// Use an outer loop i that ranges from 0 to m - 1 (where m is the number of rows).
for (int i = 0; i < m; i++) {
// Step 3: Check if the target could be in the current row
// For row i, check if target ≥ matrix[i][0] and target ≤ matrix[i][n - 1].
if (target >= matrix[i][0] && target <= matrix[i][n - 1]) {
// Step 4: Apply binary search in the current row
// If the target could be in this row, initialize two pointers: start = 0 and end = n - 1.
int start = 0, end = n - 1;
// While start ≤ end, do the following:
while (start <= end) {
// Step 5: Compute the middle index
// Compute mid = floor((start + end) / 2).
int mid = (start + end) / 2;
// Step 6: Case 1 – If matrix[i][mid] == target
// Observation: We found the target in this row.
// Conclusion: Set found = true and break out of the loop.
if (matrix[i][mid] == target) {
found = true;
break;
}
// Step 7: Case 2 – If matrix[i][mid] < target
// Observation: mid element is smaller than target.
// Conclusion: The target must be to the right of mid.
// So, move start = mid + 1.
else if (matrix[i][mid] < target) {
start = mid + 1;
}
// Step 8: Case 3 – If matrix[i][mid] > target
// Observation: mid element is greater than target.
// Conclusion: The target must be to the left of mid.
// So, move end = mid - 1.
else {
end = mid - 1;
}
}
}
// Step 9: After binary search, check if found is true
// If found, return true immediately because the target exists in the matrix.
if (found) {
return true;
}
}
// Step 10: After checking all rows, return the final answer
// If we finish all rows and found is still false, return false to indicate the target does not exist in the matrix.
return false;
}
};
int main() {
int m, n, target;
cin >> m >> n >> target; // Input number of rows, columns, and target
vector<vector<int>> matrix(m, vector<int>(n));
// Input the matrix elements
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
Solution sol;
bool result = sol.searchMatrix(matrix, target);
// Output the result
if (result) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
Java
import java.util.*; // For Scanner
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; // Number of rows
int n = matrix[0].length; // Number of columns
boolean found = false; // Step 1: Initialize the answer variable
// Create a Boolean variable found to indicate whether the target is present in the matrix.
// Initially set found = false.
// Step 2: Loop over each row of the matrix
// Use an outer loop i that ranges from 0 to m - 1 (where m is the number of rows).
for (int i = 0; i < m; i++) {
// Step 3: Check if the target could be in the current row
// For row i, check if target ≥ matrix[i][0] and target ≤ matrix[i][n - 1].
if (target >= matrix[i][0] && target <= matrix[i][n - 1]) {
// Step 4: Apply binary search in the current row
// Initialize two pointers: start = 0 and end = n - 1.
int start = 0, end = n - 1;
// While start ≤ end, do the following:
while (start <= end) {
// Step 5: Compute the middle index
int mid = (start + end) / 2;
// Step 6: Case 1 – If matrix[i][mid] == target
if (matrix[i][mid] == target) {
found = true;
break; // We found the target, exit binary search
}
// Step 7: Case 2 – If matrix[i][mid] < target
else if (matrix[i][mid] < target) {
start = mid + 1;
}
// Step 8: Case 3 – If matrix[i][mid] > target
else {
end = mid - 1;
}
}
}
// Step 9: After binary search, check if found is true
if (found) {
return true; // Return true immediately if target is found
}
}
// Step 10: After checking all rows, return the final answer
return false; // Target does not exist in the matrix
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Input number of rows, columns, and target
int m = sc.nextInt();
int n = sc.nextInt();
int target = sc.nextInt();
int[][] matrix = new int[m][n];
// Input the matrix elements
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
Solution sol = new Solution();
boolean result = sol.searchMatrix(matrix, target);
// Output the result
System.out.println(result ? "true" : "false");
}
}
Python
from typing import List # For specifying the return type
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# Step 1: Initialize the answer variable
found = False # Create a variable found to indicate whether the target is present in the matrix
# Initially set found = False
# Step 2: Loop over each row of the matrix
for i in range(len(matrix)):
# Step 3: Check if the target could be in the current row
if target >= matrix[i][0] and target <= matrix[i][-1]:
# Step 4: Apply binary search in the current row
start = 0
end = len(matrix[i]) - 1
while start <= end:
# Step 5: Compute the middle index
mid = (start + end) // 2
# Step 6: Case 1 – If matrix[i][mid] == target
if matrix[i][mid] == target:
found = True
break # We found the target, exit binary search
# Step 7: Case 2 – If matrix[i][mid] < target
elif matrix[i][mid] < target:
start = mid + 1
# Step 8: Case 3 – If matrix[i][mid] > target
else:
end = mid - 1
# Step 9: After binary search, check if found is true
if found:
return True # Return immediately if target is found
# Step 10: After checking all rows, return the final answer
return False # Target does not exist in the matrix
# Driver Code
if __name__ == "__main__":
m = int(input()) # Input the number of rows
n = int(input()) # Input the number of columns
target = int(input()) # Input the target value
matrix = []
for _ in range(m):
row = list(map(int, input().split())) # Input each row as space-separated integers
matrix.append(row)
sol = Solution()
ans = sol.searchMatrix(matrix, target)
print("true" if ans else "false") # Output whether the target exists in the matrix
Javascript
/**
* @param {number[][]} matrix - 2D array representing the matrix of numbers
* @param {number} target - The target number to search for
* @return {boolean} - Whether the target exists in the matrix
*/
var searchMatrix = function(matrix, target) {
// Step 1: Initialize the answer variable
let found = false; // Create a variable found to indicate whether the target is present in the matrix
// Initially set found = false
// Step 2: Loop over each row of the matrix
for (let i = 0; i < matrix.length; i++) {
// Step 3: Check if the target could be in the current row
if (target >= matrix[i][0] && target <= matrix[i][matrix[i].length - 1]) {
// Step 4: Apply binary search in the current row
let start = 0;
let end = matrix[i].length - 1;
while (start <= end) {
// Step 5: Compute the middle index
let mid = Math.floor((start + end) / 2);
// Step 6: Case 1 – If matrix[i][mid] == target
if (matrix[i][mid] === target) {
found = true;
break; // Break since we found the target
}
// Step 7: Case 2 – If matrix[i][mid] < target
else if (matrix[i][mid] < target) {
start = mid + 1;
}
// Step 8: Case 3 – If matrix[i][mid] > target
else {
end = mid - 1;
}
}
}
// Step 9: After binary search, check if found is true
if (found) {
return true; // Return immediately if target is found
}
}
// Step 10: After checking all rows, return the final answer
return false; // Target does not exist in the matrix
};
// Driver code
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let inputs = [];
let m = 0, n = 0, target = 0, rowCount = 0;
rl.on("line", function(line) {
if (inputs.length === 0) {
m = parseInt(line.trim()); // Input the number of rows
inputs.push(m);
} else if (inputs.length === 1) {
n = parseInt(line.trim()); // Input the number of columns
inputs.push(n);
} else if (inputs.length === 2) {
target = parseInt(line.trim()); // Input the target number
inputs.push(target);
} else {
let row = line.trim().split(' ').map(Number); // Input each row as space-separated integers
inputs.push(row);
rowCount++;
if (rowCount === m) {
let matrix = inputs.slice(3); // Extract the matrix part
let ans = searchMatrix(matrix, target);
console.log(ans ? "true" : "false"); // Output whether the target exists in the matrix
rl.close();
}
}
});
Time Complexity: O(m × log n)
Let us denote:
m = number of rows in the matrix
n = number of columns in the matrix
Initialization:
– We first get the number of rows m and the number of columns n using matrix.length and matrix[0].length.
– Time complexity: O(1) (constant time).
Loop Over Each Row:
– We use a for loop to iterate over each of the m rows.
– Number of iterations: m.
– Time complexity per iteration: depends on the binary search we perform next.
Binary Search in Each Row:
– Inside each row, we apply binary search to search for the target.
– Time complexity of binary search: O(log n).
– So, for each of the m rows: total time = O(log n).
Checking After Binary Search:
– After binary search, we check if found is true or false.
– This step is O(1).
Combining All Steps:
– Total time complexity: O(m) × O(log n) = O(m × log n).
Space Complexity: O(m × n)
Let us denote:
m = number of rows in the matrix
n = number of columns in the matrix
Auxiliary Space Complexity:
Definition: The extra space or temporary space used by the algorithm during its execution, excluding the input data.
Code Analysis:
The given code uses only a few variables:
– m and n for storing the number of rows and columns.
– found as a Boolean variable to indicate if the target is found.
– Loop variables like i, start, end, and mid during binary search.
All these variables take constant space (O(1)), independent of the input size.
Auxiliary Space Complexity: O(1)
Total Space Complexity:
The overall space used by the algorithm includes both the input data and the auxiliary space.
Input Data:
The input matrix itself is a 2D array with m rows and n columns, so it requires space proportional to its size: O(m × n).
Auxiliary Space: As analyzed above, O(1).
Combining Both:
Total space complexity: O(m × n) + O(1) = O(m × n).
Is the better approach efficient?
Given the problem constraints where the matrix dimensions satisfy 1 ≤ m, n ≤ 100, the binary search approach is also very practical.
Even though the method applies binary search on each row with time complexity O(m × log n), the total number of operations becomes at most 100 × log₂100 ≈ 100 × 7 = 700, which is extremely fast for modern computers.
Since m and n are relatively small, this approach remains efficient and easy to implement while taking advantage of the sorted property of each row.
Therefore, despite the overhead of binary search logic, the solution runs comfortably within time limits and works reliably in practice.
We have seen the binary search per row solution, which improves over brute force by using the sorted property of each row. But since the matrix itself is globally sorted—where each first element of a row is greater than the last element of the previous row—we can treat it like a single sorted list.
Can we use this property to search even faster without scanning each row separately? Let’s explore this in the most optimal approach.
Optimal Approach
Intuition
We are given a matrix where each row is sorted in non-decreasing order, and the first integer of each row is greater than the last integer of the previous row.
Let’s first understand what this means. A sorted row means the elements increase as we move left to right.
For example: [10, 11, 16, 20]
In this row:
– All elements are sorted in increasing order.
And because the first element of each row is greater than the last element of the previous row, if we list out all rows one after another, the entire matrix behaves like one big sorted list from top-left to bottom-right.
Visualizing the matrix as a flat sorted list
Observation: If we flatten the matrix into a single array, it would still be sorted.
Example:
Original matrix:
[ [1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60] ]
Flattened: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60]
Since the matrix has m rows and n columns, the flattened list has m × n elements.
Key Observations
Instead of actually flattening the matrix in memory, we can simulate it:
– Each element in the flattened list corresponds to some matrix[row][col].
– Given a single index mid in the flattened list (ranging from 0 to m × n – 1), we can compute:
– row = mid / n (using integer division)
– col = mid % n (using modulo)
This mapping helps us access any element as if the matrix were flattened, without using extra space.
Binary search on the virtual flattened array
Pick any index mid between start and end in the flattened list. It will either:
– Match the target
– Be smaller than the target
– Be greater than the target
Case 1: mid element equals target
Example: matrix[row][col] == target
Conclusion: We immediately return true, since we found the target.
Case 2: mid element is smaller than target
Example: matrix[row][col] < target
Conclusion: Since the entire flattened array is sorted, the target must be to the right of mid.
We move binary search to the right half: mid + 1 to end.
Case 3: mid element is greater than target
Example: matrix[row][col] > target
Conclusion: The target must be to the left of mid.
We move binary search to the left half: start to mid - 1.
The key idea:
– Treat the whole matrix as one sorted array of size m × n.
– Use binary search directly on this virtual array.
– Map each index back to matrix[row][col] using row = mid / n and col = mid % n.
This way, we avoid checking every cell and don’t need to physically flatten the matrix.
So, the approach is clean, elegant, and perfectly uses the sorted property of the matrix to search quickly.
Isn’t it intuitive?
Approach
Step 1: Initialize the search space
Since the entire matrix can be viewed as a single sorted list of size m × n,
create two pointers:
– start = 0 (beginning of the flattened list)
– end = m × n – 1 (last index of the flattened list)
Step 2: Apply binary search on this virtual flattened array
While start ≤ end, repeat the following steps.
Step 3: Compute the middle index
Compute:
mid = floor((start + end) / 2)
Step 4: Map mid index back to matrix coordinates
Since mid is in the virtual flattened array, map it to the matrix as follows:
– row = mid // n (integer division)
– col = mid % n (remainder)
Step 5: Case 1 – If matrix[row][col] == target
Observation: mid element matches the target.
Conclusion: Return true immediately since we found the target.
Step 6: Case 2 – If matrix[row][col] < target
Observation: mid element is smaller than target.
Conclusion: The target must be to the right of mid.
So, move start = mid + 1.
Step 7: Case 3 – If matrix[row][col] > target
Observation: mid element is greater than target.
Conclusion: The target must be to the left of mid.
So, move end = mid - 1.
Step 8: Return the final answer
If we finish the loop without finding the target, return false to indicate it does not exist in the matrix.
Dry Run
Here’s the detailed dry run of the above binary search approach for the input: matrix = [[1,3,5,7], [10,11,16,20], [23,30,34,60]], target = 13
Number of rows (m) = 3
Number of columns (n) = 4
Total elements = m × n = 12
We treat the entire matrix as a single sorted array of size 12, indexed from 0 to 11.
Initialize:
start = 0, end = 11
Iteration 1:
start = 0, end = 11
mid = floor((0+11)/2) = 5
Map mid back to matrix coordinates:
row = floor(5 / 4) = 1
col = 5 % 4 = 1
Check: matrix[1][1] = 11
11 < 13
Conclusion: target must be to the right of mid
Move: start = mid + 1 → start = 6
Iteration 2:
start = 6, end = 11
mid = floor((6+11)/2) = 8
Map mid back:
row = floor(8 / 4) = 2
col = 8 % 4 = 0
Check: matrix[2][0] = 23
23 > 13
Conclusion: target must be to the left of mid
Move: end = mid - 1 → end = 7
Iteration 3:
start = 6, end = 7
mid = floor((6+7)/2) = 6
Map back:
row = floor(6 / 4) = 1
col = 6 % 4 = 2
Check: matrix[1][2] = 16
16 > 13
Conclusion: target must be to the left of mid
Move: end = mid - 1 → end = 5
Now start = 6, end = 5 → start > end → loop stops
Final Result:
We didn’t find the target during binary search → return false.
Code for All Languages
C++
#include <iostream> // For input and output
#include <vector> // For using vector
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(); // Number of rows
int n = matrix[0].size(); // Number of columns
// Step 1: Initialize the search space
// Since the entire matrix can be viewed as a single sorted list of size m × n,
// create two pointers:
// – start = 0 (beginning of the flattened list)
// – end = m × n – 1 (last index of the flattened list)
int start = 0;
int end = m * n - 1;
// Step 2: Apply binary search on this virtual flattened array
// While start ≤ end, repeat the following steps.
while (start <= end) {
// Step 3: Compute the middle index
// Compute: mid = floor((start + end) / 2)
int mid = (start + end) / 2;
// Step 4: Map mid index back to matrix coordinates
// Since mid is in the virtual flattened array, map it to the matrix as follows:
// – row = mid // n (integer division)
// – col = mid % n (remainder)
int row = mid / n;
int col = mid % n;
// Step 5: Case 1 – If matrix[row][col] == target
// Observation: mid element matches the target.
// Conclusion: Return true immediately since we found the target.
if (matrix[row][col] == target) {
return true;
}
// Step 6: Case 2 – If matrix[row][col] < target
// Observation: mid element is smaller than target.
// Conclusion: The target must be to the right of mid.
// So, move start = mid + 1.
else if (matrix[row][col] < target) {
start = mid + 1;
}
// Step 7: Case 3 – If matrix[row][col] > target
// Observation: mid element is greater than target.
// Conclusion: The target must be to the left of mid.
// So, move end = mid - 1.
else {
end = mid - 1;
}
}
// Step 8: Return the final answer
// If we finish the loop without finding the target, return false to indicate it does not exist in the matrix.
return false;
}
};
int main() {
int m, n, target;
cin >> m >> n >> target; // Input number of rows, columns, and target
vector<vector<int>> matrix(m, vector<int>(n));
// Input the matrix elements
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
Solution sol;
bool result = sol.searchMatrix(matrix, target);
// Output the result
if (result) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}
return 0;
}
Java
import java.util.*; // For Scanner
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; // Number of rows
int n = matrix[0].length; // Number of columns
// Step 1: Initialize the search space
// Since the entire matrix can be viewed as a single sorted list of size m × n,
// create two pointers:
// – start = 0 (beginning of the flattened list)
// – end = m × n – 1 (last index of the flattened list)
int start = 0;
int end = m * n - 1;
// Step 2: Apply binary search on this virtual flattened array
// While start ≤ end, repeat the following steps.
while (start <= end) {
// Step 3: Compute the middle index
// Compute: mid = floor((start + end) / 2)
int mid = (start + end) / 2;
// Step 4: Map mid index back to matrix coordinates
// Since mid is in the virtual flattened array, map it to the matrix as follows:
// – row = mid / n (integer division)
// – col = mid % n (remainder)
int row = mid / n;
int col = mid % n;
// Step 5: Case 1 – If matrix[row][col] == target
// Observation: mid element matches the target.
// Conclusion: Return true immediately since we found the target.
if (matrix[row][col] == target) {
return true;
}
// Step 6: Case 2 – If matrix[row][col] < target
// Observation: mid element is smaller than target.
// Conclusion: The target must be to the right of mid.
else if (matrix[row][col] < target) {
start = mid + 1;
}
// Step 7: Case 3 – If matrix[row][col] > target
// Observation: mid element is greater than target.
// Conclusion: The target must be to the left of mid.
else {
end = mid - 1;
}
}
// Step 8: Return the final answer
// If we finish the loop without finding the target, return false to indicate it does not exist in the matrix.
return false;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Input number of rows, columns, and target
int m = sc.nextInt();
int n = sc.nextInt();
int target = sc.nextInt();
int[][] matrix = new int[m][n];
// Input the matrix elements
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
Solution sol = new Solution();
boolean result = sol.searchMatrix(matrix, target);
// Output the result
System.out.println(result ? "true" : "false");
}
}
Python
from typing import List # For specifying the return type
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix) # Number of rows
n = len(matrix[0]) # Number of columns
# Step 1: Initialize the search space
# Since the entire matrix can be viewed as a single sorted list of size m × n,
# create two pointers:
# – start = 0 (beginning of the flattened list)
# – end = m × n – 1 (last index of the flattened list)
start = 0
end = m * n - 1
# Step 2: Apply binary search on this virtual flattened array
# While start ≤ end, repeat the following steps.
while start <= end:
# Step 3: Compute the middle index
mid = (start + end) // 2
# Step 4: Map mid index back to matrix coordinates
# – row = mid // n (integer division)
# – col = mid % n (remainder)
row = mid // n
col = mid % n
# Step 5: Case 1 – If matrix[row][col] == target
if matrix[row][col] == target:
return True # Return true immediately since we found the target
# Step 6: Case 2 – If matrix[row][col] < target
elif matrix[row][col] < target:
start = mid + 1
# Step 7: Case 3 – If matrix[row][col] > target
else:
end = mid - 1
# Step 8: Return the final answer
return False # Target does not exist in the matrix
# Driver Code
if __name__ == "__main__":
m = int(input()) # Input the number of rows
n = int(input()) # Input the number of columns
target = int(input()) # Input the target value
matrix = []
for _ in range(m):
row = list(map(int, input().split())) # Input each row as space-separated integers
matrix.append(row)
sol = Solution()
ans = sol.searchMatrix(matrix, target)
print("true" if ans else "false") # Output whether the target exists in the matrix
Javascript
/**
* @param {number[][]} matrix - 2D array representing the matrix of numbers
* @param {number} target - The target number to search for
* @return {boolean} - Whether the target exists in the matrix
*/
var searchMatrix = function(matrix, target) {
let m = matrix.length; // Number of rows
let n = matrix[0].length; // Number of columns
// Step 1: Initialize the search space
// Since the entire matrix can be viewed as a single sorted list of size m × n,
// create two pointers:
// – start = 0 (beginning of the flattened list)
// – end = m × n – 1 (last index of the flattened list)
let start = 0;
let end = m * n - 1;
// Step 2: Apply binary search on this virtual flattened array
// While start ≤ end, repeat the following steps.
while (start <= end) {
// Step 3: Compute the middle index
let mid = Math.floor((start + end) / 2);
// Step 4: Map mid index back to matrix coordinates
// – row = Math.floor(mid / n)
// – col = mid % n
let row = Math.floor(mid / n);
let col = mid % n;
// Step 5: Case 1 – If matrix[row][col] === target
if (matrix[row][col] === target) {
return true; // Return true immediately since we found the target
}
// Step 6: Case 2 – If matrix[row][col] < target
else if (matrix[row][col] < target) {
start = mid + 1;
}
// Step 7: Case 3 – If matrix[row][col] > target
else {
end = mid - 1;
}
}
// Step 8: Return the final answer
return false; // Target does not exist in the matrix
};
// Driver code
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let inputs = [];
let m = 0, n = 0, target = 0, rowCount = 0;
rl.on("line", function(line) {
if (inputs.length === 0) {
m = parseInt(line.trim()); // Input the number of rows
inputs.push(m);
} else if (inputs.length === 1) {
n = parseInt(line.trim()); // Input the number of columns
inputs.push(n);
} else if (inputs.length === 2) {
target = parseInt(line.trim()); // Input the target number
inputs.push(target);
} else {
let row = line.trim().split(' ').map(Number); // Input each row as space-separated integers
inputs.push(row);
rowCount++;
if (rowCount === m) {
let matrix = inputs.slice(3); // Extract the matrix part
let ans = searchMatrix(matrix, target);
console.log(ans ? "true" : "false"); // Output whether the target exists in the matrix
rl.close();
}
}
});
Time complexity: O(log (m × n)).
Let us denote:
m = number of rows in the matrix
n = number of columns in the matrix
Initialization:
– We first get the number of rows m and the number of columns n using matrix.length and matrix[0].length.
– Time complexity: O(1) (constant time).
Binary Search on Flattened Matrix:
– We treat the matrix as a single sorted array of size m × n.
– We apply a single binary search over this virtual array.
Number of iterations:
– Binary search continues until start > end.
– The virtual array has size m × n, so the number of iterations is proportional to log(m × n).
Time complexity of binary search:
– O(log (m × n))
– This can also be expressed as O(log m + log n) = O(log (m × n)).
Mapping mid to matrix coordinates:
– In each iteration, computing row = mid / n and col = mid % n takes O(1) time.
Combining All Steps: Total time complexity: O(log (m × n)).
Space Complexity: O(m × n)
Let us denote:
m = number of rows in the matrix
n = number of columns in the matrix
Auxiliary Space Complexity:
Definition: The extra space or temporary space used by the algorithm during its execution, excluding the input data.
Code Analysis:
The given code uses only a few variables:
– m and n for storing the number of rows and columns.
– start, end, and mid for binary search over the flattened matrix.
All of these variables occupy constant space O(1), independent of the input size.
Auxiliary Space Complexity: O(1)
Total Space Complexity:
The overall space used by the algorithm includes both the input data and the auxiliary space.
Input Data:
The input matrix itself is a 2D array with m rows and n columns, so it requires space proportional to its size: O(m × n).
Auxiliary Space: As analyzed above, O(1).
Combining Both:
Total space complexity: O(m × n) + O(1) = O(m × n)
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
You are given a string message and a positive integer limit. Your task is to split message into consecutive parts so that each part ends with a suffix in the format <a/b>, where a is the part’s index (starting from 1) and b is the total number of parts. Each part, including its suffix, must have length exactly equal to limit, except possibly the last part, which can be shorter but must not exceed limit. After removing the suffixes from all parts and joining the remaining text, you should get back the original message.
The goal is to split the message into as few parts as possible. If it’s impossible to do this while following these rules, return an empty array.