Minimum Domino Rotations Solution for Google

Company: Google · Difficulty: Medium · Topics: Array, Greedy

Problem Statement

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)

We may rotate the ith domino, so that tops[i] and bottoms[i] swap values.

Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same.

If it cannot be done, return -1.

Examples

Example 1:

Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]

Output: 2

Explanation:

The first figure represents the initial dominoes.

If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

Example 2:

Input: tops = [3,5,1,2,3], bottoms = [3,6,3,3,4]

Output: -1

Explanation:

In this case, it is not possible to rotate the dominoes to make one row of values equal.

Intuition

The key insight is that if we can make all values in either row equal, the target value must be either the first value in the top row or the first value in the bottom row. We need to check both possibilities and find the minimum rotations required.

Approach

1. Check if we can make all values in the top row equal to tops[0]

2. Check if we can make all values in the top row equal to bottoms[0]

3. Check if we can make all values in the bottom row equal to tops[0]

4. Check if we can make all values in the bottom row equal to bottoms[0]

5. Return the minimum of all possible rotations, or -1 if none are possible

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution: Greedy Approach

Time Complexity: O(n) - Single pass through the array

Space Complexity: O(1) - Constant extra space

More Google coding questions