1007. Minimum Domino Rotations For Equal Row

Problem Description

In this problem, we are given two arrays, tops and bottoms, each representing the top and bottom halves of a stack of domino tiles, where each tile may have numbers from 1 to 6. We have the option to rotate any number of dominos to make either all top or all bottom numbers the same. Our goal is to find the minimum number of rotations required to achieve this uniformity of numbers on either side. If it's impossible to reach a state where all numbers are the same on any one side, we must return -1.

Imagine a row of dominoes lined up on a table, where we can see the top and bottom numbers of each tile. We can flip any domino, swapping its top and bottom numbers, trying to get all the top numbers to match or all the bottom numbers to match. The challenge is to do this in the fewest flips possible or determine if it's not possible at all.

Intuition

To solve this problem efficiently, we employ a greedy strategy. The key insight is that if a uniform number can be achieved on either the top or bottom of the dominos, that number must be the same as either the top or bottom of the first domino. This is because if the first domino does not contain the number we want to match everywhere, we can never make that number appear on both the first top and bottom by any rotation.

With this in mind, we define a function, f(x), that calculates the minimum number of rotations required to make all the values in either tops or bottoms equal to the number x. We only need to consider two cases for x: the number on the top and the number on the bottom of the first domino.

The function f(x) works by counting how many times the number x appears on the top (cnt1) and how many times on the bottom (cnt2). If the number x is not present in either side of a domino, it means we cannot make all values equal to x with rotations alone, and we return infinity (inf) to indicate that it is impossible for x.

If the number x is present, we calculate the rotations as the total number of dominos minus the maximum appearance count (max(cnt1, cnt2)). This represents the side with fewer appearances of x, which would need to be flipped to make all the numbers match x. We take the minimum value from applying function f(x) to both tops[0] and bottoms[0] to find the overall minimum rotations needed.

This approach is greedy because it seeks a local optimization—focusing on aligning all numbers to match either tops[0] or bottoms[0], to give a global solution which is the minimum number of rotations required. If neither number can be aligned, the function recognizes this by returning infinity, and thus the overall solution returns -1.

Learn more about Greedy patterns.

Solution Approach

The solution implements a simple yet clever approach utilizing a helper function that encapsulates the core logic required to solve the problem.

Let's walk through the steps:

1. We have a helper function f(x) which takes x as a parameter. This function is responsible for determining the minimum number of rotations needed to make all values in tops or all values in bottoms equal to x.

2. Inside f(x), we initiate two counters, cnt1 and cnt2, which count the occurrences of x in tops and bottoms arrays respectively. These counters are important as they help to evaluate the current state with respect to our target value x.

3. A loop runs over both tops and bottoms simultaneously using zip(tops, bottoms) which pairs the top and bottom values of each domino. For each pair (a, b):

   • If x is not found in either a or b, it implies that no rotations can make the ith domino's top or bottom value x. Hence, we return inf which denotes an impossible situation for x.

   • If x is found, we increment cnt1 if a (top value) equals x, and similarly, we increment cnt2 if b (bottom value) equals x.

4. After iterating over all dominos, the minimum rotations needed is calculated by taking the length of the tops array (which is the total number of dominos) and subtracting the larger of cnt1 or cnt2. This is because to make all numbers equal to x, we simply need to rotate the dominos which currently do not have x on the desired side (tops or bottoms). The side with a larger count of x will need fewer rotations since more dominos are already showing x.

5. Our main function minDominoRotations now calls f(x) for tops[0] and bottoms[0] and calculates the minimum between these two results. If we get inf, it means rotating won't help us achieve a uniform side, hence we return -1.

6. Otherwise, we return the minimum of the two values which represents the minimum number of rotations required for making all tops or all bottoms values equal.

This solution uses the greedy algorithmic paradigm where we take the local optimum (minimum rotations for tops[0] or bottoms[0]) to reach a global solution. Essential to this approach are the conditional checks and value counts which allow us to decide quickly the feasibility and cost (number of rotations) for each potential solution.

Additionally, by using Python's zip function to iterate over tops and bottoms simultaneously and its expressive syntax, the implementation remains clean, intuitive, and efficient.

Example Walkthrough

Let's consider small arrays for tops and bottoms for an illustrative example:

Suppose tops = [2, 1, 2, 4, 2] and bottoms = [5, 2, 2, 2, 2]. We want to make all numbers in either the top or bottom uniform with the minimum number of rotations.

• Firstly, we choose x to be tops[0], which is 2.

• Applying function f(x):

  • We initialize cnt1 and cnt2 both to zero, which will count the occurrences of 2 in tops and bottoms respectively.
  • As we iterate:
    • For the first domino, tops[0] is 2 so we increment cnt1 to 1.
    • For the second domino, bottoms[1] is 2, so we increment cnt2 to 1.
    • The third domino has 2 on both tops and bottoms, so we increment both cnt1 and cnt2.
    • The fourth domino does not have 2 on the top, but it is on the bottom, so we increment cnt2.
    • The fifth domino has 2 on the top, so we increment cnt1.
  • After completing the iteration, cnt1 is 4 (since tops has the number 2 in four positions) and cnt2 is 4 as well (as bottoms also has the number 2 in four positions).
  • The minimum number of rotations f(2) will be the total number of dominos (5) minus the maximum occurrences of 2 (4), which gives us 1. We can achieve this by flipping the fourth domino.

• Secondly, we choose x to be bottoms[0], which is 5.

• Applying function f(x) with 5:

  • We find that 5 does not appear in tops at all and only appears once in bottoms. This means we would have to flip every domino except the first one to get 5 on the top everywhere. This gives us a count of 4 flips.

When we compare the results, flipping to get all 2's requires only 1 rotation, while flipping to get all 5's requires 4 rotations. Therefore, the minimum number of rotations required is 1, and the target number is 2.

Hence, minDominoRotations would return 1, which indicates that we should flip the fourth domino for all dominos to show the number 2 on either tops or bottoms. Since both tops and bottoms have the number 2 on four out of five positions already, the target number 2 is the optimal choice for achieving uniformity with the minimum rotations possible.

Solution Implementation

Time and Space Complexity

The time complexity of the code provided is O(n), where n is the length of the arrays tops and bottoms. This is because the function f(x) goes through all the elements in tops and bottoms once, using a single loop with zip(tops, bottoms), to count the occurrences. The function f(x) is called at most twice, once for tops[0] and once for bottoms[0], regardless of the size of the input. Therefore, the total number of operations is proportional to the size of the arrays, thus the O(n) time complexity.

The space complexity is O(1). This is because the extra space used by the function does not depend on the size of the input arrays. The variables cnt1, cnt2, and ans use a constant amount of space, and no additional data structures that grow with the input size are used.

Learn more about how to find time and space complexity quickly using problem constraints.