Find a value in a grid sorted row after row

Searching sorted data Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
grid = [[1, 3, 5], [7, 9, 11], [13, 15, 17]]
cols = len(grid[0])
k = 7
print(grid[k // cols][k % cols], k // cols, k % cols)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 15 2 1

Right: position 7 is row 2, column 1.

Dividing by the column count turns one position into a row and column, which lets binary search treat the grid as a single list.

Why not the others?
  • B 9 1 1. Row 1 covers positions 3 to 5.
  • C 13 2 0. 7 % 3 is 1, so it is the second item of row 2.

30-second answer

Read the grid as one sorted list of R·C values: position k is row k // C, column k % C. Binary search that virtual list in O(log(R·C)) time with O(1) extra memory.

Practise saying it · 30 s. No recording, just a timer

Explain binary search on a row-sorted grid.

Say your answer out loud, then check which of these points you covered:

  • Treat it as one list
  • Row k // C, column k % C
  • O(log(R·C))

Deep dive

Two searches (first the row, then within the row) give the same O(log R + log C).

If only rows and columns are each sorted (without the row-after-row rule), start at the top-right corner and walk: O(R + C).

Index arithmetic avoids flattening the grid, which would cost O(R·C) memory.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def grid_has(grid: list[list[int]], target: int) -> bool:
    if not grid or not grid[0]:
        return False
    cols = len(grid[0])
    lo, hi = 0, len(grid) * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = grid[mid // cols][mid % cols]
        if val == target:
            return True
        if val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Common mistakes

  • Flattening the grid into a new list first.
  • Mixing up // and % with the number of columns.

Senior take & follow-ups

Explain the index mapping with one example such as k = 7 in a 3-column grid.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if rows and columns are sorted but rows overlap?

    Show hint

    Staircase walk from the top-right corner, O(R + C).

  2. How do you return the position?

    Show hint

    Return (k // C, k % C) for the matching k.

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.