Domain 2MediumMEDIUM

Minimum Domino Rotations For Equal Row

Determine minimum rotations to make all elements in A or B equal by checking candidates from index 0 and validating across arrays.

Domain: medium•Updated: 2026-09-06
#linear scan#arrays#O(N)#O(1)

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 A and B, same length (2≤N≤20,0002 \le N \le 20,000).
  • 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.
  • -1 if it is impossible to achieve uniformity for either row.

Intuition

  1. Candidate Selection: For a specific value X to be the target for the entire row (either top or bottom), every single domino must contain at least one instance of X. 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] and B[0].
  2. Validation & Counting: For each candidate value (e.g., val = A[0]), iterate through the arrays. If a domino does not contain val, that candidate is invalid for this row configuration. If it contains val, count how many rotations are needed to make Row A uniform (rot_a) and Row B uniform (rot_b).
  3. Optimal Choice: Since we want either all of A equal OR all of B equal, for a valid candidate value X, the cost is min⁡(rotations to fix A,rotations to fix B)\min(\text{rotations to fix } A, \text{rotations to fix } B). We take the minimum across both candidates and their respective row configurations.

Approach

  1. Initialize a variable ans (minimum rotations found so far) to infinity or -1.
  2. Identify candidate values from index 0: {A[0], B[0]}. Use a set to avoid redundant checks if they are identical.
  3. 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] nor B[i] equals val, this candidate is invalid. Mark as impossible immediately.
    • Update counters: Increment rot_a if A[i] != val. Increment rot_b if B[i] != val. Since the validity check passed, at least one side matches val, ensuring a valid rotation exists for that row configuration.
  4. After checking all indices for a candidate, update global minimum with min⁡(valid rot_a,valid rot_b)\min(\text{valid } rot\_a, \text{valid } rot\_b). If only one is possible (impossible case handled by validity check), take the cost; if neither valid, ignore this candidate’s costs.
  5. Return -1 if no valid configuration was found after testing candidates.

Complexity Analysis

  • Time Complexity: O(N)O(N). 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 NN relative to value range constraints (k=2k=2 checks), resulting in linear time.
  • Space Complexity: O(1)O(1) 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 all i, rot_a remains 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 NN 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).