# Minimum Domino Rotations For Equal Row
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-domino-rotations-for-equal-row)
Canonical: https://scaleengineer.com/dsa/problems/minimum-domino-rotations-for-equal-row
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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`.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-domino-rotations-for-equal-row/image0.png) 

**Input:** tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
**Output:** 2
**Explanation:** 
The first figure represents the dominoes as given by tops and bottoms: before we do any rotations.
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.

**Constraints:**

* `2 <= tops.length <= 2 * 104`
* `bottoms.length == tops.length`
* `1 <= tops[i], bottoms[i] <= 6`

# Approaches
## Brute Force with Backtracking
This approach explores every possible configuration of the domino row. For each of the `N` dominoes, we can either keep it as is or rotate it. This leads to `2^N` possible states. We can use recursion (backtracking) to generate all these states. For each state, we check if either the top row or the bottom row consists of all equal values. We keep track of the minimum number of rotations used to achieve such a state.
**Time:** O(N * 2^N). The recursion tree has `2^N` leaves. At each leaf node (base case), we perform a check that takes `O(N)` time. · **Space:** O(N). This is due to the recursion stack depth, which can go up to `N`.
**Pros:** It's a straightforward translation of the problem statement: "try all possibilities".; Guaranteed to find the correct answer.
**Cons:** Extremely inefficient and will not pass the time limits for the given constraints.
### Explanation
We define a recursive function, say `findMinRotations(index, currentRotations)`, which explores the possibilities from the `index`-th domino onwards.
The base case for the recursion is when `index` reaches the end of the array (`tops.length`). At this point, we have a complete configuration. We then check if the `tops` array is uniform or if the `bottoms` array is uniform.
To check for uniformity, we can take the first element of a row and see if all other elements are the same.
If a row is uniform, we update a global minimum rotations variable with `currentRotations` if it's smaller.
In the recursive step for a given `index`, we have two choices:
1.  **Don't rotate:** We make a recursive call `findMinRotations(index + 1, currentRotations)`.
2.  **Rotate:** We swap `tops[index]` and `bottoms[index]`, and then make a recursive call `findMinRotations(index + 1, currentRotations + 1)`. After the call returns, we must swap back (backtrack) to restore the state for other branches of the recursion.
The initial call would be `findMinRotations(0, 0)`. The final result is the global minimum found, or -1 if it was never updated.
```java
// This approach is too slow and will result in a Time Limit Exceeded error.
// It is for demonstration of the brute-force concept only.
class Solution {
    int minRotations = Integer.MAX_VALUE;

    public int minDominoRotations(int[] tops, int[] bottoms) {
        solve(0, tops, bottoms, 0);
        return minRotations == Integer.MAX_VALUE ? -1 : minRotations;
    }

    private void solve(int index, int[] tops, int[] bottoms, int rotations) {
        if (index == tops.length) {
            checkUniform(tops, bottoms, rotations);
            return;
        }

        // Option 1: Don't rotate
        solve(index + 1, tops, bottoms, rotations);

        // Option 2: Rotate
        swap(tops, bottoms, index);
        solve(index + 1, tops, bottoms, rotations + 1);
        swap(tops, bottoms, index); // Backtrack
    }

    private void checkUniform(int[] tops, int[] bottoms, int rotations) {
        boolean topsUniform = true;
        for (int i = 1; i < tops.length; i++) {
            if (tops[i] != tops[0]) {
                topsUniform = false;
                break;
            }
        }
        if (topsUniform) {
            minRotations = Math.min(minRotations, rotations);
        }

        boolean bottomsUniform = true;
        for (int i = 1; i < bottoms.length; i++) {
            if (bottoms[i] != bottoms[0]) {
                bottomsUniform = false;
                break;
            }
        }
        if (bottomsUniform) {
            minRotations = Math.min(minRotations, rotations);
        }
    }

    private void swap(int[] tops, int[] bottoms, int i) {
        int temp = tops[i];
        tops[i] = bottoms[i];
        bottoms[i] = temp;
    }
}
```
### Algorithm
1. Initialize a global variable `minRotations` to a very large value (e.g., `Integer.MAX_VALUE`).
2. Create a recursive function `solve(index, tops, bottoms, rotations)`:
    a. **Base Case:** If `index == tops.length`:
        i. Check if the `tops` row is uniform. If yes, update `minRotations = min(minRotations, rotations)`.
        ii. Check if the `bottoms` row is uniform. If yes, update `minRotations = min(minRotations, rotations)`.
        iii. Return.
    b. **Recursive Step:**
        i. **Choice 1 (No rotation):** Call `solve(index + 1, tops, bottoms, rotations)`.
        ii. **Choice 2 (Rotation):**
            - Swap `tops[index]` and `bottoms[index]`.
            - Call `solve(index + 1, tops, bottoms, rotations + 1)`.
            - **Backtrack:** Swap `tops[index]` and `bottoms[index]` back to their original values.
3. Call `solve(0, tops, bottoms, 0)`.
4. If `minRotations` is still the initial large value, return -1. Otherwise, return `minRotations`.

## Check All Possible Target Values (1-6)
Since the domino values are constrained to be between 1 and 6, the final uniform row must consist of one of these six numbers. This approach iterates through each number from 1 to 6 and treats it as a potential target value. For each target, it calculates the minimum rotations required to make either the `tops` or `bottoms` row uniform with that target.
**Time:** O(N). We iterate through the `N` dominoes for each of the 6 possible target values. The complexity is `6 * O(N)`, which simplifies to `O(N)`. · **Space:** O(1). We only use a few variables to store counts and the minimum value, regardless of the input size.
**Pros:** Significantly faster than the brute-force approach.; Correct and handles all cases.; Relatively simple to reason about and implement.
**Cons:** It performs redundant checks. We know the target value must appear in the first domino, so checking all 6 values is not strictly necessary.
### Explanation
We can create a helper function, `check(target, tops, bottoms)`, that determines the minimum rotations needed for a specific `target` value.
This function iterates through the dominoes from `i = 0` to `N-1`. For each domino, it checks if the `target` value is present (either in `tops[i]` or `bottoms[i]`). If for any domino, the `target` is not present, it's impossible to make a uniform row with this `target`, so the function can return an indicator of failure (like `Integer.MAX_VALUE`).
While iterating, the function maintains two counters: `rotationsTop` (to make the top row uniform) and `rotationsBottom` (to make the bottom row uniform).
If `tops[i]` is not the `target` (but `bottoms[i]` is), we must rotate to make the top row uniform, so we increment `rotationsTop`.
Similarly, if `bottoms[i]` is not the `target` (but `tops[i]` is), we must rotate to make the bottom row uniform, so we increment `rotationsBottom`.
After checking all dominoes, the function returns the minimum of `rotationsTop` and `rotationsBottom`.
The main function calls this `check` helper for each number from 1 to 6, keeps track of the minimum result, and returns it. If no target value works, the minimum will remain at its initial large value, and we should return -1.
```java
class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        int minSwaps = Integer.MAX_VALUE;

        for (int target = 1; target <= 6; target++) {
            int currentSwaps = check(target, tops, bottoms);
            if (currentSwaps != -1) {
                minSwaps = Math.min(minSwaps, currentSwaps);
            }
        }

        return minSwaps == Integer.MAX_VALUE ? -1 : minSwaps;
    }

    // Helper to check for a specific target value
    private int check(int target, int[] tops, int[] bottoms) {
        int rotationsTop = 0;
        int rotationsBottom = 0;
        for (int i = 0; i < tops.length; i++) {
            if (tops[i] != target && bottoms[i] != target) {
                return -1; // Impossible for this target
            } else if (tops[i] != target) {
                rotationsTop++;
            } else if (bottoms[i] != target) {
                rotationsBottom++;
            }
        }
        return Math.min(rotationsTop, rotationsBottom);
    }
}
```
### Algorithm
1. Initialize `minRotations` to `Integer.MAX_VALUE`.
2. Loop `target` from 1 to 6.
    a. Initialize `rotationsTop = 0`, `rotationsBottom = 0`, `possible = true`.
    b. Loop `i` from 0 to `tops.length - 1`.
        i. If `tops[i] != target` and `bottoms[i] != target`, then this `target` is not possible. Set `possible = false` and break the inner loop.
        ii. If `tops[i] != target`, increment `rotationsTop`.
        iii. If `bottoms[i] != target`, increment `rotationsBottom`.
    c. If `possible` is true, update `minRotations = min(minRotations, rotationsTop, rotationsBottom)`.
3. If `minRotations` is still `Integer.MAX_VALUE`, return -1. Otherwise, return `minRotations`.

## Greedy Check of First Domino's Values
This is the most optimized approach. It's based on a crucial observation: if it's possible to make an entire row uniform with a value `X`, then `X` must be present in every single domino pair `(tops[i], bottoms[i])`. This means that the target value `X` must be present in the first domino pair, `(tops[0], bottoms[0])`. Therefore, we only need to check two potential candidates for the target value: `tops[0]` and `bottoms[0]`.
**Time:** O(N). We perform at most two passes over the arrays. The complexity is `2 * O(N)`, which is `O(N)`. · **Space:** O(1). Constant extra space is used.
**Pros:** This is the most efficient solution in terms of constant factors.; It correctly identifies that only two values need to be checked.
**Cons:** The core logic relies on an insight that might not be immediately obvious to everyone.
### Explanation
We can use the same helper function `check(target, tops, bottoms)` from the previous approach, which calculates the minimum rotations for a given `target` in `O(N)` time.
First, we try `tops[0]` as the target value. We call `check(tops[0], tops, bottoms)`. This will give us the minimum rotations needed if `tops[0]` is the target, or an indicator of failure (e.g., -1 or `Integer.MAX_VALUE`) if it's not possible.
Next, we consider `bottoms[0]` as a potential target. If `bottoms[0]` is different from `tops[0]`, we also call `check(bottoms[0], tops, bottoms)`.
The final answer is the minimum of the valid results returned by these one or two calls. If both attempts fail, it's impossible to make any row uniform, so we return -1. This approach avoids iterating through all 6 possible values and directly tests the only viable candidates.
```java
class Solution {
    public int minDominoRotations(int[] tops, int[] bottoms) {
        // Try making a row uniform with tops[0]
        int rotations1 = check(tops[0], tops, bottoms);
        
        // If tops[0] and bottoms[0] are the same, no need to check again.
        // Also, if the first check was successful, we don't need to check bottoms[0]
        // because the number of rotations would be the same or worse.
        // But for simplicity and correctness, we can check both and take the min.
        if (tops[0] == bottoms[0]) {
             return rotations1;
        }
        
        // Try making a row uniform with bottoms[0]
        int rotations2 = check(bottoms[0], tops, bottoms);

        // Return the minimum valid result.
        if (rotations1 == -1 && rotations2 == -1) {
            return -1;
        } else if (rotations1 == -1) {
            return rotations2;
        } else if (rotations2 == -1) {
            return rotations1;
        } else {
            return Math.min(rotations1, rotations2);
        }
    }

    // Helper to check for a specific target value
    // Returns min rotations or -1 if not possible
    private int check(int target, int[] tops, int[] bottoms) {
        int rotationsTop = 0;
        int rotationsBottom = 0;
        for (int i = 0; i < tops.length; i++) {
            if (tops[i] != target && bottoms[i] != target) {
                return -1; // Impossible for this target
            } else if (tops[i] != target) {
                rotationsTop++;
            } else if (bottoms[i] != target) {
                rotationsBottom++;
            }
        }
        return Math.min(rotationsTop, rotationsBottom);
    }
}
```
### Algorithm
1. Define a helper function `check(target, tops, bottoms)` that returns the minimum rotations to make a row equal to `target`, or a large value/sentinel if impossible.
    a. Inside `check`, initialize `rotationsTop = 0`, `rotationsBottom = 0`.
    b. Loop `i` from 0 to `tops.length - 1`.
        i. If `tops[i] != target` and `bottoms[i] != target`, return `Integer.MAX_VALUE`.
        ii. If `tops[i] != target`, increment `rotationsTop`.
        iii. If `bottoms[i] != target`, increment `rotationsBottom`.
    c. Return `min(rotationsTop, rotationsBottom)`.
2. In the main function:
    a. Call `rotations1 = check(tops[0], tops, bottoms)`.
    b. Call `rotations2 = check(bottoms[0], tops, bottoms)`.
    c. Find the minimum of `rotations1` and `rotations2`. Let this be `minRotations`.
3. If `minRotations` is `Integer.MAX_VALUE`, return -1. Otherwise, return `minRotations`.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int[] tops;
private
  int[] bottoms;
public
  int minDominoRotations(int[] tops, int[] bottoms) {
    n = tops.length;
    this.tops = tops;
    this.bottoms = bottoms;
    int ans = Math.min(f(tops[0]), f(bottoms[0]));
    return ans > n ? -1 : ans;
  }
private
  int f(int x) {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; ++i) {
      if (tops[i] != x && bottoms[i] != x) {
        return n + 1;
      }
      cnt1 += tops[i] == x ? 1 : 0;
      cnt2 += bottoms[i] == x ? 1 : 0;
    }
    return n - Math.max(cnt1, cnt2);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minDominoRotations(vector<int> &tops, vector<int> &bottoms) {
    int n = tops.size();
    auto f = [&](int x) {
      int cnt1 = 0, cnt2 = 0;
      for (int i = 0; i < n; ++i) {
        if (tops[i] != x && bottoms[i] != x) {
          return n + 1;
        }
        cnt1 += tops[i] == x;
        cnt2 += bottoms[i] == x;
      }
      return n - max(cnt1, cnt2);
    };
    int ans = min(f(tops[0]), f(bottoms[0]));
    return ans > n ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minDominoRotations(self, tops: List[int], bottoms: List[int]) -> int: def f(x: int) -> int: cnt1 = cnt2 = 0 for a, b in zip(tops, bottoms): if x not in (a, b): return inf cnt1 += a == x cnt2 += b == x return len(tops) - max(cnt1, cnt2) ans = min(f(tops[0]), f(bottoms[0])) return - 1 if ans == inf else ans

```