Watch 10 video solutions for Card Flipping Game, a medium level problem involving Array, Hash Table. This walkthrough by 大果子coding has 561 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 2000Problem 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 | 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. |