Search a 2D Matrix II — LeetCode 240

What makes this different from Part 1?

The matrix here is only partially sorted: each row is sorted left-to-right and each column top-to-bottom — but the last value of row i is not necessarily smaller than the first value of row i+1.

This breaks the Part 1 trick of flattening to one sorted array. We need a smarter starting position that lets us eliminate exactly one row or column per step.

The algorithm

// Start at top-right corner
row = 0, col = n−1
while row < m and col ≥ 0:
  val = matrix[row][col]
  if val == target: ✓ found
  elif val > target: col−−
  else: row++
return false

💡 Why top-right? From the top-right corner, moving left decreases the value (row is sorted) and moving down increases it (column is sorted). This gives us a unique decision at each step — no guessing, no backtracking. Every step eliminates either an entire column (go left) or an entire row (go down). After at most m+n steps, we either find the target or exhaust the matrix.

❌ Why binary search fails here

Because rows aren't globally chained (row i+1 might start lower than where row i ends), the flattened array is not sorted. Binary search on it would skip or revisit the wrong cells.

✅ Why top-right works

Top-right is the unique corner that is the maximum of its row and minimum of its column. That "saddle point" property means one comparison always eliminates an entire row or column.

Complexity

Time

O(m + n)

At most m row-eliminations + n column-eliminations before leaving the matrix.

Space

O(1)

Just two pointers: row and col. No recursion, no auxiliary storage.

vs. Brute force

m·n / (m+n) ×

On a 100×100 matrix: 200 steps max vs up to 10 000 for a full scan.

Examples & edge cases

Live animation — Top-Right Staircase Search

Current cell ← Go left (col−−, val too big) ↓ Go down (row++, val too small) Found! Eliminated Path visited

⏸ Waiting to start

Current Row

—

Current Col

—

Value at cell

—

Decision

—

Step — of —

Steps taken

comparisons

Rows eliminated

moved down

Cols eliminated

moved left

Target

—

looking for

Select an example and press Play to begin.

✓ Found! ✗ Not Found

Speed Medium

Step-by-step table

Step	Row	Col	Value	vs Target	Decision	Rows gone	Cols gone

C++ implementation

search_2d_matrix_ii.cpp · LeetCode 240

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        // Start at top-right corner — the "saddle point"
        int row = 0, col = n - 1;

        while (row < m && col >= 0) {
            int val = matrix[row][col];

            if (val == target) {
                return true;    // ✓ Found!
            } else if (val > target) {
                col--;           // entire col[col] > target in this row → go left
            } else {
                row++;           // entire row[row] < target in this col → go down
            }
        }

        return false;   // exhausted matrix
    }
};

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars