7a:T46a,# 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)) # False7b:T469,# 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)7c:T53b,# 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 search7d:T75c,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'7e:T674,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!72:{"json":{"id":"seed_026cdedefbfd1e26afe87a97de085599","slug":"searching-in-2d-matrices","category":"Data Structures & Algorithms","topic":"Searching Algorithms","title":"Searching in 2D Matrices","description":"Master the art of searching in two-dimensional matrices. Learn to exploit sorted structure in row-sorted, column-sorted, and fully sorted matrices. Understand the staircase search algorithm, binary search adaptations, and time complexity analysis for each approach.","difficulty":"INTERMEDIATE","estimatedMinutes":90,"pages":[{"id":"seed_136afe7cba5b5e3120b4a1c4d94339d2","title":"Row-sorted and Column-sorted Matrices","order":0,"content":[{"id":"opening-hook","title":"From Lines to Grids: The 2D Search Challenge","content":[{"data":{"content":"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?\n\n**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.\n\nThis 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."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"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.","variant":"info"},"type":"callout"}]},{"id":"anatomy-of-2d-matrix","title":"The Anatomy of a 2D Matrix","content":[{"data":{"content":"Before diving into sorted properties, let's establish precise terminology for working with 2D matrices.\n\n**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:\n- `i` ranges from `0` to `m-1` (row index)\n- `j` ranges from `0` to `n-1` (column index)\n\nThis gives us `m × n` total elements, each uniquely identified by its (row, column) coordinate pair."},"type":"text"},{"data":{"code":"# A 4×5 matrix (4 rows, 5 columns)\nmatrix = [\n [10, 20, 30, 40, 50], # Row 0\n [15, 25, 35, 45, 55], # Row 1\n [27, 29, 37, 48, 60], # Row 2\n [32, 33, 39, 50, 62] # Row 3\n]\n# Col 0 1 2 3 4\n\n# Access element at row 2, column 3\nelement = matrix[2][3] # Returns 48\n\n# Matrix dimensions\nm = len(matrix) # 4 rows\nn = len(matrix[0]) # 5 columns\ntotal_elements = m * n # 20 elements","fileName":"matrix_representation.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**Key Geometric Concepts:**\n\n- **Row:** A horizontal sequence of elements. Row `i` contains elements `M[i][0], M[i][1], ..., M[i][n-1]`.\n- **Column:** A vertical sequence of elements. Column `j` contains elements `M[0][j], M[1][j], ..., M[m-1][j]`.\n- **Diagonal:** Elements where row and column indices have a fixed relationship. The main diagonal contains `M[0][0], M[1][1], ...`\n- **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]`.\n\nThese structural concepts become critical when analyzing search algorithms, as the sorted property creates predictable relationships between element positions."},"type":"text"},{"data":{"icon":"Info","title":"Memory Layout Matters","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"row-sorted-matrices","title":"Row-Sorted Matrices — Definition and Properties","content":[{"data":{"content":"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.\n\n**Formal Definition:**\n\nA matrix `M` of dimensions `m × n` is **row-sorted** if and only if:\n\n```\nFor all i ∈ [0, m-1] and j ∈ [0, n-2]:\n M[i][j] ≤ M[i][j+1]\n```\n\nIn other words, within any single row, elements increase (or stay equal) as we move from left to right."},"type":"text"},{"data":{"code":"# Row-sorted matrix example\n# Each row is independently sorted, but columns have no ordering guarantee\n\nrow_sorted_matrix = [\n [1, 4, 7, 11], # Row 0: sorted ✓\n [2, 5, 8, 12], # Row 1: sorted ✓\n [10, 13, 14, 17], # Row 2: sorted ✓\n [18, 21, 23, 26] # Row 3: sorted ✓\n]\n\n# This is also row-sorted (rows don't need inter-row ordering):\nanother_row_sorted = [\n [50, 60, 70, 80], # Row 0: sorted ✓\n [5, 10, 15, 20], # Row 1: sorted ✓ (smaller than row 0!)\n [100, 200, 300, 400] # Row 2: sorted ✓\n]\n\ndef is_row_sorted(matrix):\n \"\"\"Verify a matrix is row-sorted.\"\"\"\n for row in matrix:\n for j in range(len(row) - 1):\n if row[j] > row[j + 1]:\n return False\n return True\n\nprint(is_row_sorted(row_sorted_matrix)) # True\nprint(is_row_sorted(another_row_sorted)) # True","fileName":"row_sorted_example.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**Properties of Row-Sorted Matrices:**\n\n1. **Minimum Element per Row:** The leftmost element of each row (`M[i][0]`) is the minimum in that row.\n\n2. **Maximum Element per Row:** The rightmost element of each row (`M[i][n-1]`) is the maximum in that row.\n\n3. **Binary Search per Row:** We can apply standard binary search within any single row, achieving O(log n) search time for that row.\n\n4. **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]`.\n\n5. **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."},"type":"text"},{"data":{"rows":[["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]"]],"caption":"Row-Sorted Matrix Search Implications","headers":["Property","What It Tells Us","Search Implication"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"Row-Sorted Search Strategy","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"column-sorted-matrices","title":"Column-Sorted Matrices — Definition and Properties","content":[{"data":{"content":"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.\n\n**Formal Definition:**\n\nA matrix `M` of dimensions `m × n` is **column-sorted** if and only if:\n\n```\nFor all i ∈ [0, m-2] and j ∈ [0, n-1]:\n M[i][j] ≤ M[i+1][j]\n```\n\nIn other words, within any single column, elements increase (or stay equal) as we move from top to bottom."},"type":"text"},{"data":{"code":"$7a","fileName":"column_sorted_example.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**Properties of Column-Sorted Matrices:**\n\n1. **Minimum Element per Column:** The topmost element of each column (`M[0][j]`) is the minimum in that column.\n\n2. **Maximum Element per Column:** The bottommost element of each column (`M[m-1][j]`) is the maximum in that column.\n\n3. **Binary Search per Column:** We can apply binary search within any single column, achieving O(log m) search time for that column.\n\n4. **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.\n\n5. **Symmetric to Row-Sorted:** All properties of row-sorted matrices have column-sorted analogs, just rotated 90 degrees."},"type":"text"},{"data":{"icon":"Info","title":"Column-Sorted Search Strategy","content":"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).","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"row-and-column-sorted","title":"Row AND Column Sorted — The Young Tableau Property","content":[{"data":{"content":"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**.\n\n**Formal Definition:**\n\nA matrix `M` is **row-and-column-sorted** if and only if:\n\n```\nFor all valid i, j:\n M[i][j] ≤ M[i][j+1] (row-sorted)\n M[i][j] ≤ M[i+1][j] (column-sorted)\n```\n\nThis dual constraint creates powerful structural properties that enable elegant and efficient search algorithms."},"type":"text"},{"data":{"code":"$7b","fileName":"young_tableau_example.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**Critical Properties of Row-and-Column-Sorted Matrices:**\n\n**1. Global Minimum and Maximum:**\n- The **top-left element** `M[0][0]` is the global minimum of the entire matrix.\n- The **bottom-right element** `M[m-1][n-1]` is the global maximum of the entire matrix.\n\n**2. Monotonic Paths:**\n- Any path moving only right and/or down encounters elements in non-decreasing order.\n- Any path moving only left and/or up encounters elements in non-increasing order.\n\n**3. The Staircase Property:**\n- From any position, moving right increases or maintains the value.\n- From any position, moving down increases or maintains the value.\n- This creates a \"monotonic landscape\" that search algorithms can exploit.\n\n**4. Corner Information:**\n- **Top-right corner** `M[0][n-1]`: Maximum of first row, minimum of last column.\n- **Bottom-left corner** `M[m-1][0]`: Maximum of first column, minimum of last row.\n- These corners provide crucial decision points for search algorithms."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Power of Dual Sorting","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"visualizing-sorted-structure","title":"Visualizing the Sorted Structure","content":[{"data":{"content":"Understanding sorted 2D matrices becomes much clearer through visualization. Let's explore how the sorting constraints create geometric patterns in the value landscape.\n\n**The Value Gradient:**\n\nIn 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:\n- Rises as you move right (row-sorted)\n- Rises as you move down (column-sorted)\n- Has its lowest point at the top-left corner\n- Has its highest point at the bottom-right corner\n\nThis creates a \"ramp\" that ascends from the top-left to the bottom-right."},"type":"text"},{"data":{"code":"$7c","fileName":"value_landscape.py","showLineNumbers":true},"type":"code"},{"data":{"content":"**Contour Lines and Search Regions:**\n\nAnother powerful visualization is to think of **contour lines**—imaginary boundaries connecting cells of equal value. In a row-and-column-sorted matrix:\n\n1. **Values less than target:** Form a connected region anchored at the top-left corner.\n\n2. **Values greater than target:** Form a connected region anchored at the bottom-right corner.\n\n3. **The boundary:** The transition between \"less than\" and \"greater than\" regions forms a staircase pattern.\n\nThis staircase boundary is exactly what the staircase search algorithm (covered in the next page) exploits to achieve O(m + n) search time."},"type":"text"},{"data":{"height":"350px","mermaidSyntax":"graph TD\n subgraph \"Row-and-Column Sorted Matrix\"\n subgraph \"Search for target = 9\"\n A[\"1 < 9\"] --> B[\"4 < 9\"]\n B --> C[\"7 < 9\"]\n C --> D[\"11 > 9\"]\n A --> E[\"2 < 9\"]\n E --> F[\"5 < 9\"]\n F --> G[\"8 < 9\"]\n G --> H[\"12 > 9\"]\n E --> I[\"3 < 9\"]\n I --> J[\"6 < 9\"]\n J --> K[\"9 = 9 ✓\"]\n end\n end\n \n style K fill:#22c55e,color:#fff"},"type":"mermaid-excalidraw"},{"data":{"icon":"Info","title":"The Staircase Boundary","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"distinguishing-matrix-types","title":"Distinguishing Matrix Types in Practice","content":[{"data":{"content":"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.\n\n**Quick Classification Algorithm:**"},"type":"text"},{"data":{"code":"$7d","fileName":"matrix_classifier.py","showLineNumbers":true},"type":"code"},{"data":{"rows":[["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)"]],"caption":"Matrix Types and Their Search Implications","headers":["Matrix Type","Structure","Best Search Algorithm","Time Complexity"]},"type":"table"},{"data":{"icon":"AlertCircle","title":"Problem Statement Precision","content":"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.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"real-world-examples","title":"Real-World Examples of Sorted Matrices","content":[{"data":{"content":"Sorted 2D matrices aren't just theoretical constructs—they appear naturally in many practical applications:\n\n**1. Calendar/Schedule Data:**\n- Rows represent days, columns represent time slots\n- Appointments are sorted by date (rows) and time (columns)\n- Finding available slots is a 2D search problem\n\n**2. Geographic Grid Data:**\n- Elevation maps where values increase predictably\n- Temperature gradients with latitude (rows) and altitude (columns)\n- Searching for specific conditions in climate models\n\n**3. Database Indexes:**\n- Composite indexes on two sorted columns\n- Range queries that leverage the sorted structure\n- B-tree variations for 2D data\n\n**4. Image Processing:**\n- Integral images (summed-area tables) are row-and-column sorted\n- Used for efficient feature computation\n- Enables O(1) rectangular sum queries\n\n**5. Spreadsheet Applications:**\n- Sorted data tables with multiple sort keys\n- Finding entries in sorted rows with sorted column headers\n- Excel's data lookup functions exploit this structure"},"type":"text"},{"data":{"items":["**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"],"title":{"icon":"Target","text":"Classic Interview Problems","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"Lightbulb","title":"Interview Strategy","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"mathematical-foundations","title":"Mathematical Foundations","content":[{"data":{"content":"Understanding the mathematical structure of sorted matrices provides deeper insight into why certain search algorithms work.\n\n**Partial Ordering:**\n\nA row-and-column-sorted matrix defines a **partial order** on its elements. Given two positions (i₁, j₁) and (i₂, j₂):\n\n```\nIf i₁ ≤ i₂ AND j₁ ≤ j₂, then M[i₁][j₁] ≤ M[i₂][j₂]\n```\n\nThis 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.\n\n**Lattice Structure:**\n\nThe set of matrix positions forms a lattice under the coordinate-wise comparison:\n- Join (⊔): (i₁, j₁) ⊔ (i₂, j₂) = (max(i₁, i₂), max(j₁, j₂))\n- Meet (⊓): (i₁, j₁) ⊓ (i₂, j₂) = (min(i₁, i₂), min(j₁, j₂))\n\nThis lattice structure means:\n- There's a unique minimum position: (0, 0)\n- There's a unique maximum position: (m-1, n-1)\n- Any two positions have well-defined upper and lower bounds"},"type":"text"},{"data":{"code":"$7e","fileName":"partial_order_analysis.py","showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"Why O(m + n) is Achievable","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"summary-whats-next","title":"Summary: Understanding Sorted 2D Matrices","content":[{"data":{"content":"We've established the foundational understanding of sorted 2D matrices—the structural knowledge that enables efficient search algorithms."},"type":"text"},{"data":{"type":"ordered","items":["**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."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nWith 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."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_924715487c32e21045e71e930d1387aa","title":"Staircase Search Algorithm","order":1,"content":null,"isLocked":true},{"id":"seed_8a84be737f2f7588486b7fb8f7d674b0","title":"Fully Sorted Matrix as 1D Array","order":2,"content":null,"isLocked":true},{"id":"seed_1cd0b57601a094a5bbba1dae57a1f614","title":"Time Complexity for Each Approach","order":3,"content":null,"isLocked":true}]}}