Card Flipping Game - Solution & Explanation
Problem Statement
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.length1 <= n <= 10001 <= fronts[i], backs[i] <= 2000
Approach Overview
Problem Overview: You are given two arrays fronts and backs representing numbers on each side of cards. You may flip any card. The goal is to find the smallest number that can appear on the back of a card while not appearing on the front of any card after choosing an orientation.
Approach 1: Direct Comparison Approach (O(n2) time, O(1) space)
Start by treating every number in fronts and backs as a potential candidate. For each candidate value x, scan all cards and check whether x is forced onto the front of some card. If a card has fronts[i] == backs[i] == x, that value can never be hidden because flipping the card still leaves x on the front. Such values are invalid. For each remaining candidate, verify that it can appear on the back of at least one card while not being forced on the front anywhere else. This approach works with simple iteration and comparisons but requires nested scanning, leading to O(n2) time.
Approach 2: Set-Based Approach (O(n) time, O(n) space)
The key observation: numbers that appear on both sides of the same card (fronts[i] == backs[i]) are permanently visible. No flip can hide them from the front. Collect all such numbers into a hash set called banned. Then iterate through both arrays and look for the smallest value not present in this set. Any number not banned can be arranged so it appears on the back of some card while staying off the front of all cards by flipping appropriately.
This method relies on constant-time hash lookups and a single pass through the arrays. You iterate once to build the banned set and once more to find the smallest valid value. The result is an efficient O(n) time solution with O(n) extra space using a hash table. The problem itself is mainly about recognizing the constraint created by identical card sides and using a array scan combined with a set to filter invalid candidates.
Recommended for interviews: The set-based approach. Interviewers expect you to notice that cards with identical front and back values create unavoidable numbers. Storing them in a hash set and scanning the arrays once demonstrates strong problem decomposition and efficient use of hash lookups. The direct comparison method shows correct reasoning but lacks scalability.
Approach 1: Set-Based Approach
This approach involves using a set to track numbers that appear on both sides of the same card, and another to track potential good numbers that appear on the back of any card. The goal is to identify the smallest number that can only appear on the back and not on any front.
In this C implementation, two boolean arrays (bothSides and isBack) are used to track numbers appearing on both sides of a card and those available on the back side, respectively. The main loop over the cards checks if the number on the front or back can potentially be a 'good' integer by ensuring it doesn't appear on both sides and picks the minimum possible value.
Complexity
Time Complexity: O(n), where n is the number of cards.
Space Complexity: O(1), due to fixed-size additional arrays used.
Approach 2: Direct Comparison Approach
This approach iteratively checks each card to determine if its front or back can be good. It then selects the smallest number not facing front on any card but still appears on the back of some card, by direct value comparisons.
The solution in C compares each card's back against the current minimum good integer unless it's on both sides. It ensures the smallest obtainable integer by tracking with two variables, one for fronts and one for matching potential backs.
Complexity
Time Complexity: O(n), processing each card pair.
Space Complexity: O(1), no additional data structures used.
Approach 3: Hash Table
We observe that for position i, if fronts[i] is equal to backs[i], then it certainly does not satisfy the condition.
Therefore, we first identify all elements that appear the same on both the front and back sides and record them in a hash set s.
Next, we iterate through all elements in both the front and back arrays. For any element x that is not in the hash set s, we update the minimum value of the answer.
Finally, if we find any element that satisfies the condition, we return the minimum answer; otherwise, we return 0.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the arrays.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Set-Based Approach | Time Complexity: O(n), where n is the number of cards. |
| Direct Comparison Approach | Time Complexity: O(n), processing each card pair. |
| Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Comparison Approach | O(n²) | O(1) | Useful for understanding the constraint logic without extra data structures. |
| Set-Based Approach | O(n) | O(n) | Best general solution. Efficient for large inputs using hash lookups. |
Video Solution
Leetcode 822 Card Flipping Game - Medium • 大果子coding • 565 views views
Watch 6 more video solutions →Frequently Asked Questions
Is Card Flipping Game easy or hard?
Card Flipping Game Python/Java solution
How to solve Card Flipping Game in O(n)?
What is the best approach for Card Flipping Game?
Is Card Flipping Game asked at Google/Amazon/Meta?
What data structure is used in Card Flipping Game?
What is the time complexity of Card Flipping Game?
Ready to solve this problem?
Practice Card Flipping Game with our built-in code editor and test cases.
Practice on FleetCode