# Card Flipping Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/card-flipping-game)
Canonical: https://scaleengineer.com/dsa/problems/card-flipping-game
**Data structures:** Array, Hash Table
---
## Problem
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`.

**Example 1:**

**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.

**Example 2:**

**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`

# Approaches
## Brute-Force with Bitmasking
This approach explores every possible combination of card flips. Since each of the `n` cards can either be in its original state or flipped, there are `2^n` total configurations. For each configuration, we determine the set of numbers facing up and the set of numbers facing down. We then find the minimum number that is in the "down" set but not in the "up" set. The overall minimum across all `2^n` configurations is the answer.
**Time:** O(2^n * n). There are `2^n` configurations. For each, we iterate through `n` cards to build the sets (O(n)) and then iterate through the down-facing numbers (at most `n`) to find the minimum good number (O(n)). Thus, the total time is O(2^n * n). · **Space:** O(n). The sets `up_numbers` and `down_numbers` can store up to `n` elements each.
**Pros:** Conceptually simple, as it directly models the problem statement by trying all possibilities.
**Cons:** Extremely inefficient. The exponential time complexity makes it infeasible for the given constraints (`n` up to 1000). It will result in a "Time Limit Exceeded" error.
### Explanation
We use a bitmask, an integer from `0` to `2^n - 1`, to represent a specific configuration of flips. If the `j`-th bit is 0, card `j` is not flipped. If it's 1, card `j` is flipped. The algorithm iterates through all `2^n` masks. For each mask, it constructs two sets: `up_numbers` and `down_numbers`. It iterates through each card `j` from 0 to `n-1`. Based on the `j`-th bit of the mask, it adds the appropriate `fronts[j]` or `backs[j]` to the `up_numbers` and `down_numbers` sets. After building the sets for a configuration, it finds the minimum "good" number for that specific configuration by iterating through all numbers in `down_numbers` and checking if they are absent from `up_numbers`. A global minimum is maintained and updated after processing each of the `2^n` configurations. If no good number is ever found, we return 0.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        int n = fronts.length;
        int minGood = Integer.MAX_VALUE;

        for (int i = 0; i < (1 << n); i++) { // Iterate through all 2^n flip combinations
            Set<Integer> upNumbers = new HashSet<>();
            Set<Integer> downNumbers = new HashSet<>();

            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) { // Card j is flipped
                    upNumbers.add(backs[j]);
                    downNumbers.add(fronts[j]);
                } else { // Card j is not flipped
                    upNumbers.add(fronts[j]);
                    downNumbers.add(backs[j]);
                }
            }

            int currentMinGood = Integer.MAX_VALUE;
            for (int num : downNumbers) {
                if (!upNumbers.contains(num)) {
                    currentMinGood = Math.min(currentMinGood, num);
                }
            }
            minGood = Math.min(minGood, currentMinGood);
        }

        return minGood == Integer.MAX_VALUE ? 0 : minGood;
    }
}
```
### Algorithm
- Initialize `min_good` to a very large value.
- Loop through all integers `mask` from `0` to `2^n - 1`.
    - Create an empty set `up_numbers` and `down_numbers`.
    - For each card `j` from `0` to `n-1`:
        - If the `j`-th bit of `mask` is set, it means flip card `j`. Add `backs[j]` to `up_numbers` and `fronts[j]` to `down_numbers`.
        - Otherwise, do not flip. Add `fronts[j]` to `up_numbers` and `backs[j]` to `down_numbers`.
    - Initialize `current_min_good` to a very large value.
    - For each `num` in `down_numbers`:
        - If `num` is not in `up_numbers`, update `current_min_good = min(current_min_good, num)`.
    - Update `min_good = min(min_good, current_min_good)`.
- If `min_good` is still the large initial value, return 0. Otherwise, return `min_good`.

## Test Each Candidate Number
Instead of iterating through all possible flip configurations, we can iterate through all possible numbers that could be the answer. The candidates for a good number must be numbers that appear on the cards. We can collect all unique numbers from both `fronts` and `backs` arrays and test each one to see if it can be a "good" number.
**Time:** O(U * n), where `U` is the number of unique values on the cards and `n` is the number of cards. In the worst case, `U` can be `2n`, leading to O(n^2). This is acceptable for the given constraints. · **Space:** O(U) or O(n), where U is the number of unique values on the cards. This is for storing the `candidates` set.
**Pros:** Much more efficient than the brute-force approach.; Solves the problem within typical time limits.
**Cons:** Not the most optimal solution as it involves a nested loop structure. The logic can be streamlined.
### Explanation
A number `x` can be a good number if and only if we can arrange the cards such that `x` is never facing up. This is impossible only if there is a card that has `x` on both its front and back. If `fronts[i] == backs[i] == x`, then card `i` will always have `x` facing up, regardless of flips. The algorithm first gathers all unique numbers from `fronts` and `backs` into a candidate set. Then, for each candidate number `c`, it checks if there exists any card `i` where `fronts[i] == backs[i] == c`. If no such card exists for `c`, it means `c` can be made a good number. We can always flip any card showing `c` on its front to hide it on the back. Since `c` is a candidate, it's present on at least one card, so it can be made to face down. We keep track of the minimum candidate that satisfies this condition.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        Set<Integer> candidates = new HashSet<>();
        for (int num : fronts) {
            candidates.add(num);
        }
        for (int num : backs) {
            candidates.add(num);
        }

        int minGood = Integer.MAX_VALUE;
        for (int candidate : candidates) {
            boolean isPossible = true;
            for (int i = 0; i < fronts.length; i++) {
                if (fronts[i] == candidate && backs[i] == candidate) {
                    isPossible = false;
                    break;
                }
            }
            if (isPossible) {
                minGood = Math.min(minGood, candidate);
            }
        }

        return minGood == Integer.MAX_VALUE ? 0 : minGood;
    }
}
```
### Algorithm
- Create a `Set` called `candidates` and populate it with all unique numbers from `fronts` and `backs`.
- Initialize `min_good` to a very large value.
- For each `candidate` in the `candidates` set:
    - Assume it's possible to make `candidate` a good number (`is_possible = true`).
    - Iterate through each card `i` from `0` to `n-1`.
        - If `fronts[i] == candidate` and `backs[i] == candidate`, it's impossible. Set `is_possible = false` and break the inner loop.
    - If `is_possible` remains `true`, it means `candidate` can be a good number. Update `min_good = min(min_good, candidate)`.
- If `min_good` is still the large initial value, return 0. Otherwise, return `min_good`.

## Single Pass with a Set of Invalid Numbers
This is the most efficient approach. The key insight is that a number can be a "good" number if and only if it does not appear on both sides of the same card. If a number `x` is on both the front and back of a card, it's impossible to hide it, so it can never be good. We can first identify all such "invalid" numbers. Then, the answer is simply the minimum number among all card faces that is not in our set of invalid numbers.
**Time:** O(n). The first pass to populate the `invalid` set takes O(n). The next two passes to check all numbers in `fronts` and `backs` also take O(n). Set operations (add, contains) take O(1) on average. The total time is linear. · **Space:** O(k), where `k` is the number of cards with the same number on both sides. In the worst case, `k` can be up to `n`, so the space complexity is O(n).
**Pros:** Optimal time complexity. It solves the problem in a single effective pass over the data.; Simple and elegant logic.
**Cons:** Requires extra space for the `HashSet`, although this is necessary for the time efficiency.
### Explanation
The algorithm works in two main steps. First, it identifies all numbers that are impossible to make "good". It iterates through all the cards once. If for any card `i`, `fronts[i] == backs[i]`, the number `fronts[i]` is added to a `HashSet` of invalid numbers. Second, it finds the minimum possible good number. It iterates through all numbers in both the `fronts` and `backs` arrays. For each number, it checks if it is present in the `invalid` set. If it's not, it's a valid candidate for a good number. The algorithm keeps track of the minimum such valid candidate found. If after checking all numbers, no valid candidate was found, it means no good number exists, and we return 0. Otherwise, we return the minimum found.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int flipgame(int[] fronts, int[] backs) {
        Set<Integer> invalid = new HashSet<>();
        for (int i = 0; i < fronts.length; i++) {
            if (fronts[i] == backs[i]) {
                invalid.add(fronts[i]);
            }
        }

        int minGood = Integer.MAX_VALUE;

        for (int num : fronts) {
            if (!invalid.contains(num)) {
                minGood = Math.min(minGood, num);
            }
        }

        for (int num : backs) {
            if (!invalid.contains(num)) {
                minGood = Math.min(minGood, num);
            }
        }

        return minGood == Integer.MAX_VALUE ? 0 : minGood;
    }
}
```
### Algorithm
- Create an empty `HashSet` called `invalid`.
- Iterate through the cards from `i = 0` to `n-1`. If `fronts[i] == backs[i]`, add `fronts[i]` to the `invalid` set.
- Initialize `min_good` to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through the `fronts` array. For each `num`, if `num` is not in `invalid`, update `min_good = min(min_good, num)`.
- Iterate through the `backs` array. For each `num`, if `num` is not in `invalid`, update `min_good = min(min_good, num)`.
- If `min_good` remains at its initial large value, return 0. Otherwise, return `min_good`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int Flipgame(int[] fronts, int[] backs) {
        var s = new HashSet < int > ();
        int n = fronts.Length;
        for (int i = 0; i < n; ++i) {
            if (fronts[i] == backs[i]) {
                s.Add(fronts[i]);
            }
        }
        int ans = 9999;
        for (int i = 0; i < n; ++i) {
            if (!s.Contains(fronts[i])) {
                ans = Math.Min(ans, fronts[i]);
            }
            if (!s.Contains(backs[i])) {
                ans = Math.Min(ans, backs[i]);
            }
        }
        return ans % 9999;
    }
}
```

### Java

```java
class Solution {
public
  int flipgame(int[] fronts, int[] backs) {
    Set<Integer> s = new HashSet<>();
    int n = fronts.length;
    for (int i = 0; i < n; ++i) {
      if (fronts[i] == backs[i]) {
        s.add(fronts[i]);
      }
    }
    int ans = 9999;
    for (int v : fronts) {
      if (!s.contains(v)) {
        ans = Math.min(ans, v);
      }
    }
    for (int v : backs) {
      if (!s.contains(v)) {
        ans = Math.min(ans, v);
      }
    }
    return ans % 9999;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int flipgame(vector<int> &fronts, vector<int> &backs) {
    unordered_set<int> s;
    int n = fronts.size();
    for (int i = 0; i < n; ++i) {
      if (fronts[i] == backs[i]) {
        s.insert(fronts[i]);
      }
    }
    int ans = 9999;
    for (int &v : fronts) {
      if (!s.count(v)) {
        ans = min(ans, v);
      }
    }
    for (int &v : backs) {
      if (!s.count(v)) {
        ans = min(ans, v);
      }
    }
    return ans % 9999;
  }
};

```

### Python

```python
class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int: s = {a for a, b in zip(fronts, backs) if a == b} return min((x for x in chain(fronts, backs) if x not in s), default=0)

```