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};
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.