Search in Row and Column-wise Sorted Matrix
Optimal Approach using Binary Search

⬅ Previous Topic

Next Topic ⮕

Topic Contents

Problem Examples Solution Algorithm Code Time Space

Problem Statement

You are given a 2D matrix where each row and each column is sorted in non-decreasing order. Your task is to search for a given target value in this matrix.

You need to determine whether the target value exists in the matrix or not. Return true if it exists, else return false.

The matrix is not fully sorted overall, but it has a special property:

Each row is sorted from left to right.
Each column is sorted from top to bottom.

This property allows us to use an efficient search technique rather than scanning every element.

Examples❯

Matrix	Target	Found	Description
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]	5	true	5 is present in the middle of the matrix
[[10, 20, 30], [15, 25, 35], [27, 29, 37]]	29	true	29 is present in the last row
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]	10	false	10 is greater than all elements in the matrix
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]	0	false	0 is smaller than all elements in the matrix
[[5]]	5	true	Single element match
[[5]]	3	false	Single element does not match
[]	1	false	Empty matrix has no elements

Solution❯

To solve this problem efficiently, we take advantage of the matrix's structure—each row and each column is sorted in non-decreasing order.

Understanding the Matrix Structure

Since rows are sorted left-to-right and columns are sorted top-to-bottom, this gives us a clever way to eliminate entire rows or columns at each step. We don’t need to check every cell.

Where to Start?

We begin our search at the top-right corner of the matrix. Why? Because:

The element at the top-right is the largest in its row and the smallest in its column.
This allows us to move left if the current element is too large or down if the current element is too small.

Step-by-Step Explanation

We set our starting position to row = 0 and col = number_of_columns - 1. Then we enter a loop that continues until either:

We find the target (return true), or
We move out of bounds (return false)

At each step:

If the current element equals the target, we’re done!
If the current element is greater than the target, we move left (since all elements to the left are smaller).
If the current element is less than the target, we move down (since all elements below are larger).

Handling Edge Cases

Empty Matrix: If the matrix has no rows or columns, we return false immediately.
Single Element Matrix: If it matches the target, return true. Otherwise, false.
Target smaller than all elements: We’ll keep moving left until we exit the matrix.
Target greater than all elements: We’ll keep moving down until we exit the matrix.

Why This Works

This approach ensures we only visit at most rows + columns elements in the worst case. So even if the matrix is large, this method stays efficient. The time complexity is O(N + M), where N = number of rows and M = number of columns.

Algorithm Steps

Start at the top-right corner of the matrix, i.e., row = 0, col = M - 1.
While row < N and col ≥ 0:
→ If mat[row][col] == target, return true.
→ If mat[row][col] > target, move left by doing col--.
→ If mat[row][col] < target, move down by doing row++.
If the loop ends without finding the target, return false.

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

public class MatrixSearch {
  public static boolean searchMatrix(int[][] mat, int target) {
    int n = mat.length;
    int m = mat[0].length;
    int row = 0, col = m - 1;

    while (row < n && col >= 0) {
      if (mat[row][col] == target) {
        return true;
      } else if (mat[row][col] > target) {
        col--; // Move left
      } else {
        row++; // Move down
      }
    }
    return false;
  }

  public static void main(String[] args) {
    int[][] mat = {
      {1, 4, 7},
      {2, 5, 8},
      {3, 6, 9}
    };
    int target = 5;
    System.out.println("Element found: " + searchMatrix(mat, target));
  }
}

Time Complexity

Case	Time Complexity	Explanation
Best Case	O(1)	When the target is found at the starting cell (top-right corner).
Average Case	O(N + M)	In each step, we either eliminate a row or a column, leading to at most N + M steps.
Worst Case	O(N + M)	In the worst case, the search visits one full row and one full column without finding the target.

Space Complexity

O(1)

Explanation: Only a few extra variables are used for row and column tracking, with no additional memory.

⬅ Previous Topic

Search in a Sorted 2D Matrix

Next Topic ⮕

Find Target in 2D Matrix

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Search in Row and Column-wise Sorted Matrix
Optimal Approach using Binary Search

Problem Statement

Examples❯

Solution❯

Understanding the Matrix Structure

Where to Start?

Step-by-Step Explanation

Handling Edge Cases

Why This Works

Algorithm Steps

Code

Time Complexity

Space Complexity

Support ProgramGuru.org❯

Search in Row and Column-wise Sorted MatrixOptimal Approach using Binary Search

Problem Statement

Examples❯

Solution❯

Understanding the Matrix Structure

Where to Start?

Step-by-Step Explanation

Handling Edge Cases

Why This Works

Algorithm Steps

Code

Time Complexity

Space Complexity

Welcome to ProgramGuru

Support ProgramGuru.org❯

Search in Row and Column-wise Sorted Matrix
Optimal Approach using Binary Search