Leetcode 1007. Minimum Domino Rotations For Equal Row

Problem Explanation

In this problem we have a set of dominos, with numbers from 1 to 6 at the top and the bottom of each domino. Our objective is to find the minimum number of rotations needed so that all the top or bottom values of all dominos become the same. If this is not possible, then we should return -1.

For example, consider the dominos represented by these arrays A = [2,1,2,4,2,2] and B = [5,2,6,2,3,2]. Here the dominos are (2,5), (1,2), (2,6), (4,2), (2,3), (2,2). If we swap 2nd and 4th dominos, all the top values will become same as 2.

Solution

The key to solve this problem is to keep track of counts of the numbers in top and bottom. We create two count arrays countTops and countBottoms to represent the count of numbers in A and B arrays respectively. Also we create an array countBoth to represent the count of the numbers that are same at top and bottom.

So we start with iterating through all dominos. For each domino, we increment the counter for top and bottom number in their respective count array. And if top and bottom numbers are same, we increment the counter for that number in countBoth.

We also initialize n to the size of any of the arrays (since both arrays are of same size).

After this, we iterate from 1 through 6 (as domino numbers are from 1 to 6), and checks if the sum of the counters for that number in countTops and countBottoms, subtracted by the counter for that number in countBoth, equals to n. If yes, that means all dominos can be made to have same number either at top or bottom by rotating minimum of n - max(countTops[i], countBottoms[i]) times.

If no number satisfies the requirement, we return -1.

1
2python
3class Solution:
4    def minDominoRotations(self, A, B):
5        n = len(A)
6        countA, countB, countSame = [0] * 7, [0] * 7, [0] * 7
7        for i in range(n):
8            countA[A[i]] += 1
9            countB[B[i]] += 1
10            if A[i] == B[i]:
11                countSame[A[i]] += 1
12        for i in range(1, 7):
13            if countA[i] + countB[i] - countSame[i] >= n:
14                return n - max(countA[i], countB[i])
15        return -1

1
2java
3class Solution {
4    public int minDominoRotations(int[] A, int[] B) {
5        int n = A.length;
6        int[] countA = new int[7];
7        int[] countB = new int[7];
8        int[] countSame = new int[7];
9        for (int i = 0; i < n; i++) {
10            countA[A[i]]++;
11            countB[B[i]]++;
12            if (A[i] == B[i])
13                countSame[A[i]]++;
14        }
15        for (int i = 1; i <= 6; i++) {
16            if (countA[i] + countB[i] - countSame[i] == n)
17                return n - Math.max(countA[i], countB[i]);
18        }
19        return -1;
20    }
21}

1
2javascript
3class Solution {
4  minDominoRotations(A, B) {
5    const n = A.length;
6    const counterA = Array(7).fill(0);
7    const counterB = Array(7).fill(0);
8    const counterSame = Array(7).fill(0);
9
10    for (let i = 0; i < n; ++i) {
11      counterA[A[i]]++;
12      counterB[B[i]]++;
13      if (A[i] == B[i]) counterSame[A[i]]++;
14    }
15
16    for (let i = 1; i <= 6; ++i)
17      if (counterA[i] + counterB[i] - counterSame[i] === n)
18        return n - Math.max(counterA[i], counterB[i]);
19
20    return -1;
21  }
22}

1
2cpp
3class Solution {
4public:
5    int minDominoRotations(vector<int>& A, vector<int>& B) {
6        int n = A.size();
7        vector<int> countA(7, 0);
8        vector<int> countB(7, 0);
9        vector<int> countSame(7, 0);
10
11        for (int i = 0; i < n; i++) {
12            countA[A[i]]++;
13            countB[B[i]]++;
14            if (A[i] == B[i])
15                countSame[A[i]]++;
16        }
17
18        for (int i = 1; i <= 6; i++)
19            if (countA[i] + countB[i] - countSame[i] == n)
20                return n - max(countA[i], countB[i]);
21
22        return -1;
23    }
24};

1
2csharp
3public class Solution {
4    public int MinDominoRotations(int[] A, int[] B) {
5        var n = A.Length;
6        var countA = new int[7];
7        var countB = new int[7];
8        var countSame = new int[7];
9
10        for (var i = 0; i < n; i++) {
11            countA[A[i]]++;
12            countB[B[i]]++;
13            if (A[i] == B[i]) {
14                countSame[A[i]]++;
15            }
16        }
17
18        for (var i = 1; i <= 6; i++) {
19            if (countA[i] + countB[i] - countSame[i] == n) {
20                return n - Math.Max(countA[i], countB[i]);
21            }
22        }
23
24        return -1;
25    }
26}

The given problem can be solved using array or hash map. We iterate over the given dominos and maintains separate counts for the top and bottom values of each domino. While doing so, if the top and bottom values are same, we also maintain count for this in a separate array or map.

Then we iterate from 1 to 6(as the possible values on each domino), if the sum of counts for a certain number from top and bottom values subtracting the counts of that number where it was same at top and bottom equals the total number of dominos, it means that, we can make same numbers on top or bottom by just rotating the dominos. And while calculating the minimum rotations we pick the number from these whose maximum presence on top or bottom is maximum.

If not even a single number with given condition found, then it is not possible to arrange dominos in desired way, hence return -1.

Following are solutions for python, js, java and c++:

1
2python
3class Solution:
4    def minDominoRotations(self, A, B):
5        n = len(A)
6        countA, countB, countSame = [0] * 7, [0] * 7, [0] * 7
7        for i in range(n):
8            countA[A[i]] += 1
9            countB[B[i]] += 1
10            if A[i] == B[i]:
11                countSame[A[i]] += 1
12        for i in range(1, 7):
13            if countA[i] + countB[i] - countSame[i] == n:
14                return n - max(countA[i], countB[i])
15        return -1

1
2javascript
3function minDominoRotations(A, B) {
4    const n = A.length;
5
6    const countA = new Array(7).fill(0);
7    const countB = new Array(7).fill(0);
8    const countSame = new Array(7).fill(0);
9
10    for (let i = 0; i < n; i++) {
11        countA[A[i]]++;
12        countB[B[i]]++;
13        if (A[i] === B[i]) {
14            countSame[A[i]]++;
15        }
16    }
17
18    for (let i = 1; i <= 6; i++) {
19        if ((countA[i] + countB[i] - countSame[i]) === n) {
20            return n - Math.max(countA[i], countB[i]);
21        }
22    }
23
24    return -1;
25}

1
2java
3class Solution {
4    public int minDominoRotations(int[] A, int[] B) {
5        int[] countA = new int[7], countB = new int[7], countSame = new int[7];
6        int N = A.length;
7        for (int i = 0; i < N; ++i) {
8            countA[A[i]]++;
9            countB[B[i]]++;
10            if (A[i] == B[i])
11                countSame[A[i]]++;
12        }
13        for (int i = 1; i <= 6; i++)
14            if (countA[i] + countB[i] - countSame[i] == N)
15                return N - Integer.max(countA[i], countB[i]);
16        return -1;
17    }
18}

1
2c++
3class Solution {
4public:
5    int minDominoRotations(vector<int>& A, vector<int>& B) {
6        int countA[7] = {0}, countB[7] = {0}, countSame[7] = {0};
7        int N = A.size();
8        for (int i = 0; i < N; ++i) {
9            countA[A[i]]++;
10            countB[B[i]]++;
11            if (A[i] == B[i])
12                countSame[A[i]]++;
13        }
14        for (int i = 1; i <= 6; ++i)
15            if (countA[i] + countB[i] - countSame[i] == N)
16                return N - max(countA[i], countB[i]);
17        return -1;
18    }
19};