Card Flipping Game — Solution in Python, Java & C++
Card Flipping Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Google.
Card Flipping Game is a medium coding problem on arrays and hash table, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have n cards on a table. Card i has the positive integer fronts[i] on its face and backs[i] on its reverse, and it starts face up.
You may flip any number of cards (possibly none). After flipping, an integer is good if it is printed on the back of some card and it is not showing on the front of any card.
Return the smallest integer that can be made good by some choice of flips, or 0 if no integer can ever be good.
Example 1
Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: Flip the second card: it now shows 3 and hides 2. No front shows 2, so 2 is good. 1 can never be good because the first card has 1 on both faces.
Example 2
Input: fronts = [1], backs = [1]
Output: 0
Explanation: The only number, 1, is on both faces of the same card, so it always shows.
Example 3
Input: fronts = [5,3], backs = [3,5]
Output: 3
Explanation: Flip the second card so it shows 5 and hides 3. The fronts now read 5 and 5, and 3 sits on a back, so 3 is good.
Constraints
n == fronts.length == backs.length1 <= n <= 10001 <= fronts[i], backs[i] <= 2000
Hints for Card Flipping Game
Hint 1
Which numbers can never be good, whatever you flip?
Hint 2
A card with the same number on both faces always shows that number on its front.
Hint 3
Every other number can be made good by turning each card that carries it so the number is hidden. Take the smallest number that is not on a same-faced card.
How to solve Card Flipping Game
A number x is blocked only when some card has x on both faces — that card shows x whatever you do. Any unblocked x that appears anywhere can be made good, so the answer is the smallest unblocked number.
Approach
- Collect every value with
fronts[i] == backs[i]into a blocked set. - Scan all values in
frontsandbacks; keep the smallest that is not blocked. - Return it, or 0 if every value is blocked.
Why it works
If x is not blocked, every card carrying x has a different number on its other face, so turn each such card to show that other number. Then no front shows x, and at least one back carries it — x is good. Conversely, a blocked x always shows on a front.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Only cards with equal faces block a number; a number appearing on several different cards is still achievable.
- Candidates come from both arrays — a number seen only on a front can be flipped to the back.
Reference solution
Python
from typing import List
def flipgame(fronts: List[int], backs: List[int]) -> int:
blocked = {f for f, b in zip(fronts, backs) if f == b}
best = 0
for x in fronts + backs:
if x not in blocked and (best == 0 or x < best):
best = x
return bestJava
public static int flipgame(int[] fronts, int[] backs) {
Set<Integer> blocked = new HashSet<>();
for (int i = 0; i < fronts.length; i++) if (fronts[i] == backs[i]) blocked.add(fronts[i]);
int best = 0;
for (int i = 0; i < fronts.length; i++) {
int a = fronts[i], b = backs[i];
if (!blocked.contains(a) && (best == 0 || a < best)) best = a;
if (!blocked.contains(b) && (best == 0 || b < best)) best = b;
}
return best;
}C++
int flipgame(vector<int>& fronts, vector<int>& backs) {
unordered_set<int> blocked;
for (size_t i = 0; i < fronts.size(); i++) if (fronts[i] == backs[i]) blocked.insert(fronts[i]);
int best = 0;
for (size_t i = 0; i < fronts.size(); i++) {
int a = fronts[i], b = backs[i];
if (!blocked.count(a) && (best == 0 || a < best)) best = a;
if (!blocked.count(b) && (best == 0 || b < best)) best = b;
}
return best;
}JavaScript
var flipgame = function(fronts, backs) {
var blocked = new Set();
for (var i = 0; i < fronts.length; i++) if (fronts[i] === backs[i]) blocked.add(fronts[i]);
var best = 0;
for (var j = 0; j < fronts.length; j++) {
var a = fronts[j], b = backs[j];
if (!blocked.has(a) && (best === 0 || a < best)) best = a;
if (!blocked.has(b) && (best === 0 || b < best)) best = b;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets