Leetcode 1007: Minimum Domino Rotations For Equal Row
You are given two arrays, tops and bottoms, where each array represents the top and bottom halves of a series of dominoes. A domino can be rotated, which means swapping its top and bottom halves. The task is to determine the minimum number of rotations required to make either the entire top row or the bottom row consist of the same value. If it is not possible to achieve this, return -1.
Problem
Approach
Steps
Complexity
Input: The input consists of two arrays of integers, tops and bottoms, where 1 <= tops.length == bottoms.length <= 2 * 10^4 and 1 <= tops[i], bottoms[i] <= 6.
Example: tops = [2, 1, 3, 4], bottoms = [4, 1, 2, 3]
Constraints:
• 1 <= tops.length == bottoms.length <= 2 * 10^4
• 1 <= tops[i], bottoms[i] <= 6
Output: Return the minimum number of rotations required to make all elements in either the top or bottom row equal. If it is not possible, return -1.
Example: Output: 1
Constraints:
• If no rotations can achieve a uniform row, return -1.
Goal: The goal is to determine the minimum number of rotations needed to make all elements in either the top or bottom row the same. If not possible, return -1.
Steps:
• Count the frequency of each value in both the top and bottom rows.
• For each value that appears in both rows, check if rotating dominoes can make either row uniform with that value.
• Keep track of the minimum number of rotations required and return the result.
Goal: Ensure that the solution can handle the maximum constraints efficiently.
Steps:
• The input arrays can have up to 2 * 10^4 elements, so the solution should be optimized to handle large inputs.
Assumptions:
• The values in the tops and bottoms arrays are between 1 and 6.
• The dominoes can be rotated to swap the top and bottom values.
• Input: Input: tops = [2, 1, 2, 4, 2, 2], bottoms = [5, 2, 6, 2, 3, 2]
• Explanation: In this case, rotating the second and fourth dominoes will make the top row equal to 2 with only 2 rotations.
• Input: Input: tops = [3, 5, 1, 2, 3], bottoms = [3, 6, 3, 3, 4]
• Explanation: In this case, it is impossible to make either row uniform with the same value, so the output is -1.
Approach: The approach is to check if we can achieve a uniform row by rotating dominoes. We will consider each value that appears in both rows and calculate the number of rotations needed to make all elements in either the top or bottom row the same value.
Observations:
• We need to ensure that we can align all values in one row either by keeping them as they are or rotating the corresponding dominoes.
• We can iterate through the dominoes and check if it's possible to make all top values or all bottom values equal for any common value.
Steps:
• 1. Iterate over each domino and record the frequency of each number in both the tops and bottoms arrays.
• 2. Check for each value from 1 to 6 if it can become the value for the entire row by rotating the dominoes. Calculate the rotations needed for each case.
• 3. Return the minimum number of rotations needed, or -1 if it's not possible to make either row uniform.
Empty Inputs:
• The input arrays will never be empty, as per the problem constraints.
Large Inputs:
• The solution should efficiently handle input arrays with lengths up to 2 * 10^4.
Special Values:
• If all values in either row are already the same, no rotations are needed.
Constraints:
• The solution must handle the largest case efficiently, requiring a linear solution in terms of the length of the input arrays.
int minDominoRotations(vector<int>& top, vector<int>& bottom) {
map<int, int> mp;
vector<int> tc(7, 0), uc(7, 0);
int n = top.size();
for(int i = 0; i < n; i++) {
if(bottom[i] != top[i]) {
mp[bottom[i]]++;
mp[top[i]]++;
} else mp[top[i]]++;
uc[bottom[i]]++;
tc[top[i]]++;
}
vector<int> opt;
for(auto it: mp) {
if(it.second == n)
opt.push_back(it.first);
}
if(opt.empty()) return -1;
int res = INT_MAX;
for(int x: opt) {
if(uc[x] == n || tc[x] == n) return 0;
res = min(res, n - uc[x]);
res = min(res, n - tc[x]);
}
return res;
}
1 : Function Declaration
int minDominoRotations(vector<int>& top, vector<int>& bottom) {
Declares the main function which takes two vectors, top and bottom, representing the top and bottom numbers of each domino.
2 : Map Initialization
map<int, int> mp;
Initializes a map to store the frequency of each number across both top and bottom arrays.
3 : Vector Initialization
vector<int> tc(7, 0), uc(7, 0);
Initializes two vectors, tc and uc, each of size 7 to track the count of numbers on top and bottom, respectively.
4 : Variable Initialization
int n = top.size();
Sets the variable n to the size of the top vector, which represents the number of dominoes.
5 : Loop Begin
for(int i = 0; i < n; i++) {
Starts a loop that iterates through each domino in the top and bottom arrays.
6 : Condition Check
if(bottom[i] != top[i]) {
Checks if the top and bottom values for the current domino are different.
7 : Map Update
mp[bottom[i]]++;
Increases the count for the bottom value in the map.
8 : Map Update
mp[top[i]]++;
Increases the count for the top value in the map.
9 : Same Number Check
} else mp[top[i]]++;
If the top and bottom values are the same, just increase the count for the top value in the map.
10 : Vector Update
uc[bottom[i]]++;
Increases the count for the bottom number in the uc vector.
11 : Vector Update
tc[top[i]]++;
Increases the count for the top number in the tc vector.
12 : Optional Numbers
vector<int> opt;
Initializes a vector to store the numbers that could be used for the minimum rotation.
13 : Map Iteration
for(auto it: mp) {
Iterates through the map to find which numbers appear in all the dominoes.
14 : Condition Check
if(it.second == n)
Checks if a number appears in all dominoes (top and bottom arrays combined).
15 : Vector Update
opt.push_back(it.first);
Adds the number to the options vector if it appears in all dominoes.
16 : Empty Check
if(opt.empty()) return -1;
If no numbers can be used for rotation, return -1 indicating it's not possible.
17 : Result Initialization
int res = INT_MAX;
Initializes the result variable with the maximum possible value to find the minimum rotations.
18 : Option Iteration
for(int x: opt) {
Iterates through the possible numbers in the options vector to find the minimum rotations.
19 : Condition Check
if(uc[x] == n || tc[x] == n) return 0;
Checks if all dominoes can already show the same number either on the top or bottom.
20 : Result Update
res = min(res, n - uc[x]);
Calculates the minimum number of rotations needed for the bottom values.
21 : Result Update
res = min(res, n - tc[x]);
Calculates the minimum number of rotations needed for the top values.
22 : Return Result
return res;
Returns the minimum number of rotations needed.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of dominoes, as we process each domino a constant number of times.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1), as we only need a few extra variables to track counts of numbers in the rows.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus