Skip to main content

Hashing

Card Flipping Game Solution In C++/Java/Python/JS

Problem Description

You are given two 0-indexed integer arrays fronts and backs of length n, where the ith card has the positive integer fronts[i] printed on the front and backs[i]  printed on the back. Initially, each card is placed on a table such that the front number is facing up and the other is facing down. You may flip over any number of cards (possibly zero).
After flipping the cards, an integer is considered good if it is facing down on some card and not facing up on any card.
Return the minimum possible good integer after flipping the cards. If there are no good integers, return 0.

Examples:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation:
If we flip the second card, the face up numbers are [1,3,4,4,7] and the face down are [1,2,4,1,3].
2 is the minimum good integer as it appears facing down but not facing up.
It can be shown that 2 is the minimum possible good integer obtainable after flipping some cards.

Input: fronts = [1], backs = [1]
Output: 0
Explanation:
There are no good integers no matter how we flip the cards, so we return 0.

Constraints:

  • n == fronts.length == backs.length
  • 1 <= n <= 1000
  • 1 <= fronts[i], backs[i] <= 2000
💡
Try it Yourself First!
This problem requires finding the smallest number that can appear on the front but not on the back of any card. The key insight is to identify numbers that appear on both sides of at least one card (invalid choices) and exclude them. The solution involves scanning both fronts and backs, collecting potential candidates, and returning the smallest valid number.

Optimal Approach

Intuition

Imagine you have a set of cards, each with a number on the front and another on the back. You can flip any card, and your goal is to find the smallest number that is never repeated on both sides of the same card. This ensures that the number appears only as a possible "good" number when flipped.

To solve this, we iterate through both fronts and backs, treating each number as a candidate. For each candidate number (either from fronts[i] or backs[i]), we check if it appears on both sides of any card—if so, it cannot be a valid answer. We perform this check for every number and update our result with the smallest valid number found.

The nested loops ensure that we verify every possible candidate efficiently. If no such number exists, we return 0. The approach effectively balances checking for validity while maintaining the smallest possible "good" number.

Approach

Step 1: Initialize Variables

  • We determine the number of cards using n = fronts.length.
  • We set minGood = Infinity, which will store the smallest valid number we find.

Step 2: Iterate Over Each Card

  • We loop through each index i from 0 to n - 1.
  • For each card, we extract the numbers on its front (num1 = fronts[i]) and back (num2 = backs[i]).

Step 3: Check If num1 Is a Good Number

  • We assume num1 is a good number (isValid1 = true).
  • We iterate through all cards (j = 0 to n - 1) and check:
  • If fronts[j] === num1 and backs[j] === num1, it means the number appears on both sides of a card, making it invalid.
  • If this happens, we set isValid1 = false and break out of the loop.

Step 4: Check If num2 Is a Good Number

  • Similar to num1, we assume num2 is valid (isValid2 = true).
  • We iterate through all cards and check if num2 appears on both sides of any card.
  • If so, we set isValid2 = false and break the loop.

Step 5: Update the Minimum Good Number

  • If isValid1 is still true, we update minGood = Math.min(minGood, num1).
  • If isValid2 is still true, we update minGood = Math.min(minGood, num2).

Step 6: Return the Result

  • If we found a valid number, minGood will contain the smallest good number.
  • If no valid number was found, minGood remains Infinity, so we return 0.

Card Flipping Game Dry run - Optimal

Input:

fronts = [1,2,4,4,7]
backs = [1,3,4,1,3]
Step 1: Initialize Variables
n = 5 (number of cards)
minGood = Infinity (initially set to a large number)
Step 2: Iterate Over Each Card
Iteration 1 (i = 0)
num1 = 1, num2 = 1
Check if 1 is a good number:

  • 1 appears on both sides of card 0, so it is not valid.

Iteration 2 (i = 1)
num1 = 2, num2 = 3
Check if 2 is a good number:

  • 2 does not appear on both sides of any card, so it is valid.
    Check if 3 is a good number:
  • 3 does not appear on both sides of any card, so it is valid.
    Update minGood to min(∞, 2, 3) = 2.

Iteration 3 (i = 2)
num1 = 4, num2 = 4
Check if 4 is a good number:

  • 4 appears on both sides of card 2, so it is not valid.

Iteration 4 (i = 3)
num1 = 4, num2 = 1
Check if 4 is a good number:

  • 4 appears on both sides of card 2, so it is not valid.
    Check if 1 is a good number:
  • 1 appears on both sides of card 0, so it is not valid.

Iteration 5 (i = 4)
num1 = 7, num2 = 3
Check if 7 is a good number:

  • 7 does not appear on both sides of any card, so it is valid.
    Check if 3 is a good number:
  • 3 does not appear on both sides of any card, so it is valid.
    Update minGood to min(2, 7, 3) = 2.

Step 3: Return Result
The smallest valid good number is 2.
Output:2

Card Flipping Game Code for All Languages - Optimal
C++ 
class Solution {
public:
    int flipgame(vector<int>& fronts, vector<int>& backs) {
        int n = fronts.size();
        int minGood = INT_MAX;

        // Check all numbers from both fronts and backs
        for (int i = 0; i < n; i++) {
            int num1 = fronts[i];
            int num2 = backs[i];

            // Verify if num1 is a good number
            bool isValid1 = true;
            for (int j = 0; j < n; j++) {
                if (fronts[j] == num1 && backs[j] == num1) {
                    isValid1 = false;
                    break;
                }
            }

            // Verify if num2 is a good number
            bool isValid2 = true;
            for (int j = 0; j < n; j++) {
                if (fronts[j] == num2 && backs[j] == num2) {
                    isValid2 = false;
                    break;
                }
            }

            // Update minimum good number
            if (isValid1) minGood = min(minGood, num1);
            if (isValid2) minGood = min(minGood, num2);
        }

        return (minGood == INT_MAX) ? 0 : minGood;
    }
};

Card Flipping Game code in Java - Optimal 
class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        int n = fronts.length;
        int minGood = Integer.MAX_VALUE;

        // Iterate over both fronts and backs
        for (int i = 0; i < n; i++) {
            int num1 = fronts[i];
            int num2 = backs[i];

            // Check if num1 is a good number
            boolean isValid1 = true;
            for (int j = 0; j < n; j++) {
                if (fronts[j] == num1 && backs[j] == num1) {
                    isValid1 = false;
                    break;
                }
            }

            // Check if num2 is a good number
            boolean isValid2 = true;
            for (int j = 0; j < n; j++) {
                if (fronts[j] == num2 && backs[j] == num2) {
                    isValid2 = false;
                    break;
                }
            }

            // Update the minimum good number
            if (isValid1) minGood = Math.min(minGood, num1);
            if (isValid2) minGood = Math.min(minGood, num2);
        }

        return (minGood == Integer.MAX_VALUE) ? 0 : minGood;
    }
}

Card Flipping Game code in Python - Optimal 
class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        n = len(fronts)
        min_good = float('inf')

        # Iterate over both fronts and backs
        for i in range(n):
            num1 = fronts[i]
            num2 = backs[i]

            # Check if num1 is a good number
            is_valid1 = all(fronts[j] != num1 or backs[j] != num1 for j in range(n))

            # Check if num2 is a good number
            is_valid2 = all(fronts[j] != num2 or backs[j] != num2 for j in range(n))

            # Update the minimum good number
            if is_valid1:
                min_good = min(min_good, num1)
            if is_valid2:
                min_good = min(min_good, num2)

        return 0 if min_good == float('inf') else min_good

Card Flipping Game code in Javascript - Optimal 
class Solution {
    flipgame(fronts, backs) {
        let n = fronts.length;
        let minGood = Infinity;

        // Iterate over both fronts and backs
        for (let i = 0; i < n; i++) {
            let num1 = fronts[i];
            let num2 = backs[i];

            // Check if num1 is a good number
            let isValid1 = true;
            for (let j = 0; j < n; j++) {
                if (fronts[j] === num1 && backs[j] === num1) {
                    isValid1 = false;
                    break;
                }
            }

            // Check if num2 is a good number
            let isValid2 = true;
            for (let j = 0; j < n; j++) {
                if (fronts[j] === num2 && backs[j] === num2) {
                    isValid2 = false;
                    break;
                }
            }

            // Update the minimum good number
            if (isValid1) minGood = Math.min(minGood, num1);
            if (isValid2) minGood = Math.min(minGood, num2);
        }

        return minGood === Infinity ? 0 : minGood;
    }
}

Time Complexity: O(n2)

The brute force approach iterates over both fronts and backs, checking each number for validity by scanning the entire array. This results in nested loops, leading to a time complexity of O(n²):

  • The outer loop runs O(n) times (iterating through fronts and backs).
  • The inner loop checks whether the number appears on both sides for each i, which takes O(n).
  • Thus, the total time complexity is O(n²).

Space Complexity:O(1)

Auxiliary Space Complexity (Extra Memory Used Apart from Input)

  • The algorithm only uses a few integer variables (minGood, num1, num2, and loop counters).
  • These take O(1) constant space, as they don't scale with input size.
  • There are no extra data structures (like arrays, maps, or sets) used for storage.

Total Space Complexity (Input + Auxiliary Space)

  • The input arrays fronts and backs already exist in memory, consuming O(n) space.
  • Since the algorithm doesn’t create additional data structures, the total space complexity is O(n) (from input) + O(1) (auxiliary) = O(n).

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.