Flip Tiles for a Uniform Row

Medium

A row of tiles lies on the table, each with two halves holding numbers from 1 to 6. Tile i shows upper[i] on its top half and lower[i] on its bottom half. You may flip any tile, which swaps its top and bottom numbers. The goal is to make every number in the top row the same, or every number in the bottom row the same. Return the smallest number of flips that achieves this, or -1 if it is impossible.

Example 1

upper=[4, 1, 4, 4], lower=[2, 4, 3, 1] → 1

Flip the second tile and the top row is all 4s.

Example 2

upper=[2, 6, 2], lower=[6, 2, 6] → 1

Flipping the second tile puts all 2s on top and all 6s at the bottom; one flip is enough.

Example 3

upper=[1, 2, 3], lower=[3, 1, 2] → -1

No number appears on every tile, so the answer is -1.

Constraints

2 ≤ len(upper) ≤ 2·10⁴
len(lower) = len(upper)
1 ≤ upper[i], lower[i] ≤ 6

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array

Similar problems

Two Boards Holding Water Medium Fewest Jumps to the End Medium Reach the Last Cell Medium As Many Trades as You Like Medium Where to Start the Lap Medium

Input

upper=[4, 1, 4, 4], lower=[2, 4, 3, 1]

Expected

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