Problem Breakdown
We are given two integer lists A (top halves) and B (bottom halves), representing a row of dominoes. We can rotate any domino to swap its values between top (A[i]) and bottom (B[i]). The goal is to make all elements in either array uniform (all equal).
Inputs:
- Two lists
AandB, same length (). - Values are integers between 1 and 6.
Outputs:
- An integer representing the minimum number of rotations required to make all values in one row equal.
-1if it is impossible to achieve uniformity for either row.
Intuition
- Candidate Selection: For a specific value
Xto be the target for the entire row (either top or bottom), every single domino must contain at least one instance ofX. Consequently, this property must hold true for the very first pair(A[0], B[0]). Therefore, we only need to test two candidate values:A[0]andB[0]. - Validation & Counting: For each candidate value (e.g.,
val = A[0]), iterate through the arrays. If a domino does not containval, that candidate is invalid for this row configuration. If it containsval, count how many rotations are needed to make Row A uniform (rot_a) and Row B uniform (rot_b). - Optimal Choice: Since we want either all of A equal OR all of B equal, for a valid candidate value
X, the cost is . We take the minimum across both candidates and their respective row configurations.
Approach
- Initialize a variable
ans(minimum rotations found so far) to infinity or -1. - Identify candidate values from index 0:
{A[0], B[0]}. Use a set to avoid redundant checks if they are identical. - For each unique candidate value
val:- Initialize counters for rotations needed for Row A (
rot_a) and Row B (rot_b). - Iterate through the arrays simultaneously (using index).
- Check validity: If neither
A[i]norB[i]equalsval, this candidate is invalid. Mark as impossible immediately. - Update counters: Increment
rot_aifA[i] != val. Incrementrot_bifB[i] != val. Since the validity check passed, at least one side matchesval, ensuring a valid rotation exists for that row configuration.
- Initialize counters for rotations needed for Row A (
- After checking all indices for a candidate, update global minimum with . If only one is possible (impossible case handled by validity check), take the cost; if neither valid, ignore this candidate’s costs.
- Return -1 if no valid configuration was found after testing candidates.
Complexity Analysis
- Time Complexity: . We iterate through the arrays at most twice (once for each unique candidate from index 0). Since there are only two distinct values to check, this is effectively a constant number of passes over input size relative to value range constraints ( checks), resulting in linear time.
- Space Complexity: auxiliary space. We use a few integer variables and counters regardless of input size (excluding the set for candidates which holds max 2 elements).
Solution
def minDominoRotations(A: list[int], B: list[int]) -> int:
n = len(A)
# Helper function to calculate rotations for a specific target value
def get_min_rotations(target_val):
rot_a = 0
rot_b = 0
for i in range(n):
top, bottom = A[i], B[i]
# If neither side has the target value, this candidate is impossible
if not (top == target_val or bottom == target_val):
return -1
# Count rotations needed to make Row A uniform with target_val
if top != target_val:
rot_a += 1
# Count rotations needed to make Row B uniform with target_val
if bottom != target_val:
rot_b += 1
# Return the minimum valid cost for this candidate value.
# If both rows can be made uniform, we take the smaller rotation count.
return min(rot_a, rot_b)
candidates = {A[0], B[0]}
ans = float('inf')
for val in candidates:
res = get_min_rotations(val)
# If valid configuration found (res != -1), update global minimum
if res != -1:
ans = min(ans, res)
return ans if ans != float('inf') else -1
# Example usage matching problem description logic implicitly handled by function signature
Edge Cases Handled
- Impossible Case: If no candidate value allows every domino to contain it (e.g.,
A=[3], B=[4]), the helper returns-1, and final answer is-1. - Duplicate Candidates: Using a set
{A[0], B[0]}ensures we don’t process the same number twice if both halves of index 0 are identical. - Zero Rotations Needed: If
A[i]already equals target for alli,rot_aremains 0, correctly returning 0 as minimum cost. - Single Candidate Validity: The logic handles cases where only one row (e.g., Row A) can be made uniform with a specific value while the other cannot; it takes that valid path’s cost via
min(rot_a, rot_b)inside the helper function for each candidate target. If validity check fails globally, both counts are invalid (-1). - Constraints: Handles up to 20,000 within time limits due to linear scan and constant number of candidates (max 6 unique values possible but we limit checks to index 0).