Show problems as
Classic problem #2661MediumArrayHash TableMatrix

First Completely Painted Row or Column

Real-world version: First Filled Shelf Row Or Column
Tracked in this browser only
Read First Completely Painted Row or Column on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def first_full_line(order: list[int], board: list[list[int]]) -> int:
Java
public int firstFullLine(int[] order, int[][] board)

More on the same topics