Staircase price board

The price board is sorted twice over — along every row and down every column — but not as one long list. Where you start the walk decides whether that ordering helps.

The problem

A theatre prices each seat on a grid. board[r][c] is the price of seat c in row r. Prices rise from the aisle toward the centre of a row and rise again as the seats near the stage, so rows are non-decreasing left to right and columns top to bottom. Nothing stronger holds: read row after row and the prices are not sorted.

A patron names an exact amount; say whether some seat costs it. The board runs to a thousand rows by a thousand seats and the window answers thousands of patrons an hour, so reading every cell is too slow.

Input. board — rows of integers, non-decreasing along rows and down columns. price — the amount the patron names.

Output. True if some seat costs exactly price, False otherwise.

Example.

board = [[ 4,  8, 12, 18],
         [ 6, 10, 15, 22],
         [ 9, 14, 19, 27],
         [13, 20, 25, 31]], price = 15   ->  True

Seat 2 in row 1 costs 15.

A second example, showing why the board is not one sorted list:

board = [[ 4,  8, 12, 18],
         [ 6, 10, 15, 22],
         [ 9, 14, 19, 27],
         [13, 20, 25, 31]], price = 21   ->  False

21 sits between 20 and 25 in the last row and 19 and 27 in the row above, so it is nowhere. Row 1 also starts at 6, below where row 0 ended at 18: flattening gives an unsorted sequence.

Constraints.

• 1 <= len(board) <= 10^3 and 1 <= len(board[0]) <= 10^3
• 0 <= board[r][c] <= 10^9, values may repeat
• every row is non-decreasing; every column is non-decreasing

Hints

Approach

Brute force

Compare every cell: 10⁶ prices per patron. Binary searching each row is better at O(R log C), about 10⁴ comparisons, but it uses the row order and ignores the column order completely.

The insight

Start at the top-right corner, the only cell that is simultaneously the largest in its row and the smallest in its column, so one comparison always deletes a whole row or a whole column.

Sit at (r, c), rows above and columns right already discarded. If board[r][c] exceeds the price, the rest of column c is at or above it — columns rise downward — so the column goes and c moves left. If it is under the price, the rest of row r is at or below it, since c is the rightmost column left, so the row goes and r moves down. Each step deletes a line: binary search's discipline on a staircase instead of an interval.

Algorithm

1. Set r = 0 and c = len(board[0]) - 1.
2. While r is a valid row and c is a valid column:
3. If board[r][c] == price, return True.
4. If board[r][c] > price, move left: c -= 1.
5. Otherwise move down: r += 1.
6. Return False once the walk leaves the board.

Complexity

Time O(R + C) — each step drops a row or a column: at most 2000 comparisons on the largest board, against 10⁶ for the scan. Space O(1); two indices.

Solution

"""Staircase price board — walk the doubly sorted grid from its top-right corner."""


def solve(board, price):
    rows, cols = len(board), len(board[0])
    r, c = 0, cols - 1
    while r < rows and c >= 0:
        # Invariant: rows above r and columns right of c cannot hold the price.
        seat = board[r][c]
        if seat == price:
            return True
        if seat > price:
            c -= 1                        # column c only grows downward, so drop it
        else:
            r += 1                        # row r only shrinks leftward, so drop it
    return False


BOARD = [
    [4, 8, 12, 18],
    [6, 10, 15, 22],
    [9, 14, 19, 27],
    [13, 20, 25, 31],
]

TESTS = [
    ((BOARD, 15), True),
    ((BOARD, 21), False),
    ((BOARD, 4), True),
    ((BOARD, 31), True),
    ((BOARD, 3), False),
    ((BOARD, 40), False),
    (([[7]], 7), True),
    (([[7]], 2), False),
    (([[2, 2], [2, 2]], 2), True),
    (([[1, 2], [3, 4]], 3), True),
]

Pitfalls

• Starting at the top-left or bottom-right corner. Both directions increase there, so a mismatch leaves two live moves and the walk has to branch.
• Flattening the board and binary searching it. Rows are sorted, so it looks safe — but row 1 starts at 6 after row 0 ended at 18, and the flattened search reports False for 15, a price that is really there.
• Stepping down and left at once. The diagonal skips cells nothing ruled out.
• Forgetting a bound. c falls below 0 when the price is under every seat and r passes the last row when it is above them; both must end the loop rather than index the board.

Variants

• Toll plaza minute — the same reasoning in one dimension, hunting a boundary rather than a value.
• Sprinkler square — another grid, halved by size rather than walked.