Search a Matrix Sorted by Rows and Columns

Quick Overview

Search a row-and-column sorted matrix with staircase elimination, proving why each move removes a safe region in linear rows-plus-columns time.

Search a Matrix Sorted by Rows and Columns

Company: ByteDance

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a rectangular matrix whose rows are sorted ascending left to right and columns ascending top to bottom, determine whether it contains a target value. ### Clarifying Questions to Ask - Are both rows and columns sorted, rather than the entire matrix flattened into one sorted sequence? - Can the matrix be empty or contain duplicate values? ```hint Choose a corner with opposite directions At one corner, moving in one direction increases values while moving in the other decreases them. ``` ### What a Strong Answer Covers - A staircase search from top-right or bottom-left. - Eliminating an entire row or column after each comparison. - O(rows+columns) time, empty input, and duplicate values. ### Follow-up Questions - Why is binary search on the flattened matrix not generally valid? - When might searching each row with binary search be preferable?

Overview: Search a row-and-column sorted matrix with staircase elimination, proving why each move removes a safe region in linear rows-plus-columns time.

ByteDance logo
ByteDance
Nov 13, 2026
mediumMachine Learning EngineerOnsiteCoding & Algorithms
0
0

Given a rectangular matrix whose rows are sorted ascending left to right and columns ascending top to bottom, determine whether it contains a target value.

Clarifying Questions to Ask Guidance

  • Are both rows and columns sorted, rather than the entire matrix flattened into one sorted sequence?
  • Can the matrix be empty or contain duplicate values?

What a Strong Answer Covers Guidance

  • A staircase search from top-right or bottom-left.
  • Eliminating an entire row or column after each comparison.
  • O(rows+columns) time, empty input, and duplicate values.

Follow-up Questions Guidance

  • Why is binary search on the flattened matrix not generally valid?
  • When might searching each row with binary search be preferable?