LeetCode 822: Card Flipping Game

Problem Restatement

We are given two arrays:

fronts
backs

Each index represents one card.

For card i:

fronts[i]

is the number on the front side, and:

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

Examples

Example 1:

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

If we flip the second card, the arrays become:

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:

2

Example 2:

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:

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:

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:

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:

blocked = set()

For each card i:

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

Implementation

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:

blocked = set()

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

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

Then we search all visible and hidden numbers as candidates:

for value in fronts:

and:

for value in backs:

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

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

If no candidate was found, return 0:

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

Otherwise, return the smallest candidate.

Testing

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()