Introduction

Search in Sorted Matrix means finding a target element inside a matrix where:

  • rows are sorted
  • columns are sorted

The task is to:

  • search efficiently
  • reduce unnecessary traversal
  • optimize search operations

Example:

Input Matrix:1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17

Target = 9

Output:
True

Explanation:

Target element:9

Element exists inside matrix.

This problem is one of the most important applications of:

 Staircase Search

Constraints

 1 <= Rows, Columns <= 10^3-10^9 <= Matrix Values <= 10^9

Approach 1 : Brute Force (Linear Search)

Explanations:

Explanation:

The idea is:

  • traverse every matrix element
  • compare with target

Steps:

  1. Traverse rows.
  2. Traverse columns.
  3. Compare with target.
  4. Return result.

This approach works but:

  • takes extra time

So optimized searching is preferred.

Dry Run

Matrix:1 4 7 11
2 5 8 12
3 6 9 16

Target:
9

Compare:
1, 4, 7 ...

Found:
9

Practice :

Complexity Analysis :

Time Complexity:- O(rows × cols)Explanation :
Every matrix element is visited once.

Space Complexity:- O(1)
Explanation :
No extra space is used.

Approach 2 : Optimal Solution(Staircase Search)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • start from top-right corner
  • eliminate one row or column at every step

Rules:

  • move left if current value is larger
  • move down if current value is smaller

This reduces:

  • unnecessary traversal

Dry Run

Matrix:1 4 7 11
2 5 8 12
3 6 9 16

Target:
9

Start:
11

Move left:
7

Move down:
8

Move down:
9

Target found.

Practice :

Complexity Analysis :

Time Complexity:- O(rows + cols)Explanation :
One row or column is eliminated each step.

Space Complexity:- O(1)
Explanation :
No extra space is used.

Why This Problem is Important

This problem builds the foundation for:

  • Matrix searching
  • Binary Search concepts
  • Efficient traversal
  • Grid optimization
  • Search algorithms

Real-World Applications

Sorted matrix searching concepts are used in:

  • Database systems
  • Spreadsheet software
  • Search engines
  • Scientific computing
  • Data analytics

Common Beginner Mistakes

  • Wrong starting position
  • Incorrect movement logic
  • Out of bounds errors
  • Confusing row and column movement
  • Infinite loops

Interview Tip

Interviewers often expect:

  • staircase search optimization
  • proper traversal logic
  • matrix understanding
  • O(rows + cols) solution

Always explain:

  • why top-right corner is chosen
  • how rows/columns are eliminated

Related Questions

  • Search a 2D Matrix
  • Binary Search
  • Matrix Traversal
  • Spiral Matrix
  • Rotate Matrix

Final Takeaway

The Search in Sorted Matrix problem is one of the most important matrix searching interview problems.

It teaches:

  • staircase search
  • matrix traversal
  • efficient searching
  • grid optimization

Understanding this problem builds a strong foundation for:

  •  advanced matrix problems
  • searching algorithms
  • interview-level data structure questions.