Row-sorted and Column-sorted Matrices - Searching in 2D Matrices | OneNoughtOne

0/361

Data Structures & AlgorithmsSearching Algorithms

Searching in 2D Matrices

LevelIntermediate

Duration90 mins

TopicSearching Algorithms

1 / 4

Row-sorted and Column-sorted Matrices

From Lines to Grids: The 2D Search Challenge

Up until now, our search algorithms have operated on one-dimensional sequences—arrays, lists, and linear collections. Binary search, the crown jewel of efficient searching, exploits the sorted property of a linear sequence to eliminate half the search space with each comparison. But what happens when our data lives in two dimensions?

The 2D matrix represents a natural extension of linear data structures. Spreadsheets, images, game boards, geographic grids, and database tables all organize information in rows and columns. When these matrices possess sorted properties, we can develop specialized search algorithms that dramatically outperform brute-force scanning.

This page establishes the foundational understanding of sorted 2D matrices—specifically, what it means for a matrix to be row-sorted, column-sorted, or both. These structural properties form the bedrock upon which efficient 2D search algorithms are built.

What You Will Learn

By the end of this page, you will understand the precise definitions of row-sorted and column-sorted matrices, recognize how sorting properties constrain element positions, visualize the geometric interpretation of sorted structure, and appreciate why different sorting configurations demand different search strategies.

The Anatomy of a 2D Matrix

Before diving into sorted properties, let's establish precise terminology for working with 2D matrices.

Definition: A 2D matrix M is a rectangular array of elements arranged in m rows and n columns. We denote the element at row i and column j as M[i][j], where:

i ranges from 0 to m-1 (row index)
j ranges from 0 to n-1 (column index)

This gives us m × n total elements, each uniquely identified by its (row, column) coordinate pair.

matrix_representation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# A 4×5 matrix (4 rows, 5 columns)
matrix = [
    [10, 20, 30, 40, 50],      # Row 0
    [15, 25, 35, 45, 55],      # Row 1
    [27, 29, 37, 48, 60],      # Row 2
    [32, 33, 39, 50, 62]       # Row 3
]
#    Col 0  1   2   3   4
 
# Access element at row 2, column 3
element = matrix[2][3]  # Returns 48
 
# Matrix dimensions
m = len(matrix)         # 4 rows
n = len(matrix[0])      # 5 columns
total_elements = m * n  # 20 elements

Key Geometric Concepts:

Row: A horizontal sequence of elements. Row i contains elements M[i][0], M[i][1], ..., M[i][n-1].
Column: A vertical sequence of elements. Column j contains elements M[0][j], M[1][j], ..., M[m-1][j].
Diagonal: Elements where row and column indices have a fixed relationship. The main diagonal contains M[0][0], M[1][1], ...
Corner Elements: The four extreme positions—top-left M[0][0], top-right M[0][n-1], bottom-left M[m-1][0], bottom-right M[m-1][n-1].

These structural concepts become critical when analyzing search algorithms, as the sorted property creates predictable relationships between element positions.

Memory Layout Matters

In most programming languages, 2D matrices are stored as arrays of arrays (row-major order), meaning elements in the same row are contiguous in memory. This affects cache performance: traversing by rows is typically faster than traversing by columns due to spatial locality.

Row-Sorted Matrices — Definition and Properties

A row-sorted matrix is one where each row, considered independently, is sorted in non-decreasing order. This is the simplest form of 2D sorted structure.

Formal Definition:

A matrix M of dimensions m × n is row-sorted if and only if:

For all i ∈ [0, m-1] and j ∈ [0, n-2]:
    M[i][j] ≤ M[i][j+1]

In other words, within any single row, elements increase (or stay equal) as we move from left to right.

row_sorted_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Row-sorted matrix example
# Each row is independently sorted, but columns have no ordering guarantee
 
row_sorted_matrix = [
    [1,  4,  7,  11],    # Row 0: sorted ✓
    [2,  5,  8,  12],    # Row 1: sorted ✓
    [10, 13, 14, 17],    # Row 2: sorted ✓
    [18, 21, 23, 26]     # Row 3: sorted ✓
]
 
# This is also row-sorted (rows don't need inter-row ordering):
another_row_sorted = [
    [50, 60, 70, 80],    # Row 0: sorted ✓
    [5,  10, 15, 20],    # Row 1: sorted ✓ (smaller than row 0!)
    [100, 200, 300, 400] # Row 2: sorted ✓
]
 
def is_row_sorted(matrix):
    """Verify a matrix is row-sorted."""
    for row in matrix:
        for j in range(len(row) - 1):
            if row[j] > row[j + 1]:
                return False
    return True
 
print(is_row_sorted(row_sorted_matrix))      # True
print(is_row_sorted(another_row_sorted))     # True

Properties of Row-Sorted Matrices:

Minimum Element per Row: The leftmost element of each row (M[i][0]) is the minimum in that row.
Maximum Element per Row: The rightmost element of each row (M[i][n-1]) is the maximum in that row.
Binary Search per Row: We can apply standard binary search within any single row, achieving O(log n) search time for that row.
No Cross-Row Guarantees: Crucially, row-sorted structure tells us nothing about the relationship between elements in different rows. M[0][0] might be greater than, equal to, or less than M[1][0].
Total Elements Still Require Row Scans: To find a target in a row-sorted matrix without additional structure, we might need to binary search each row independently.

Row-Sorted Matrix Search Implications
Property	What It Tells Us	Search Implication
M[i][j] ≤ M[i][j+1]	Elements increase left-to-right within rows	Binary search works within each row
No column ordering	Column values can be arbitrary between rows	Cannot eliminate rows based on column values alone
Row min at column 0	First column has each row's minimum	Can skip entire row if target < M[i][0]
Row max at column n-1	Last column has each row's maximum	Can skip entire row if target > M[i][n-1]

Row-Sorted Search Strategy

For a row-sorted matrix, the baseline approach is to binary search each row, giving O(m × log n) time complexity. However, we can optimize by first checking if the target falls within each row's range [M[i][0], M[i][n-1]] before performing binary search, potentially skipping many rows entirely.

Column-Sorted Matrices — Definition and Properties

A column-sorted matrix is the vertical analog of row-sorted: each column, considered independently, is sorted in non-decreasing order from top to bottom.

Formal Definition:

A matrix M of dimensions m × n is column-sorted if and only if:

For all i ∈ [0, m-2] and j ∈ [0, n-1]:
    M[i][j] ≤ M[i+1][j]

In other words, within any single column, elements increase (or stay equal) as we move from top to bottom.

column_sorted_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Column-sorted matrix example
# Each column is independently sorted, but rows have no ordering guarantee
 
column_sorted_matrix = [
    [1,  5,  10, 2],     # Column values increase downward
    [3,  7,  15, 8],     
    [6,  12, 18, 14],    
    [9,  20, 25, 22]     
]
# Col 0: 1→3→6→9 ✓
# Col 1: 5→7→12→20 ✓
# Col 2: 10→15→18→25 ✓
# Col 3: 2→8→14→22 ✓
 
# But rows are NOT sorted:
# Row 0: [1, 5, 10, 2] — 10 > 2, not sorted!
 
def is_column_sorted(matrix):
    """Verify a matrix is column-sorted."""
    if not matrix:
        return True
    m, n = len(matrix), len(matrix[0])
    
    for j in range(n):  # For each column
        for i in range(m - 1):  # Check vertical adjacency
            if matrix[i][j] > matrix[i + 1][j]:
                return False
    return True
 
print(is_column_sorted(column_sorted_matrix))  # True
 
def is_row_sorted(matrix):
    """Check if rows are sorted."""
    for row in matrix:
        for j in range(len(row) - 1):
            if row[j] > row[j + 1]:
                return False
    return True
 
print(is_row_sorted(column_sorted_matrix))     # False

Properties of Column-Sorted Matrices:

Minimum Element per Column: The topmost element of each column (M[0][j]) is the minimum in that column.
Maximum Element per Column: The bottommost element of each column (M[m-1][j]) is the maximum in that column.
Binary Search per Column: We can apply binary search within any single column, achieving O(log m) search time for that column.
No Cross-Column Guarantees: Column-sorted structure tells us nothing about relationships across different columns. Adjacent columns may have interleaved or completely disjoint value ranges.
Symmetric to Row-Sorted: All properties of row-sorted matrices have column-sorted analogs, just rotated 90 degrees.

Column-Sorted Search Strategy

For a column-sorted matrix, we can binary search each column, giving O(n × log m) time complexity. This is analogous to row-sorted search but operates vertically. The choice between row-first or column-first searching depends on the matrix aspect ratio (m vs n).

Row AND Column Sorted — The Young Tableau Property

The most interesting case occurs when a matrix is sorted both by rows AND by columns simultaneously. This creates a structure known as a Young Tableau (named after Alfred Young) or a sorted matrix.

Formal Definition:

A matrix M is row-and-column-sorted if and only if:

For all valid i, j:
    M[i][j] ≤ M[i][j+1]     (row-sorted)
    M[i][j] ≤ M[i+1][j]     (column-sorted)

This dual constraint creates powerful structural properties that enable elegant and efficient search algorithms.

young_tableau_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Row-and-column-sorted matrix (Young Tableau)
# BOTH rows AND columns are sorted
 
young_tableau = [
    [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]
]
 
# Verify row-sorted: each row increases left-to-right ✓
# Verify column-sorted: each column increases top-to-bottom ✓
 
def is_young_tableau(matrix):
    """Verify a matrix is both row and column sorted."""
    if not matrix:
        return True
    m, n = len(matrix), len(matrix[0])
    
    for i in range(m):
        for j in range(n):
            # Check right neighbor (row-sorted property)
            if j + 1 < n and matrix[i][j] > matrix[i][j + 1]:
                return False
            # Check bottom neighbor (column-sorted property)
            if i + 1 < m and matrix[i][j] > matrix[i + 1][j]:
                return False
    return True
 
print(is_young_tableau(young_tableau))  # True
 
# Visualizing the structure:
# Each element is ≤ its right neighbor AND ≤ its bottom neighbor
# This creates a "flow" from top-left (minimum) to bottom-right (maximum)

Critical Properties of Row-and-Column-Sorted Matrices:

1. Global Minimum and Maximum:

The top-left element M[0][0] is the global minimum of the entire matrix.
The bottom-right element M[m-1][n-1] is the global maximum of the entire matrix.

2. Monotonic Paths:

Any path moving only right and/or down encounters elements in non-decreasing order.
Any path moving only left and/or up encounters elements in non-increasing order.

3. The Staircase Property:

From any position, moving right increases or maintains the value.
From any position, moving down increases or maintains the value.
This creates a "monotonic landscape" that search algorithms can exploit.

4. Corner Information:

Top-right corner M[0][n-1]: Maximum of first row, minimum of last column.
Bottom-left corner M[m-1][0]: Maximum of first column, minimum of last row.
These corners provide crucial decision points for search algorithms.

The Power of Dual Sorting

The row-and-column-sorted property enables O(m + n) search time—far better than the O(m × n) brute force. This is because from certain positions (top-right or bottom-left corners), every comparison eliminates an entire row OR an entire column from consideration.

Visualizing the Sorted Structure

Understanding sorted 2D matrices becomes much clearer through visualization. Let's explore how the sorting constraints create geometric patterns in the value landscape.

The Value Gradient:

In a row-and-column-sorted matrix, imagine each cell's value as its elevation on a 3D terrain. The dual sorting property creates a surface that:

Rises as you move right (row-sorted)
Rises as you move down (column-sorted)
Has its lowest point at the top-left corner
Has its highest point at the bottom-right corner

This creates a "ramp" that ascends from the top-left to the bottom-right.

value_landscape.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Visualizing the value constraints in a row-and-column-sorted matrix
 
matrix = [
    [1,   4,   7,  11],
    [2,   5,   8,  12],
    [3,   6,   9,  16],
    [10,  13,  14,  17]
]
 
def visualize_constraints(matrix):
    """
    Show how each element relates to its neighbors.
    
    For element at (i, j):
    - LEFT neighbor (if exists): smaller or equal
    - RIGHT neighbor (if exists): larger or equal
    - UP neighbor (if exists): smaller or equal
    - DOWN neighbor (if exists): larger or equal
    """
    m, n = len(matrix), len(matrix[0])
    
    for i in range(m):
        for j in range(n):
            val = matrix[i][j]
            constraints = []
            
            # Check relationships with neighbors
            if j > 0:
                constraints.append(f"{matrix[i][j-1]} ≤ {val}")  # Left
            if j < n - 1:
                constraints.append(f"{val} ≤ {matrix[i][j+1]}")  # Right
            if i > 0:
                constraints.append(f"{matrix[i-1][j]} ≤ {val}")  # Up
            if i < m - 1:
                constraints.append(f"{val} ≤ {matrix[i+1][j]}")  # Down
            
            print(f"M[{i}][{j}] = {val}: {', '.join(constraints)}")
        print()
 
# The constraint network creates a partial ordering of all elements
# This partial order is what enables efficient search

Contour Lines and Search Regions:

Another powerful visualization is to think of contour lines—imaginary boundaries connecting cells of equal value. In a row-and-column-sorted matrix:

Values less than target: Form a connected region anchored at the top-left corner.
Values greater than target: Form a connected region anchored at the bottom-right corner.
The boundary: The transition between "less than" and "greater than" regions forms a staircase pattern.

This staircase boundary is exactly what the staircase search algorithm (covered in the next page) exploits to achieve O(m + n) search time.

Converting Mermaid diagram...

The Staircase Boundary

If we color all elements < target as blue and all elements > target as red, the boundary between these colors forms a staircase shape. The target (if present) sits at a step of this staircase. This geometric insight is fundamental to understanding why O(m + n) search is possible.

Distinguishing Matrix Types in Practice

When facing a 2D matrix search problem, the first critical step is identifying the sorting structure. Different matrix types require different algorithms and achieve different complexities.

Quick Classification Algorithm:

matrix_classifier.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def classify_matrix(matrix):
    """
    Classify a matrix by its sorting properties.
    
    Returns one of:
    - 'fully_sorted': Can be treated as a 1D sorted array
    - 'row_and_column_sorted': Young Tableau structure
    - 'row_sorted': Only rows are individually sorted
    - 'column_sorted': Only columns are individually sorted
    - 'unsorted': No sorted structure
    """
    if not matrix or not matrix[0]:
        return 'empty'
    
    m, n = len(matrix), len(matrix[0])
    
    # Check row-sorted property
    row_sorted = True
    for i in range(m):
        for j in range(n - 1):
            if matrix[i][j] > matrix[i][j + 1]:
                row_sorted = False
                break
        if not row_sorted:
            break
    
    # Check column-sorted property
    col_sorted = True
    for j in range(n):
        for i in range(m - 1):
            if matrix[i][j] > matrix[i + 1][j]:
                col_sorted = False
                break
        if not col_sorted:
            break
    
    # Check fully sorted (each row continues from previous)
    fully_sorted = row_sorted  # Must be row-sorted first
    if fully_sorted:
        for i in range(m - 1):
            if matrix[i][n - 1] > matrix[i + 1][0]:
                fully_sorted = False
                break
    
    # Classify
    if fully_sorted:
        return 'fully_sorted'
    elif row_sorted and col_sorted:
        return 'row_and_column_sorted'
    elif row_sorted:
        return 'row_sorted'
    elif col_sorted:
        return 'column_sorted'
    else:
        return 'unsorted'
 
# Examples
print(classify_matrix([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]))  # 'fully_sorted'
 
print(classify_matrix([
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9]
]))  # 'row_and_column_sorted'
 
print(classify_matrix([
    [10, 20, 30],
    [1, 2, 3],
    [100, 200, 300]
]))  # 'row_sorted'

Matrix Types and Their Search Implications
Matrix Type	Structure	Best Search Algorithm	Time Complexity
Fully Sorted	Row ends ≤ next row start	Single binary search (treat as 1D)	O(log(m × n))
Row-and-Column Sorted	Rows sorted, columns sorted	Staircase search	O(m + n)
Row-Sorted Only	Each row independently sorted	Binary search per row	O(m × log n)
Column-Sorted Only	Each column independently sorted	Binary search per column	O(n × log m)
Unsorted	No sorting guarantees	Brute force scan	O(m × n)

Problem Statement Precision

Interview and competitive programming problems often describe matrices as 'sorted' without specifying the exact structure. Always clarify: Is it row-sorted only? Column-sorted only? Both? Or fully sorted as a linearized 1D array? The answer determines your algorithm.

Real-World Examples of Sorted Matrices

Sorted 2D matrices aren't just theoretical constructs—they appear naturally in many practical applications:

1. Calendar/Schedule Data:

Rows represent days, columns represent time slots
Appointments are sorted by date (rows) and time (columns)
Finding available slots is a 2D search problem

2. Geographic Grid Data:

Elevation maps where values increase predictably
Temperature gradients with latitude (rows) and altitude (columns)
Searching for specific conditions in climate models

3. Database Indexes:

Composite indexes on two sorted columns
Range queries that leverage the sorted structure
B-tree variations for 2D data

4. Image Processing:

Integral images (summed-area tables) are row-and-column sorted
Used for efficient feature computation
Enables O(1) rectangular sum queries

5. Spreadsheet Applications:

Sorted data tables with multiple sort keys
Finding entries in sorted rows with sorted column headers
Excel's data lookup functions exploit this structure

Classic Interview Problems

•Search a 2D Matrix (LeetCode 74): Matrix is fully sorted—use single binary search
•Search a 2D Matrix II (LeetCode 240): Row-and-column sorted—use staircase search
•Kth Smallest Element in a Sorted Matrix (LeetCode 378): Uses heap with matrix structure
•Count Negative Numbers in a Sorted Matrix (LeetCode 1351): Exploits staircase boundary
•Find a Peak Element II (LeetCode 1901): Uses binary reduction on sorted structure

Interview Strategy

When given a 2D matrix search problem, always ask: 'What are the sorting guarantees?' This single question often reveals the intended algorithm. Fully sorted → binary search. Row-and-column sorted → staircase. Anything else → consider the specific structure carefully.

Mathematical Foundations

Understanding the mathematical structure of sorted matrices provides deeper insight into why certain search algorithms work.

Partial Ordering:

A row-and-column-sorted matrix defines a partial order on its elements. Given two positions (i₁, j₁) and (i₂, j₂):

If i₁ ≤ i₂ AND j₁ ≤ j₂, then M[i₁][j₁] ≤ M[i₂][j₂]

This is a partial (not total) order because some pairs of elements are incomparable. For example, M[0][2] and M[2][0] have no guaranteed relationship—we can't deduce which is larger without knowing their values.

Lattice Structure:

The set of matrix positions forms a lattice under the coordinate-wise comparison:

Join (⊔): (i₁, j₁) ⊔ (i₂, j₂) = (max(i₁, i₂), max(j₁, j₂))
Meet (⊓): (i₁, j₁) ⊓ (i₂, j₂) = (min(i₁, i₂), min(j₁, j₂))

This lattice structure means:

There's a unique minimum position: (0, 0)
There's a unique maximum position: (m-1, n-1)
Any two positions have well-defined upper and lower bounds

partial_order_analysis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def can_compare(pos1, pos2):
    """
    Determine if two positions are comparable in the partial order.
    
    (i1, j1) ≤ (i2, j2) iff i1 ≤ i2 AND j1 ≤ j2
    
    Two positions are comparable if one dominates the other.
    """
    i1, j1 = pos1
    i2, j2 = pos2
    
    # pos1 ≤ pos2
    if i1 <= i2 and j1 <= j2:
        return True, f"{pos1} ≤ {pos2}"
    
    # pos2 ≤ pos1
    if i2 <= i1 and j2 <= j1:
        return True, f"{pos2} ≤ {pos1}"
    
    # Incomparable
    return False, f"{pos1} and {pos2} are incomparable"
 
# Examples
print(can_compare((0, 0), (2, 2)))  # True, (0,0) ≤ (2,2)
print(can_compare((0, 2), (2, 0)))  # False, incomparable
print(can_compare((1, 1), (1, 3)))  # True, (1,1) ≤ (1,3)
 
# In a row-and-column sorted matrix:
# If can_compare returns True with pos1 ≤ pos2, then M[pos1] ≤ M[pos2]
# If positions are incomparable, M[pos1] and M[pos2] could be in any order
 
def count_comparable_pairs(m, n):
    """Count how many pairs of positions are comparable."""
    total_pairs = (m * n) * (m * n - 1) // 2
    comparable = 0
    
    for i1 in range(m):
        for j1 in range(n):
            for i2 in range(m):
                for j2 in range(n):
                    if (i1, j1) < (i2, j2):  # Avoid double counting
                        result, _ = can_compare((i1, j1), (i2, j2))
                        if result:
                            comparable += 1
    
    return comparable, total_pairs
 
# For a 4×4 matrix:
comp, total = count_comparable_pairs(4, 4)
print(f"Comparable: {comp}/{total} = {comp/total:.1%}")
# Many pairs are incomparable, which is why O(m+n) is achievable!

Why O(m + n) is Achievable

The existence of incomparable pairs is precisely why we can't simply binary search the entire matrix. However, the staircase search exploits the fact that from corner positions, every comparison resolves a maximally ambiguous situation—eliminating either an entire row or an entire column.

Summary: Understanding Sorted 2D Matrices

We've established the foundational understanding of sorted 2D matrices—the structural knowledge that enables efficient search algorithms.

Key Takeaways

•Row-sorted matrices have each row independently sorted, enabling binary search per row with O(m × log n) total search time.
•Column-sorted matrices have each column independently sorted, enabling binary search per column with O(n × log m) total search time.
•Row-and-column-sorted matrices (Young Tableaux) combine both properties, creating a partial order that enables O(m + n) search via the staircase algorithm.
•The corner elements provide crucial structural information: top-left is always minimum, bottom-right is always maximum in row-and-column-sorted matrices.
•The staircase boundary between values less than and greater than the target is the geometric insight underlying efficient 2D search.
•Always clarify the sorting structure when given a problem—it determines which algorithm applies.

What's Next:

With our understanding of matrix structure established, we're ready to learn the elegant staircase search algorithm—an O(m + n) approach that exploits the row-and-column-sorted property. The next page will walk through this algorithm step by step, proving its correctness and analyzing its efficiency.

Page Complete

You now understand the structural properties of sorted 2D matrices—row-sorted, column-sorted, and both. This foundation is essential for the search algorithms we'll explore next. The distinction between these matrix types directly determines the optimal search strategy.

Data Structures & AlgorithmsSearching Algorithms

Searching in 2D Matrices

LevelIntermediate

Duration90 mins

TopicSearching Algorithms

1 / 4

Row-sorted and Column-sorted Matrices

From Lines to Grids: The 2D Search Challenge

What You Will Learn

The Anatomy of a 2D Matrix

Before diving into sorted properties, let's establish precise terminology for working with 2D matrices.

Definition: A 2D matrix M is a rectangular array of elements arranged in m rows and n columns. We denote the element at row i and column j as M[i][j], where:

i ranges from 0 to m-1 (row index)
j ranges from 0 to n-1 (column index)

This gives us m × n total elements, each uniquely identified by its (row, column) coordinate pair.

matrix_representation.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# A 4×5 matrix (4 rows, 5 columns)
matrix = [
    [10, 20, 30, 40, 50],      # Row 0
    [15, 25, 35, 45, 55],      # Row 1
    [27, 29, 37, 48, 60],      # Row 2
    [32, 33, 39, 50, 62]       # Row 3
]
#    Col 0  1   2   3   4
 
# Access element at row 2, column 3
element = matrix[2][3]  # Returns 48
 
# Matrix dimensions
m = len(matrix)         # 4 rows
n = len(matrix[0])      # 5 columns
total_elements = m * n  # 20 elements

Key Geometric Concepts:

Row: A horizontal sequence of elements. Row i contains elements M[i][0], M[i][1], ..., M[i][n-1].
Column: A vertical sequence of elements. Column j contains elements M[0][j], M[1][j], ..., M[m-1][j].
Diagonal: Elements where row and column indices have a fixed relationship. The main diagonal contains M[0][0], M[1][1], ...
Corner Elements: The four extreme positions—top-left M[0][0], top-right M[0][n-1], bottom-left M[m-1][0], bottom-right M[m-1][n-1].

These structural concepts become critical when analyzing search algorithms, as the sorted property creates predictable relationships between element positions.

Memory Layout Matters

Row-Sorted Matrices — Definition and Properties

A row-sorted matrix is one where each row, considered independently, is sorted in non-decreasing order. This is the simplest form of 2D sorted structure.

Formal Definition:

A matrix M of dimensions m × n is row-sorted if and only if:

For all i ∈ [0, m-1] and j ∈ [0, n-2]:
    M[i][j] ≤ M[i][j+1]

In other words, within any single row, elements increase (or stay equal) as we move from left to right.

row_sorted_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Row-sorted matrix example
# Each row is independently sorted, but columns have no ordering guarantee
 
row_sorted_matrix = [
    [1,  4,  7,  11],    # Row 0: sorted ✓
    [2,  5,  8,  12],    # Row 1: sorted ✓
    [10, 13, 14, 17],    # Row 2: sorted ✓
    [18, 21, 23, 26]     # Row 3: sorted ✓
]
 
# This is also row-sorted (rows don't need inter-row ordering):
another_row_sorted = [
    [50, 60, 70, 80],    # Row 0: sorted ✓
    [5,  10, 15, 20],    # Row 1: sorted ✓ (smaller than row 0!)
    [100, 200, 300, 400] # Row 2: sorted ✓
]
 
def is_row_sorted(matrix):
    """Verify a matrix is row-sorted."""
    for row in matrix:
        for j in range(len(row) - 1):
            if row[j] > row[j + 1]:
                return False
    return True
 
print(is_row_sorted(row_sorted_matrix))      # True
print(is_row_sorted(another_row_sorted))     # True

Properties of Row-Sorted Matrices:

Minimum Element per Row: The leftmost element of each row (M[i][0]) is the minimum in that row.
Maximum Element per Row: The rightmost element of each row (M[i][n-1]) is the maximum in that row.
Binary Search per Row: We can apply standard binary search within any single row, achieving O(log n) search time for that row.
No Cross-Row Guarantees: Crucially, row-sorted structure tells us nothing about the relationship between elements in different rows. M[0][0] might be greater than, equal to, or less than M[1][0].
Total Elements Still Require Row Scans: To find a target in a row-sorted matrix without additional structure, we might need to binary search each row independently.

Row-Sorted Matrix Search Implications
Property	What It Tells Us	Search Implication
M[i][j] ≤ M[i][j+1]	Elements increase left-to-right within rows	Binary search works within each row
No column ordering	Column values can be arbitrary between rows	Cannot eliminate rows based on column values alone
Row min at column 0	First column has each row's minimum	Can skip entire row if target < M[i][0]
Row max at column n-1	Last column has each row's maximum	Can skip entire row if target > M[i][n-1]

Row-Sorted Search Strategy

Column-Sorted Matrices — Definition and Properties

A column-sorted matrix is the vertical analog of row-sorted: each column, considered independently, is sorted in non-decreasing order from top to bottom.

Formal Definition:

A matrix M of dimensions m × n is column-sorted if and only if:

For all i ∈ [0, m-2] and j ∈ [0, n-1]:
    M[i][j] ≤ M[i+1][j]

In other words, within any single column, elements increase (or stay equal) as we move from top to bottom.

column_sorted_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Column-sorted matrix example
# Each column is independently sorted, but rows have no ordering guarantee
 
column_sorted_matrix = [
    [1,  5,  10, 2],     # Column values increase downward
    [3,  7,  15, 8],     
    [6,  12, 18, 14],    
    [9,  20, 25, 22]     
]
# Col 0: 1→3→6→9 ✓
# Col 1: 5→7→12→20 ✓
# Col 2: 10→15→18→25 ✓
# Col 3: 2→8→14→22 ✓
 
# But rows are NOT sorted:
# Row 0: [1, 5, 10, 2] — 10 > 2, not sorted!
 
def is_column_sorted(matrix):
    """Verify a matrix is column-sorted."""
    if not matrix:
        return True
    m, n = len(matrix), len(matrix[0])
    
    for j in range(n):  # For each column
        for i in range(m - 1):  # Check vertical adjacency
            if matrix[i][j] > matrix[i + 1][j]:
                return False
    return True
 
print(is_column_sorted(column_sorted_matrix))  # True
 
def is_row_sorted(matrix):
    """Check if rows are sorted."""
    for row in matrix:
        for j in range(len(row) - 1):
            if row[j] > row[j + 1]:
                return False
    return True
 
print(is_row_sorted(column_sorted_matrix))     # False

Properties of Column-Sorted Matrices:

Minimum Element per Column: The topmost element of each column (M[0][j]) is the minimum in that column.
Maximum Element per Column: The bottommost element of each column (M[m-1][j]) is the maximum in that column.
Binary Search per Column: We can apply binary search within any single column, achieving O(log m) search time for that column.
No Cross-Column Guarantees: Column-sorted structure tells us nothing about relationships across different columns. Adjacent columns may have interleaved or completely disjoint value ranges.
Symmetric to Row-Sorted: All properties of row-sorted matrices have column-sorted analogs, just rotated 90 degrees.

Column-Sorted Search Strategy

Row AND Column Sorted — The Young Tableau Property

Formal Definition:

A matrix M is row-and-column-sorted if and only if:

For all valid i, j:
    M[i][j] ≤ M[i][j+1]     (row-sorted)
    M[i][j] ≤ M[i+1][j]     (column-sorted)

This dual constraint creates powerful structural properties that enable elegant and efficient search algorithms.

young_tableau_example.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Row-and-column-sorted matrix (Young Tableau)
# BOTH rows AND columns are sorted
 
young_tableau = [
    [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]
]
 
# Verify row-sorted: each row increases left-to-right ✓
# Verify column-sorted: each column increases top-to-bottom ✓
 
def is_young_tableau(matrix):
    """Verify a matrix is both row and column sorted."""
    if not matrix:
        return True
    m, n = len(matrix), len(matrix[0])
    
    for i in range(m):
        for j in range(n):
            # Check right neighbor (row-sorted property)
            if j + 1 < n and matrix[i][j] > matrix[i][j + 1]:
                return False
            # Check bottom neighbor (column-sorted property)
            if i + 1 < m and matrix[i][j] > matrix[i + 1][j]:
                return False
    return True
 
print(is_young_tableau(young_tableau))  # True
 
# Visualizing the structure:
# Each element is ≤ its right neighbor AND ≤ its bottom neighbor
# This creates a "flow" from top-left (minimum) to bottom-right (maximum)

Critical Properties of Row-and-Column-Sorted Matrices:

1. Global Minimum and Maximum:

The top-left element M[0][0] is the global minimum of the entire matrix.
The bottom-right element M[m-1][n-1] is the global maximum of the entire matrix.

2. Monotonic Paths:

Any path moving only right and/or down encounters elements in non-decreasing order.
Any path moving only left and/or up encounters elements in non-increasing order.

3. The Staircase Property:

From any position, moving right increases or maintains the value.
From any position, moving down increases or maintains the value.
This creates a "monotonic landscape" that search algorithms can exploit.

4. Corner Information:

Top-right corner M[0][n-1]: Maximum of first row, minimum of last column.
Bottom-left corner M[m-1][0]: Maximum of first column, minimum of last row.
These corners provide crucial decision points for search algorithms.

The Power of Dual Sorting

Visualizing the Sorted Structure

Understanding sorted 2D matrices becomes much clearer through visualization. Let's explore how the sorting constraints create geometric patterns in the value landscape.

The Value Gradient:

In a row-and-column-sorted matrix, imagine each cell's value as its elevation on a 3D terrain. The dual sorting property creates a surface that:

Rises as you move right (row-sorted)
Rises as you move down (column-sorted)
Has its lowest point at the top-left corner
Has its highest point at the bottom-right corner

This creates a "ramp" that ascends from the top-left to the bottom-right.

value_landscape.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Visualizing the value constraints in a row-and-column-sorted matrix
 
matrix = [
    [1,   4,   7,  11],
    [2,   5,   8,  12],
    [3,   6,   9,  16],
    [10,  13,  14,  17]
]
 
def visualize_constraints(matrix):
    """
    Show how each element relates to its neighbors.
    
    For element at (i, j):
    - LEFT neighbor (if exists): smaller or equal
    - RIGHT neighbor (if exists): larger or equal
    - UP neighbor (if exists): smaller or equal
    - DOWN neighbor (if exists): larger or equal
    """
    m, n = len(matrix), len(matrix[0])
    
    for i in range(m):
        for j in range(n):
            val = matrix[i][j]
            constraints = []
            
            # Check relationships with neighbors
            if j > 0:
                constraints.append(f"{matrix[i][j-1]} ≤ {val}")  # Left
            if j < n - 1:
                constraints.append(f"{val} ≤ {matrix[i][j+1]}")  # Right
            if i > 0:
                constraints.append(f"{matrix[i-1][j]} ≤ {val}")  # Up
            if i < m - 1:
                constraints.append(f"{val} ≤ {matrix[i+1][j]}")  # Down
            
            print(f"M[{i}][{j}] = {val}: {', '.join(constraints)}")
        print()
 
# The constraint network creates a partial ordering of all elements
# This partial order is what enables efficient search

Contour Lines and Search Regions:

Another powerful visualization is to think of contour lines—imaginary boundaries connecting cells of equal value. In a row-and-column-sorted matrix:

Values less than target: Form a connected region anchored at the top-left corner.
Values greater than target: Form a connected region anchored at the bottom-right corner.
The boundary: The transition between "less than" and "greater than" regions forms a staircase pattern.

This staircase boundary is exactly what the staircase search algorithm (covered in the next page) exploits to achieve O(m + n) search time.

Converting Mermaid diagram...

The Staircase Boundary

Distinguishing Matrix Types in Practice

When facing a 2D matrix search problem, the first critical step is identifying the sorting structure. Different matrix types require different algorithms and achieve different complexities.

Quick Classification Algorithm:

matrix_classifier.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def classify_matrix(matrix):
    """
    Classify a matrix by its sorting properties.
    
    Returns one of:
    - 'fully_sorted': Can be treated as a 1D sorted array
    - 'row_and_column_sorted': Young Tableau structure
    - 'row_sorted': Only rows are individually sorted
    - 'column_sorted': Only columns are individually sorted
    - 'unsorted': No sorted structure
    """
    if not matrix or not matrix[0]:
        return 'empty'
    
    m, n = len(matrix), len(matrix[0])
    
    # Check row-sorted property
    row_sorted = True
    for i in range(m):
        for j in range(n - 1):
            if matrix[i][j] > matrix[i][j + 1]:
                row_sorted = False
                break
        if not row_sorted:
            break
    
    # Check column-sorted property
    col_sorted = True
    for j in range(n):
        for i in range(m - 1):
            if matrix[i][j] > matrix[i + 1][j]:
                col_sorted = False
                break
        if not col_sorted:
            break
    
    # Check fully sorted (each row continues from previous)
    fully_sorted = row_sorted  # Must be row-sorted first
    if fully_sorted:
        for i in range(m - 1):
            if matrix[i][n - 1] > matrix[i + 1][0]:
                fully_sorted = False
                break
    
    # Classify
    if fully_sorted:
        return 'fully_sorted'
    elif row_sorted and col_sorted:
        return 'row_and_column_sorted'
    elif row_sorted:
        return 'row_sorted'
    elif col_sorted:
        return 'column_sorted'
    else:
        return 'unsorted'
 
# Examples
print(classify_matrix([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]))  # 'fully_sorted'
 
print(classify_matrix([
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9]
]))  # 'row_and_column_sorted'
 
print(classify_matrix([
    [10, 20, 30],
    [1, 2, 3],
    [100, 200, 300]
]))  # 'row_sorted'

Matrix Types and Their Search Implications
Matrix Type	Structure	Best Search Algorithm	Time Complexity
Fully Sorted	Row ends ≤ next row start	Single binary search (treat as 1D)	O(log(m × n))
Row-and-Column Sorted	Rows sorted, columns sorted	Staircase search	O(m + n)
Row-Sorted Only	Each row independently sorted	Binary search per row	O(m × log n)
Column-Sorted Only	Each column independently sorted	Binary search per column	O(n × log m)
Unsorted	No sorting guarantees	Brute force scan	O(m × n)

Problem Statement Precision

Real-World Examples of Sorted Matrices

Sorted 2D matrices aren't just theoretical constructs—they appear naturally in many practical applications:

1. Calendar/Schedule Data:

Rows represent days, columns represent time slots
Appointments are sorted by date (rows) and time (columns)
Finding available slots is a 2D search problem

2. Geographic Grid Data:

Elevation maps where values increase predictably
Temperature gradients with latitude (rows) and altitude (columns)
Searching for specific conditions in climate models

3. Database Indexes:

Composite indexes on two sorted columns
Range queries that leverage the sorted structure
B-tree variations for 2D data

4. Image Processing:

Integral images (summed-area tables) are row-and-column sorted
Used for efficient feature computation
Enables O(1) rectangular sum queries

5. Spreadsheet Applications:

Sorted data tables with multiple sort keys
Finding entries in sorted rows with sorted column headers
Excel's data lookup functions exploit this structure

Classic Interview Problems

•Search a 2D Matrix (LeetCode 74): Matrix is fully sorted—use single binary search
•Search a 2D Matrix II (LeetCode 240): Row-and-column sorted—use staircase search
•Kth Smallest Element in a Sorted Matrix (LeetCode 378): Uses heap with matrix structure
•Count Negative Numbers in a Sorted Matrix (LeetCode 1351): Exploits staircase boundary
•Find a Peak Element II (LeetCode 1901): Uses binary reduction on sorted structure

Interview Strategy

Mathematical Foundations

Understanding the mathematical structure of sorted matrices provides deeper insight into why certain search algorithms work.

Partial Ordering:

A row-and-column-sorted matrix defines a partial order on its elements. Given two positions (i₁, j₁) and (i₂, j₂):

If i₁ ≤ i₂ AND j₁ ≤ j₂, then M[i₁][j₁] ≤ M[i₂][j₂]

Lattice Structure:

The set of matrix positions forms a lattice under the coordinate-wise comparison:

Join (⊔): (i₁, j₁) ⊔ (i₂, j₂) = (max(i₁, i₂), max(j₁, j₂))
Meet (⊓): (i₁, j₁) ⊓ (i₂, j₂) = (min(i₁, i₂), min(j₁, j₂))

This lattice structure means:

There's a unique minimum position: (0, 0)
There's a unique maximum position: (m-1, n-1)
Any two positions have well-defined upper and lower bounds

partial_order_analysis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def can_compare(pos1, pos2):
    """
    Determine if two positions are comparable in the partial order.
    
    (i1, j1) ≤ (i2, j2) iff i1 ≤ i2 AND j1 ≤ j2
    
    Two positions are comparable if one dominates the other.
    """
    i1, j1 = pos1
    i2, j2 = pos2
    
    # pos1 ≤ pos2
    if i1 <= i2 and j1 <= j2:
        return True, f"{pos1} ≤ {pos2}"
    
    # pos2 ≤ pos1
    if i2 <= i1 and j2 <= j1:
        return True, f"{pos2} ≤ {pos1}"
    
    # Incomparable
    return False, f"{pos1} and {pos2} are incomparable"
 
# Examples
print(can_compare((0, 0), (2, 2)))  # True, (0,0) ≤ (2,2)
print(can_compare((0, 2), (2, 0)))  # False, incomparable
print(can_compare((1, 1), (1, 3)))  # True, (1,1) ≤ (1,3)
 
# In a row-and-column sorted matrix:
# If can_compare returns True with pos1 ≤ pos2, then M[pos1] ≤ M[pos2]
# If positions are incomparable, M[pos1] and M[pos2] could be in any order
 
def count_comparable_pairs(m, n):
    """Count how many pairs of positions are comparable."""
    total_pairs = (m * n) * (m * n - 1) // 2
    comparable = 0
    
    for i1 in range(m):
        for j1 in range(n):
            for i2 in range(m):
                for j2 in range(n):
                    if (i1, j1) < (i2, j2):  # Avoid double counting
                        result, _ = can_compare((i1, j1), (i2, j2))
                        if result:
                            comparable += 1
    
    return comparable, total_pairs
 
# For a 4×4 matrix:
comp, total = count_comparable_pairs(4, 4)
print(f"Comparable: {comp}/{total} = {comp/total:.1%}")
# Many pairs are incomparable, which is why O(m+n) is achievable!

Why O(m + n) is Achievable

Summary: Understanding Sorted 2D Matrices

We've established the foundational understanding of sorted 2D matrices—the structural knowledge that enables efficient search algorithms.

Key Takeaways

•Row-sorted matrices have each row independently sorted, enabling binary search per row with O(m × log n) total search time.
•Column-sorted matrices have each column independently sorted, enabling binary search per column with O(n × log m) total search time.
•Row-and-column-sorted matrices (Young Tableaux) combine both properties, creating a partial order that enables O(m + n) search via the staircase algorithm.
•The corner elements provide crucial structural information: top-left is always minimum, bottom-right is always maximum in row-and-column-sorted matrices.
•The staircase boundary between values less than and greater than the target is the geometric insight underlying efficient 2D search.
•Always clarify the sorting structure when given a problem—it determines which algorithm applies.

What's Next:

Page Complete