DSA-065 · FOCUSED PRACTICE

Search a Row-major Sorted Matrix

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 14124 deterministic checks. Learner drafts are not executed.

Understand the problem

Determine whether target occurs in a rectangular matrix whose flattened row-major sequence is nondecreasing. Search the virtual sequence without copying cells into a new array.

matrix is nonnull, rectangular, and has nonnull rows. The row-major sequence is globally nondecreasing: each row is sorted and each next row starts at least as high as the previous row ends. Duplicates and int extremes are valid.
Rectangular shape, row nonnullness, and ordering are unchecked preconditions, intentionally avoiding an O(R) metadata or O(RC) value-validation pass. There may be zero rows or a rectangular set of zero-length rows; both return false. Null top-level matrix throws NullPointerException.
There are at most 100,000 rows and 100,000 columns. Virtual cell counts and search indices use long, so products above Integer.MAX_VALUE are supported without allocating a flat copy. Input cells and row object references are unchanged; shared row objects are allowed when the ordering promise still holds.

Examples

Input: [[1,3,5],[7,9,11]], target=7
Output: true
Virtual index 3 maps to row 1, column 0 using division/remainder by three columns.
Input: [[1,3,5],[7,9,11]], target=6
Output: false
The value lies between rows but need not exist at the insertion boundary.
Input: [[],[]], any target
Output: false
A valid zero-column rectangle has no indexable cell.

Before you start

Rectangular matrices and row-major mapping
Half-open exact binary search and long arithmetic

Recognize the structure

Global row-major order is stronger than separately sorted rows or independently sorted rows and columns. That stronger promise permits one sorted virtual sequence; dimensions supply an O(1) mapping between virtual indices and coordinates.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 138/20,000 characters

Self-review

I distinguish global row-major order from weaker sorting promises.I cast before multiplying and cast back only coordinates.I report preconditions and validation cost honestly, and preserve row identities.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Imagine one globally sorted array, but avoid actually building it.

Hint 2

How does a virtual index map to row and column when every row has C cells?

Hint 3

Use a long [0,R*C) interval and map mid via /C and %C; guard empty dimensions first.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Scan all cells without assuming search order

Visit each row and each value and return on equality. For [[1,3,5],[7,9,11]], target=7, the scan checks four cells. This uses O(RC) cell comparisons and O(1) workspace; zero-column input still visits row metadata in the baseline. No flattened allocation is necessary even for the simple method.

Improve the baseline

Handle empty dimensions first

If R==0 return false before reading row zero. Read C from the first row, then return false if C==0 before dividing or taking remainders.

Create a long virtual interval

Set left=0,right=(long)R*C. Cast before multiplication; casting an already-overflowed int product is too late. Search [left,right) just like exact lookup.

Map only a probed virtual cell

For mid, row=mid/C and col=mid%C. Both fit int dimensions even when mid does not fit int. Compare that cell to target and discard the impossible virtual half.

Why it is correct

Bijection and sortedness

For C>0, division/remainder uniquely maps every k in [0,RC) to 0<=row<R and 0<=col<C. Global row-major order makes the cell values nondecreasing in k.

Candidate preservation

The exact-search invariant from DSA-059 applies to the virtual interval. A probed value below target excludes all earlier virtual cells; a value above target excludes the midpoint and all later cells.

Safety and termination

The long product and difference-based midpoint do not overflow under the dimension limits. Every mapped coordinate is valid by the bijection. Strict interval shrinkage returns equality or false without allocating a flat matrix or changing any row reference.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        Objects.requireNonNull(matrix, "matrix");
        if (matrix.length == 0) return false;
        int cols = matrix[0].length;
        if (cols == 0) return false;
        long left = 0, right = (long) matrix.length * cols;
        while (left < right) {
            long mid = left + (right - left) / 2;
            int value = matrix[(int) (mid / cols)][(int) (mid % cols)];
            if (value == target) return true;
            if (value < target) left = mid + 1;
            else right = mid;
        }
        return false;
    }
    public static boolean baseline(int[][] matrix, int target) {
        Objects.requireNonNull(matrix, "matrix");
        for (int[] row : matrix) for (int value : row) if (value == target) return true;
        return false;
    }
}

Read the meaningful blocks

Zero-dimension guards

Avoid matrix[0] when no rows and avoid /0 when no columns. Shape validation is a caller obligation, not a hidden pass.

Widen before multiplying

(long)matrix.length*cols produces the correct total. left/right/mid stay long; cast only mapped row and column indices back to int.

Global ordering is essential

The method compares by flattened position. It is not the staircase-search algorithm for the weaker row-and-column-sorted problem.

Complexity

Optimized time O(log(RC+1)) and O(1) auxiliary space for a valid rectangle, with O(1) empty-dimension handling. No shape or sortedness scan is included; adding full validation changes the end-to-end bound.

The baseline takes O(R+RC) traversal work including row metadata, and O(1) workspace. Flattening into a new array would add O(RC) time and space and eliminate the logarithmic lookup advantage for a single query.

Exact-state walkthroughs

Reveal normal and boundary traces

Virtual index maps across a row boundary

Input: {"matrix":[[1,3,5],[7,9,11]],"target":7} · Result: true

Step 1 of 3: Guard empty dimensions before mapping virtual indices.

The virtual sequence is globally sorted by precondition. Java uses a long product and no flattened allocation.

Matrix lookup — virtual row-major index

Virtual candidate elements: [0, 6). Columns per row: 3.

135

7911

The matrix is not flattened or mutated. Global row-major order and rectangular shape are preconditions; virtual indices use long in Java. Empty dimensions have no cells.

State after this step
Variable	Value
matrix	`[[1,3,5],[7,9,11]]`
target	`7`
rows	`2`
cols	`3`
left	`0`
right	`6`
bounds	`"half-open"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static boolean searchMatrix(int[][] matrix, int target) {
 5         Objects.requireNonNull(matrix, "matrix");
 6         if (matrix.length == 0) return false;
 7         int cols = matrix[0].length;
 8         if (cols == 0) return false;
 9         long left = 0, right = (long) matrix.length * cols;
10         while (left < right) {
11             long mid = left + (right - left) / 2;
12             int value = matrix[(int) (mid / cols)][(int) (mid % cols)];
13             if (value == target) return true;
14             if (value < target) left = mid + 1;
15             else right = mid;
16         }
17         return false;
18     }
19     public static boolean baseline(int[][] matrix, int target) {
20         Objects.requireNonNull(matrix, "matrix");
21         for (int[] row : matrix) for (int value : row) if (value == target) return true;
22         return false;
23     }
24 }
25

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Guard empty dimensions before mapping virtual indices.
The virtual sequence is globally sorted by precondition. Java uses a long product and no flattened allocation.
matrix
[[1,3,5],[7,9,11]]
target
7
rows
2
cols
3
left
0
right
6
bounds
"half-open"
phase
"search"
The mapped cell matches target.
Division/remainder by columns maps this original virtual index to one valid cell.
matrix
[[1,3,5],[7,9,11]]
target
7
rows
2
cols
3
left
0
right
6
bounds
"half-open"
phase
"search"
before
[0,6]
mid
3
row
1
col
0
probeValue
7
found
true
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
true

Absent value between sorted rows

Input: {"matrix":[[1,3,5],[7,9,11]],"target":6} · Result: false

Step 1 of 5: Guard empty dimensions before mapping virtual indices.

The virtual sequence is globally sorted by precondition. Java uses a long product and no flattened allocation.

Matrix lookup — virtual row-major index

Virtual candidate elements: [0, 6). Columns per row: 3.

135

7911

The matrix is not flattened or mutated. Global row-major order and rectangular shape are preconditions; virtual indices use long in Java. Empty dimensions have no cells.

State after this step
Variable	Value
matrix	`[[1,3,5],[7,9,11]]`
target	`6`
rows	`2`
cols	`3`
left	`0`
right	`6`
bounds	`"half-open"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static boolean searchMatrix(int[][] matrix, int target) {
 5         Objects.requireNonNull(matrix, "matrix");
 6         if (matrix.length == 0) return false;
 7         int cols = matrix[0].length;
 8         if (cols == 0) return false;
 9         long left = 0, right = (long) matrix.length * cols;
10         while (left < right) {
11             long mid = left + (right - left) / 2;
12             int value = matrix[(int) (mid / cols)][(int) (mid % cols)];
13             if (value == target) return true;
14             if (value < target) left = mid + 1;
15             else right = mid;
16         }
17         return false;
18     }
19     public static boolean baseline(int[][] matrix, int target) {
20         Objects.requireNonNull(matrix, "matrix");
21         for (int[] row : matrix) for (int value : row) if (value == target) return true;
22         return false;
23     }
24 }
25

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Guard empty dimensions before mapping virtual indices.
The virtual sequence is globally sorted by precondition. Java uses a long product and no flattened allocation.
matrix
[[1,3,5],[7,9,11]]
target
6
rows
2
cols
3
left
0
right
6
bounds
"half-open"
phase
"search"
Discard the impossible virtual half.
The exact-search invariant applies to flattened order without copying any matrix cells.
matrix
[[1,3,5],[7,9,11]]
target
6
rows
2
cols
3
left
0
right
3
bounds
"half-open"
phase
"search"
before
[0,6]
mid
3
row
1
col
0
probeValue
7
found
false
Discard the impossible virtual half.
The exact-search invariant applies to flattened order without copying any matrix cells.
matrix
[[1,3,5],[7,9,11]]
target
6
rows
2
cols
3
left
2
right
3
bounds
"half-open"
phase
"search"
before
[0,3]
mid
1
row
0
col
1
probeValue
3
found
false
Discard the impossible virtual half.
The exact-search invariant applies to flattened order without copying any matrix cells.
matrix
[[1,3,5],[7,9,11]]
target
6
rows
2
cols
3
left
3
right
3
bounds
"half-open"
phase
"search"
before
[2,3]
mid
2
row
0
col
2
probeValue
5
found
false
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
false

Zero-column rectangle

Input: {"matrix":[[],[]],"target":1} · Result: false

Step 1 of 2: Guard empty dimensions before mapping virtual indices.

The virtual sequence is globally sorted by precondition. Java uses a long product and no flattened allocation.

Matrix lookup — virtual row-major index

Virtual candidate elements: [0, 0). Columns per row: 0.

The matrix is not flattened or mutated. Global row-major order and rectangular shape are preconditions; virtual indices use long in Java. Empty dimensions have no cells.

State after this step
Variable	Value
matrix	`[[],[]]`
target	`1`
rows	`2`
cols	`0`
left	`0`
right	`0`
bounds	`"half-open"`
phase	`"search"`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     public static boolean searchMatrix(int[][] matrix, int target) {
 5         Objects.requireNonNull(matrix, "matrix");
 6         if (matrix.length == 0) return false;
 7         int cols = matrix[0].length;
 8         if (cols == 0) return false;
 9         long left = 0, right = (long) matrix.length * cols;
10         while (left < right) {
11             long mid = left + (right - left) / 2;
12             int value = matrix[(int) (mid / cols)][(int) (mid % cols)];
13             if (value == target) return true;
14             if (value < target) left = mid + 1;
15             else right = mid;
16         }
17         return false;
18     }
19     public static boolean baseline(int[][] matrix, int target) {
20         Objects.requireNonNull(matrix, "matrix");
21         for (int[] row : matrix) for (int value : row) if (value == target) return true;
22         return false;
23     }
24 }
25

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Guard empty dimensions before mapping virtual indices.
The virtual sequence is globally sorted by precondition. Java uses a long product and no flattened allocation.
matrix
[[],[]]
target
1
rows
2
cols
0
left
0
right
0
bounds
"half-open"
phase
"search"
Return the documented value, index, boundary, range, or rate.
The final result follows the problem-specific contract; the inputs were never mutated.
result
false

Test the contract

Input: [] and [[],[]]
Output: false
Both empty-dimension policies.
Input: [[1,3,5],[7,9,11]], target=7
Output: true
First cell of second row.
Input: Same matrix, target=6
Output: false
Gap between rows.
Input: [[MIN,0],[0,MAX]], target=MAX
Output: true
Duplicates across a row boundary.
Input: 50,000 shared 50,000-cell rows, all 7
Output: true for 7; false for 6/8
2.5 billion virtual cells exercise long indices with a small aliasing fixture.

Common mistakes and counterexamples

Use only row/column ordering

Counterexample: [[1,4],[2,5]] has sorted rows and columns but flattened [1,4,2,5] is not sorted.

Require global row-major order or use a different staircase algorithm.

Multiply R*C as int

Counterexample: 50,000×50,000 exceeds Integer.MAX_VALUE even though each dimension fits int.

Promote R before multiplication and retain long virtual indices.

Map using the number of rows

Counterexample: A 2×3 matrix needs index/C with C=3, not index/R.

Use columns for both quotient and remainder.

Claim logarithmic time after scanning shape/order

Counterexample: Checking every row length adds O(R); checking every cell adds O(RC).

State unchecked shape/order preconditions or report validation cost explicitly.

Follow-ups

Only rows and columns are individually sorted.

Use a corner-based staircase search, discarding a row or column per step in O(R+C). Flattening cannot be justified under that weaker ordering.

Rows have different lengths.

A ragged representation needs row-length prefix metadata or another indexing structure; coordinate mapping is no longer one division/remainder. Include preprocessing and mapping costs.

Many queries target the same matrix.

The virtual search already reuses dimensions with no value copy. If input validation is required, validate once in an immutable snapshot API and distinguish construction cost from per-query cost.

Related foundations

Binary search: candidate intervals and monotone feasibility

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.