All problems

Minimum Domino Rotations for Equal Row

Medium · greedy

A row of n dominoes lies on a table. Domino i shows the number tops[i] on its upper half and the number bottoms[i] on its lower half.

One rotation turns a single domino upside down, which swaps its upper and lower numbers. You may rotate any domino, any number of times.

Return the smallest number of rotations after which all upper halves show the same number, or all lower halves show the same number (either row will do). If neither is possible, return -1.

Examples

Example 1

Input: tops = [3, 5, 3, 3, 8], bottoms = [5, 3, 5, 8, 3]

Output: 2

Rotate the dominoes at positions 1 and 4. The top row becomes 3, 3, 3, 3, 3.

Example 2

Input: tops = [4, 4, 4], bottoms = [4, 4, 4]

Output: 0

Both rows are already equal.

Example 3

Input: tops = [1, 2, 3], bottoms = [2, 3, 1]

Output: -1

No number appears on every domino, so no row can be made equal.

Constraints