0768MediumArrayHash TableMatrix

First Filled Shelf Row Or Column

Tracked in this browser only

Trains the technique from

LeetCode 2661First Completely Painted Row or Column

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A stockroom wall is an m x n grid of shelf slots. board[r][c] holds the bin ticket assigned to the slot in row r, column c, and every ticket on the wall is different.

A picker works through order, which lists every ticket on the wall exactly once. Each ticket called fills the one slot carrying it.

Return the 0-based index into order of the call after which some row is entirely filled or some column is entirely filled, whichever happens first. A row is entirely filled when all n of its slots are filled, and a column when all m of its slots are filled.

Examples

Example 1

Input: order = [5, 1, 3, 6, 2, 4], board = [[5, 2], [1, 6], [3, 4]]
Output: 2

Tickets 5, 1 and 3 sit in column 0 of the three rows, so after the third call that column is completely filled. No row is complete at that point, since each row still has one empty slot.

Example 2

Input: order = [4, 9, 6, 1, 8, 3, 5, 2, 7], board = [[4, 9, 6], [7, 3, 1], [8, 5, 2]]
Output: 2

The first three calls are exactly the three tickets of row 0, so that row is full after the call at index 2.

Example 3

Input: order = [2, 5, 1, 6, 3, 4], board = [[1, 2, 3], [4, 5, 6]]
Output: 1

Ticket 2 sits in row 0, column 1 and ticket 5 in row 1, column 1, so the second call leaves column 1 filled top to bottom. Each row is three slots wide and still has gaps.

Constraints

1 <= board.length <= 10^5
1 <= board[i].length <= 10^5
1 <= order[i] <= 10^5
1 <= board[i][j] <= 10^5
Writing m for board.length and n for board[i].length, order.length == m * n and 1 <= m * n <= 10^5.
Every row of board has the same length.
order and board each hold the integers 1 through m * n exactly once.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def first_full_line(order: list[int], board: list[list[int]]) -> int:

Java

public int firstFullLine(int[] order, int[][] board)

The intended approach

Time O(m n): one pass to index the wall and one pass over the calls.Space O(m n) for the ticket table.

Build a table from ticket to its slot coordinates in one pass over the wall. Then walk `order` keeping one running tally per row and one per column: each call bumps exactly one of each. A row is done the moment its tally reaches the column count, and a column the moment its tally reaches the row count, so the first call that trips either test is the answer.

Pythonentry point: first_full_line

def first_full_line(order, board):
    # Time O(m n), space O(m n) for the position table.
    rows = len(board)
    cols = len(board[0])
    at = {}
    for r in range(rows):
        line = board[r]
        for c in range(cols):
            at[line[c]] = (r, c)
    row_hits = [0] * rows
    col_hits = [0] * cols
    for i in range(len(order)):
        r, c = at[order[i]]
        row_hits[r] += 1
        col_hits[c] += 1
        if row_hits[r] == cols or col_hits[c] == rows:
            return i
    return -1

The obvious version

Keep a grid of filled flags. After each call, find the ticket by scanning the whole wall, mark its slot, then re-scan every row and every column looking for one that is completely filled. Costs the wall area per call.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_first_full_line(order, board):
    rows = len(board)
    cols = len(board[0])
    marked = [[False] * cols for _ in range(rows)]
    for i in range(len(order)):
        want = order[i]
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == want:
                    marked[r][c] = True
        for r in range(rows):
            if all(marked[r]):
                return i
        for c in range(cols):
            full = True
            for r in range(rows):
                if not marked[r][c]:
                    full = False
                    break
            if full:
                return i
    return -1

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in