Minimum Domino Rotations For Equal Row | Dynamic Programming Approach
Anonymous User
85

Hi all,

I attempted today's daily challenge question with Dynamic Programming. But for one test-case, my answer came smaller than the expected answer. I am unable to figure out the incorrectness in my DP thought process. Can anyone help me?

I took two DP arrays:

  • withSwap[i] is number of swaps until ith index where ith index must be swapped
  • withoutSwap[i] is number of swaps until ith index where ith index must NOT be swapped

I defined a helper function:
helper(A, B, withSwap, withoutSwap, index, toSwapIndexOrNot)

if (A[idx] == B[idx]) {
		if (toSwap) {
			withSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
		} else {
			withoutSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
		}

	} else if (A[idx] == A[idx - 1] || B[idx] == B[idx-1]) {
		if (toSwap) {
			withSwap[idx] = 1 + helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
		} else {
			withoutSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
		}

	} else if (A[idx] == B[idx - 1] || B[idx] == A[idx-1]) {
		if (toSwap) {
			withSwap[idx] = 1 + helper(A, B, withSwap, withoutSwap, idx - 1, !toSwap);
		} else {
			withoutSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, !toSwap);
		}   
	}

Full Code:

class Solution {
    public int minDominoRotations(int[] A, int[] B) {
        int n = A.length;
        // check if it's possible
        Set<Integer> candidates = new HashSet<>();
        candidates.add(A[0]);
        candidates.add(B[0]);
        
        for (int i = 1; i < n; i++) {
            // System.out.println(candidates);
            if (candidates.contains(A[i])) {
                candidates.retainAll(Arrays.asList(A[i]));
            } else if (candidates.contains(B[i])) {
                candidates.retainAll(Arrays.asList(B[i]));
            } else {
                return -1;
            }
        }
        
        int[] withSwap = new int[n],
            withoutSwap = new int[n];
        
        Arrays.fill(withSwap, -1);
        Arrays.fill(withoutSwap, -1);
        
        return Math.min(helper(A, B, withSwap, withoutSwap, n-1, true),
                        helper(A, B, withSwap, withoutSwap, n-1, false));
    }
    
    private int helper(int[] A, int[] B, int[] withSwap, int[] withoutSwap, int idx, boolean toSwap) {
        if (idx == 0) {
            return toSwap ? 1 : 0;
            
        } else if (toSwap && withSwap[idx] >= 0) {
            return withSwap[idx];
            
        } else if (!toSwap && withoutSwap[idx] >= 0) {
            return withoutSwap[idx];
            
        }
        
        if (A[idx] == B[idx]) {
            if (toSwap) {
                withSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
            } else {
                withoutSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
            }
            
        } else if (A[idx] == A[idx - 1] || B[idx] == B[idx-1]) {
            if (toSwap) {
                withSwap[idx] = 1 + helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
            } else {
                withoutSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, toSwap);
            }
            
        } else if (A[idx] == B[idx - 1] || B[idx] == A[idx-1]) {
            if (toSwap) {
                withSwap[idx] = 1 + helper(A, B, withSwap, withoutSwap, idx - 1, !toSwap);
            } else {
                withoutSwap[idx] = helper(A, B, withSwap, withoutSwap, idx - 1, !toSwap);
            }   
        }
        
        return toSwap ? withSwap[idx] : withoutSwap[idx];
    }
}
Comments (0)