Search a Row- and Column-Sorted Matrix
Updated
Problem statement
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. The matrix has these properties:
- The integers in each row are sorted in non-decreasing order from left to right.
- The integers in each column are sorted in non-decreasing order from top to bottom.
Return true if target appears anywhere in the matrix, and false otherwise. The first value of a row can be smaller than the last value of the row above it, so the matrix is not one sorted list read row by row.
Function
searchMatrix(matrix: int[][], target: int) → booleanExamples
Example 1
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 = 5return = true5is in the second row and second column, so the answer istrue.
Example 2
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 = 20return = false20would sit between19and21, but no cell holds it, so the answer isfalse.
Constraints
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109- Every row is sorted in non-decreasing order from left to right.
- Every column is sorted in non-decreasing order from top to bottom.
-109 <= target <= 109
More ByteDance Onsite Interview questions
- Alien DictionaryPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lexicographically Smallest Topological OrderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Implement Multi-Head AttentionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dynamic Median with Additions and DeletionsONSITE INTERVIEW · Seen Oct 2026
- Serialize and Deserialize a String Key-Value StoreONSITE INTERVIEW · Seen Oct 2026
- Binary Tree Maximum Path SumONSITE INTERVIEW · Seen Oct 2026
- Merge Overlapping IntervalsONSITE INTERVIEW · Seen Oct 2026
- Tic-Tac-Toe Move WinnersONSITE INTERVIEW · Seen Oct 2026
- Kth Largest Element without a HeapONSITE INTERVIEW · Seen Oct 2026
- Least Recently Used CachePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- 3Sum SmallerSalesforce · ONSITE INTERVIEWSalesforce interview questions
- K Smallest Squares from a Sorted ArrayUber · ONSITE INTERVIEWUber interview questions
- Find K Closest Elements in a Sorted ArrayLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Row with Maximum OnesAmazon · ONSITE INTERVIEW
- Search a Row-Major Sorted MatrixMotive · ONSITE INTERVIEWMotive interview questions
- Party Celebrity from a Knows MatrixExpedia · ONSITE INTERVIEWExpedia interview questions
- Find K Closest Elements in a Sorted ArrayBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Find K Closest Elements in a Sorted ArrayNavi · PHONE SCREEN
- Grid Path With the Most ClearanceDocuSign · OADocuSign interview questions
- Count Winning Dice Face PairsGoogle · PHONE SCREENGoogle interview questions