# LeetCode 822: Card Flipping Game

## Problem Restatement

We are given two arrays:

```python
fronts
backs
```

Each index represents one card.

For card `i`:

```python
fronts[i]
```

is the number on the front side, and:

```python
backs[i]
```

is the number on the back side.

We may flip any number of cards. A flip swaps the front and back number of that card.

After flipping, we choose one card. If the number on the back of that chosen card does not appear on the front of any card, then that number is good.

Return the smallest possible good number. If no good number exists, return `0`. The official statement gives `fronts = [1,2,4,4,7]`, `backs = [1,3,4,1,3]`, with answer `2`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two arrays `fronts` and `backs` |
| Output | Smallest good number, or `0` |
| Operation | Flip any number of cards |
| Good number | A back-side number that does not appear on any front side |
| Constraint | `fronts[i]` and `backs[i]` are positive integers |

## Examples

Example 1:

```python
fronts = [1, 2, 4, 4, 7]
backs  = [1, 3, 4, 1, 3]
```

If we flip the second card, the arrays become:

```python
fronts = [1, 3, 4, 4, 7]
backs  = [1, 2, 4, 1, 3]
```

Now `2` is on the back of a card, and `2` does not appear on any front side.

So the answer is:

```python
2
```

Example 2:

```python
fronts = [1]
backs  = [1]
```

No matter how we flip the only card, `1` is always on the front.

So there is no good number.

The answer is:

```python
0
```

## First Thought: Try Every Flip Pattern

There are `n` cards.

Each card has two choices:

1. Keep it as it is.
2. Flip it.

That gives:

```python
2^n
```

possible configurations.

For each configuration, we could check every back number and see whether it appears on the front.

This is correct, but too slow.

## Key Insight

A number is impossible only when it appears on both sides of the same card.

For example:

```python
fronts[i] == backs[i] == 4
```

Then `4` will always be visible on the front of that card, no matter whether we flip it.

So `4` can never be good.

Now consider a number that does not appear on both sides of any single card.

If it appears on the front of some cards, we can flip those cards so the number moves to the back. Since no card has that same number on both sides, flipping those cards will not leave that number visible on the front of the same card.

Therefore, the answer is the smallest number that appears anywhere on the cards but is not blocked by a same-front-and-back card.

## Algorithm

Create a set of blocked numbers:

```python
blocked = set()
```

For each card `i`:

```python
if fronts[i] == backs[i]:
    blocked.add(fronts[i])
```

Then scan every number in both `fronts` and `backs`.

If a number is not in `blocked`, it is a candidate.

Return the smallest candidate.

If no candidate exists, return `0`.

## Correctness

Any number that appears on both sides of the same card can never be good. That card always shows the number on its front side, regardless of flipping. The algorithm marks every such number as blocked.

Now take any number that is not blocked. For every card where this number appears on the front, the back side must contain a different number. We can flip each such card, moving the candidate number away from the front. Cards that do not have this number on the front do not need to be changed. After these flips, the candidate number appears on no front side.

Since the candidate appears somewhere in `fronts` or `backs`, it can be placed on the back of at least one card. Therefore, every unblocked number appearing on any card can be good.

The algorithm returns the smallest such unblocked number, so it returns the smallest possible good number. If no such number exists, no good number exists, so returning `0` is correct.

## Complexity

Let `n = len(fronts)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the cards a constant number of times |
| Space | `O(n)` | The blocked set may store up to `n` values |

## Implementation

```python
class Solution:
    def flipgame(self, fronts: list[int], backs: list[int]) -> int:
        blocked = set()

        for front, back in zip(fronts, backs):
            if front == back:
                blocked.add(front)

        answer = float("inf")

        for value in fronts:
            if value not in blocked:
                answer = min(answer, value)

        for value in backs:
            if value not in blocked:
                answer = min(answer, value)

        if answer == float("inf"):
            return 0

        return answer
```

## Code Explanation

First, we collect numbers that can never be good:

```python
blocked = set()
```

A number is blocked when it appears on both sides of the same card:

```python
if front == back:
    blocked.add(front)
```

Then we search all visible and hidden numbers as candidates:

```python
for value in fronts:
```

and:

```python
for value in backs:
```

If a value is not blocked, it can become good:

```python
if value not in blocked:
    answer = min(answer, value)
```

If no candidate was found, return `0`:

```python
if answer == float("inf"):
    return 0
```

Otherwise, return the smallest candidate.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.flipgame(
        [1, 2, 4, 4, 7],
        [1, 3, 4, 1, 3],
    ) == 2

    assert s.flipgame(
        [1],
        [1],
    ) == 0

    assert s.flipgame(
        [1, 2],
        [2, 1],
    ) == 1

    assert s.flipgame(
        [2, 2, 3],
        [2, 4, 3],
    ) == 4

    assert s.flipgame(
        [1, 1],
        [1, 2],
    ) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Official sample | Finds smallest valid number after possible flips |
| Single same-sided card | No good number exists |
| Crossed cards | Both values are possible, choose the smaller |
| Some blocked values | Skips values that appear on both sides of one card |
| Repeated blocked front value | Finds valid value from a back side |