Skip to main content

Search a 2D Matrix II Solution

In this tutorial, we will solve the Search a 2D Matrix II problem using efficient search techniques. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, and C++.

Problem Description​

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending order from left to right.
  • Integers in each column are sorted in ascending order from top to bottom.

Examples​

Example 1:

Input: matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
], target = 5
Output: true

Example 2:

Input: matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
], target = 20
Output: false

Constraints​

  • m == matrix.length
  • n == matrix[i].length
  • 1≤n,m≤3001 \leq n, m \leq 300
  • −109≤matrix[i][j]≤109-10^9 \leq \text{matrix[i][j]} \leq 10^9
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • −109≤target≤109-10^9 \leq target \leq 10^9

Solution for Search a 2D Matrix II​

Intuition and Approach​

To search for a value in this matrix efficiently, we can utilize the properties of the matrix. Since the matrix is sorted both row-wise and column-wise, we can start our search from the top-right corner of the matrix. From here, we have two options:

  1. If the target is greater than the current value, move downwards.
  2. If the target is less than the current value, move leftwards.

This approach ensures that we eliminate one row or one column in each step, leading to an efficient search.

By leveraging the sorted properties of the matrix, we can search for the target value efficiently using a greedy approach. This involves starting from the top-right corner and adjusting our search direction based on the current value.

Implementation​

Live Editor
function searchMatrix(matrix, target) {
  if (!matrix || matrix.length === 0 || matrix[0].length === 0) return false;
  let rows = matrix.length;
  let cols = matrix[0].length;
  let row = 0;
  let col = cols - 1;

  while (row < rows && col >= 0) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] > target) {
      col--;
    } else {
      row++;
    }
  }
  return false;
}

const matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30],
];
const target = 5;
const result = searchMatrix(matrix, target);

return (
  <div>
    <p>
      <b>Input:</b> matrix = [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9,
      16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ], target = 5
    </p>
    <p>
      <b>Output:</b> {result ? "true" : "false"}
    </p>
  </div>
);
Result
Loading...

Codes in Different Languages​

Written by @aryansh-patel
 function searchMatrix(matrix, target) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return false;
let rows = matrix.length;
let cols = matrix[0].length;
let row = 0;
let col = cols - 1;

while (row < rows && col >= 0) {
if (matrix[row][col] === target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}

Complexity Analysis​

  • Time Complexity: O(m+n)O(m + n), where m is the number of rows and n is the number of columns.

  • Space Complexity: O(1)O(1), as we are not using any additional space.

  • The time complexity is linear in terms of the dimensions of the matrix. Each step eliminates either a row or a

column, leading to a linear time complexity of O(m+n)O(m + n).

  • The space complexity is constant because we only use a few extra variables regardless of the matrix size.
Note

This solution leverages the matrix's properties to reduce the search space efficiently, making it suitable for large matrices.


Video Explanation of Search a 2D Matrix II​