First Fully Painted Line

Medium

An m × n table grid holds every number from 1 to m · n exactly once. The list order holds the same numbers in some other order. Walk through order from the start: at step k, paint the cell of the table that contains order[k]. Return the smallest step k (0-based) after which some row or some column of the table is completely painted.

Example 1

order=[4, 1, 6, 2, 5, 3], grid=[[1, 2, 3], [4, 5, 6]] → 1

Step 0 paints 4 and step 1 paints 1. Column 0 holds only 1 and 4, so it is complete after step 1.

Example 2

order=[2, 3, 1, 4], grid=[[1, 2], [3, 4]] → 2

After steps 0 and 1 the cells 2 and 3 are painted, in different rows and columns. Step 2 paints 1, completing the row [1, 2].

Example 3

order=[1], grid=[[1]] → 0

Constraints

1 ≤ m, n
1 ≤ m · n ≤ 10⁵
grid and order each contain every number from 1 to m · n exactly once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Matrix

Similar problems

Sudoku Board Without Clashes Medium Zero Out the Crosses Medium Multiply Mostly-Zero Matrices Medium Lonely Dark Pixels Medium Dark Pixels in Twin Rows Medium

Input

order=[4, 1, 6, 2, 5, 3], grid=[[1, 2, 3], [4, 5, 6]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 54 tests on the server, hidden ones included.