LeetCode 822 - Card Flipping Game

In this problem, we are given a collection of cards where each card has two numbers, one on the front and one on the back. Initially, every card is placed with its front side facing upward.

leetcodemediumarrayhash-table

LeetCode Problem 822

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

In this problem, we are given a collection of cards where each card has two numbers, one on the front and one on the back. Initially, every card is placed with its front side facing upward. We are allowed to flip any subset of cards, including flipping none of them or flipping all of them. After choosing the final orientation of every card, we want to identify a good integer.

A number is considered good if it satisfies two conditions simultaneously. First, the number must appear facing down on at least one card. Second, the same number must not appear facing up on any card. Among all such valid numbers, we must return the smallest possible one. If no number can satisfy these conditions regardless of how we flip the cards, we return 0.

The input consists of two integer arrays, fronts and backs, where fronts[i] represents the number currently shown on the front of the i-th card and backs[i] represents the number printed on the opposite side. The cards are indexed from 0 to n - 1.

The constraints are relatively small. We know that n ≤ 1000, and each card value is between 1 and 2000. This tells us that even quadratic solutions may be feasible, but we should still aim for a clean and efficient approach.

The most important observation involves cards where fronts[i] == backs[i]. Such numbers are problematic because no matter how the card is flipped, that same number will always remain visible on one side. Therefore, these values can never become good integers, since they are guaranteed to be facing up somewhere.

Several edge cases deserve attention. A single card where the front and back values are identical immediately forces the answer to 0, since the number can never disappear from the visible side. Another tricky case occurs when all candidate numbers are invalidated because they appear on identical front-back cards. We must also handle situations where flipping cards creates multiple valid candidates and ensure we return the minimum one.

Approaches

Brute Force Approach

A brute-force solution would try every possible flipping configuration. Since each card can either remain as-is or be flipped, there are 2^n possible states.

For every configuration, we would determine which numbers are facing up and which are facing down. Then we would identify all numbers that appear facing down but never appear facing up, select the minimum one, and compare it against the global minimum over all configurations.

This approach is correct because it explicitly evaluates every legal arrangement of cards. However, it becomes computationally infeasible very quickly. Even with only n = 30, there are already over one billion possible states. Since n can be as large as 1000, exhaustive search is impossible.

Optimal Approach

The key insight is recognizing which numbers are permanently invalid.

If a card has the same number on both sides, such as [4,4], then regardless of whether we flip the card, the number 4 will always be visible on that card. Therefore, 4 can never be a good integer because one of the requirements is that the number must not appear facing up anywhere.

We first collect all such permanently invalid numbers into a set called banned.

After identifying invalid numbers, we examine every number appearing in both fronts and backs. Any number that is not banned is potentially achievable as a good integer. Since we only need the smallest valid number, we simply track the minimum candidate.

This works because for any non-banned number, we can always orient cards in a way that prevents it from appearing face up while still allowing it to exist face down somewhere.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n · n) O(n) Enumerates every flipping configuration
Optimal O(n) O(n) Uses a set of permanently invalid numbers

Algorithm Walkthrough

  1. Create a set called banned to store numbers that can never become good integers.
  2. Traverse all cards once. If fronts[i] == backs[i], add that number to banned. This is done because such numbers are always visible no matter how the card is flipped.
  3. Initialize a variable minimum_good with a very large value, such as infinity.
  4. Traverse every number in both fronts and backs.
  5. For each number, check whether it is absent from banned. If it is valid, update minimum_good with the smaller value.
  6. After processing all numbers, check whether minimum_good was updated. If not, return 0 because no good integer exists.
  7. Otherwise, return the smallest valid number.

Why it works

The core invariant is that any number appearing on a card with identical front and back values can never be hidden from the visible side. Therefore, such numbers are permanently disqualified.

For any number not in the banned set, we can always choose orientations of cards so that the number appears only on the hidden side of at least one card and never on the visible side. Since we check all possible candidate values and return the smallest valid one, the algorithm always produces the correct minimum good integer.

Python Solution

from typing import List

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        banned = set()

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

        minimum_good = float("inf")

        for number in fronts:
            if number not in banned:
                minimum_good = min(minimum_good, number)

        for number in backs:
            if number not in banned:
                minimum_good = min(minimum_good, number)

        return 0 if minimum_good == float("inf") else minimum_good

The implementation begins by constructing the banned set. We iterate through corresponding front and back values using zip(fronts, backs). Whenever both sides of a card contain the same number, we add it to the set because that number can never be hidden.

Next, we search for the smallest candidate number. We iterate through both arrays and ignore any banned values. If a number is valid, we compare it against the current minimum.

Finally, if no valid number was found, the answer remains infinity and we return 0. Otherwise, we return the smallest discovered candidate.

Go Solution

func flipgame(fronts []int, backs []int) int {
	banned := make(map[int]bool)

	for i := 0; i < len(fronts); i++ {
		if fronts[i] == backs[i] {
			banned[fronts[i]] = true
		}
	}

	const INF = int(1e9)
	minimumGood := INF

	for _, number := range fronts {
		if !banned[number] && number < minimumGood {
			minimumGood = number
		}
	}

	for _, number := range backs {
		if !banned[number] && number < minimumGood {
			minimumGood = number
		}
	}

	if minimumGood == INF {
		return 0
	}

	return minimumGood
}

The Go implementation mirrors the Python logic closely. Since Go does not have a built-in set type, we use map[int]bool to simulate a hash set for banned numbers.

Instead of Python's float("inf"), we use a large sentinel integer value (1e9) because all card values are at most 2000. This safely represents an impossible upper bound.

No special handling for integer overflow is required because values remain very small relative to Go's integer limits.

Worked Examples

Example 1

Input:

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

Step 1: Build the banned set

We check each card:

Card Index Front Back Equal? Banned Set
0 1 1 Yes {1}
1 2 3 No {1}
2 4 4 Yes {1, 4}
3 4 1 No {1, 4}
4 7 3 No {1, 4}

At the end:

banned = {1, 4}

Step 2: Search for the minimum valid number

Check all numbers from both arrays:

Number Banned? Current Minimum
1 Yes INF
2 No 2
4 Yes 2
4 Yes 2
7 No 2
1 Yes 2
3 No 2
4 Yes 2
1 Yes 2
3 No 2

Final answer:

2

Example 2

Input:

fronts = [1]
backs  = [1]

Step 1: Build the banned set

Card Index Front Back Equal? Banned Set
0 1 1 Yes {1}

Step 2: Search for valid numbers

Both 1s are banned.

No candidate exists.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) We traverse the arrays a constant number of times
Space O(n) The banned set may store up to n unique numbers

The algorithm performs only linear scans across the input arrays. Building the banned set takes O(n), and scanning both arrays for the minimum candidate also takes O(n). Since hash set lookups are O(1) on average, the overall running time remains linear.

The extra memory comes from the banned set. In the worst case, every card may contribute a unique banned number, resulting in O(n) additional space.

Test Cases

from typing import List

class Solution:
    def flipgame(self, fronts: List[int], backs: List[int]) -> int:
        banned = set()

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

        minimum_good = float("inf")

        for number in fronts:
            if number not in banned:
                minimum_good = min(minimum_good, number)

        for number in backs:
            if number not in banned:
                minimum_good = min(minimum_good, number)

        return 0 if minimum_good == float("inf") else minimum_good

solution = Solution()

assert solution.flipgame([1,2,4,4,7], [1,3,4,1,3]) == 2  # Example 1
assert solution.flipgame([1], [1]) == 0  # Example 2
assert solution.flipgame([1], [2]) == 1  # Single card, different values
assert solution.flipgame([2,2], [2,2]) == 0  # All numbers banned
assert solution.flipgame([5,1,2], [6,7,8]) == 1  # Smallest valid number exists
assert solution.flipgame([10,20,30], [30,20,10]) == 10  # Multiple candidates
assert solution.flipgame([4,4,4], [4,4,4]) == 0  # Repeated banned values
assert solution.flipgame([1000], [2000]) == 1000  # Large valid values
assert solution.flipgame([3,5,7], [2,4,6]) == 2  # Minimum comes from backs
Test Why
[1,2,4,4,7], [1,3,4,1,3] Validates provided example
[1], [1] Ensures no good integer returns 0
[1], [2] Tests simplest non-trivial case
[2,2], [2,2] Verifies fully banned inputs
[5,1,2], [6,7,8] Ensures smallest valid candidate is selected
[10,20,30], [30,20,10] Tests multiple candidate values
[4,4,4], [4,4,4] Confirms repeated banned numbers behave correctly
[1000], [2000] Checks upper-range values
[3,5,7], [2,4,6] Verifies answer can come from backs

Edge Cases

One important edge case occurs when a card has identical values on both sides. For example, [4,4] means the number 4 can never be hidden because flipping the card changes nothing. A naive implementation may mistakenly treat 4 as valid, but our algorithm explicitly places such values in the banned set.

Another tricky scenario happens when every possible number becomes banned. Consider fronts = [2,2] and backs = [2,2]. Since 2 is always visible, no good integer exists. Our implementation handles this correctly by leaving minimum_good unchanged and returning 0.

A third edge case occurs when the minimum valid number appears only on the back side of cards. For example, fronts = [3,5,7] and backs = [2,4,6] should return 2. A flawed solution that checks only front values would fail here. Our implementation scans both arrays, ensuring all valid candidates are considered.