Card Flipping Game solution and explanation
Google
6 more videos on this problem
Leetcode 822 Card Flipping Game - Medium大果子coding · 7:27 · 565 views
822. Card Flipping Game (Leetcode Medium)Programming Live with Larry · 8:50 · 424 views
Leetcode 822. Card Flipping Game (simulation)LetsCode · 9:53 · 422 views
822. Card Flipping Game - Python - One LineAlgoPrepMaster · 1:04 · 48 views
No Sound Leetcode 822: Card Flipping GameExtremeProgrammer · 1:08 · 33 views
LeetCode 822: Card Flipping GameAlitaCode · 28:51 · 16 views
LeetCode Problem #822 Card Flipping Game神戸万事屋 · 0:36
The problem
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.
def min_good_integer(fronts, backs):
same = set()
potential = set()
for f, b in zip(fronts, backs):
if f == b:
same.add(f)
else:
potential.add(b)
result = float('inf')
for num in potential:
if num not in same:
result = min(result, num)
return 0 if result == float('inf') else result
fronts = [1, 2, 4, 4, 7]
backs = [1, 3, 4, 1, 3]
print(min_good_integer(fronts, backs))import java.util.HashSet;
import java.util.Set;
public class CardFlippingGame {
public static int minGoodInteger(int[] fronts, int[] backs) {
Set<Integer> same = new HashSet<>();
Set<Integer> potential = new HashSet<>();
for (int i = 0; i < fronts.length; i++) {
if (fronts[i] == backs[i]) {
same.add(fronts[i]);
} else {
potential.add(backs[i]);
}
}
int result = Integer.MAX_VALUE;
for (int number : potential) {
if (!same.contains(number)) {
result = Math.min(result, number);
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
public static void main(String[] args) {
int[] fronts = {1, 2, 4, 4, 7};
int[] backs = {1, 3, 4, 1, 3};
System.out.println(minGoodInteger(fronts, backs));
}
}#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
int minGoodInteger(std::vector<int>& fronts, std::vector<int>& backs) {
std::unordered_set<int> same, potential;
int n = fronts.size();
for (int i = 0; i < n; ++i) {
if (fronts[i] == backs[i]) {
same.insert(fronts[i]);
} else {
potential.insert(backs[i]);
}
}
int res = INT_MAX;
for (auto& num : potential) {
if (!same.count(num)) {
res = std::min(res, num);
}
}
return res == INT_MAX ? 0 : res;
}
int main() {
std::vector<int> fronts = {1, 2, 4, 4, 7};
std::vector<int> backs = {1, 3, 4, 1, 3};
std::cout << minGoodInteger(fronts, backs) << std::endl;
return 0;
}function minGoodInteger(fronts, backs) {
let same = new Set();
let potential = new Set();
for (let i = 0; i < fronts.length; i++) {
if (fronts[i] === backs[i]) {
same.add(fronts[i]);
} else {
potential.add(backs[i]);
}
}
let result = Infinity;
for (let num of potential) {
if (!same.has(num)) {
result = Math.min(num, result);
}
}
return result === Infinity ? 0 : result;
}
let fronts = [1, 2, 4, 4, 7];
let backs = [1, 3, 4, 1, 3];
console.log(minGoodInteger(fronts, backs));#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
int minGoodInteger(int* fronts, int* backs, int n) {
bool bothSides[2001] = {false};
bool isBack[2001] = {false};
for (int i = 0; i < n; i++) {
if (fronts[i] == backs[i]) {
bothSides[fronts[i]] = true;
} else {
isBack[backs[i]] = true;
}
}
int result = INT_MAX;
for (int i = 0; i < n; i++) {
if (!bothSides[backs[i]] && !bothSides[fronts[i]]) {
if (isBack[backs[i]]) {
if (backs[i] < result) {
result = backs[i];
}
}
if (isBack[fronts[i]]) {
if (fronts[i] < result) {
result = fronts[i];
}
}
}
}
return result == INT_MAX ? 0 : result;
}
int main() {
int fronts[] = {1, 2, 4, 4, 7};
int backs[] = {1, 3, 4, 1, 3};
int n = 5;
printf("%d\n", minGoodInteger(fronts, backs, n));
return 0;
}using System;
using System.Collections.Generic;
class CardFlippingGame {
public static int MinGoodInteger(int[] fronts, int[] backs) {
HashSet<int> same = new HashSet<int>();
HashSet<int> potential = new HashSet<int>();
for (int i = 0; i < fronts.Length; i++) {
if (fronts[i] == backs[i]) {
same.Add(fronts[i]);
} else {
potential.Add(backs[i]);
}
}
int result = int.MaxValue;
foreach (int num in potential) {
if (!same.Contains(num)) {
result = Math.Min(result, num);
}
}
return result == int.MaxValue ? 0 : result;
}
static void Main() {
int[] fronts = {1, 2, 4, 4, 7};
int[] backs = {1, 3, 4, 1, 3};
Console.WriteLine(MinGoodInteger(fronts, backs));
}
}In this Python solution, sets are used similarly to efficiently mark non-candidate numbers. By using the 'zip' function, pairs of fronts and backs are iterated over, employing key conditions to manage 'same' and 'potential'. The result calculates the smallest potential good number.
Time Complexity: O(n), given n cards processed.
Space Complexity: O(n), due to set allocations.
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.
def min_good_integer(fronts, backs):
min_front = float('inf')
result = float('inf')
for f, b in zip(fronts, backs):
if f == b:
continue
if b < result:
result = b
if f < min_front:
min_front = f
return 0 if result >= min_front else result
fronts = [1, 2, 4, 4, 7]
backs = [1, 3, 4, 1, 3]
print(min_good_integer(fronts, backs))public class CardFlippingGame {
public static int minGoodInteger(int[] fronts, int[] backs) {
int minFront = Integer.MAX_VALUE;
int result = Integer.MAX_VALUE;
for (int i = 0; i < fronts.length; i++) {
if (fronts[i] == backs[i]) continue;
if (backs[i] < result) result = backs[i];
if (fronts[i] < minFront) minFront = fronts[i];
}
return (result >= minFront) ? 0 : result;
}
public static void main(String[] args) {
int[] fronts = {1, 2, 4, 4, 7};
int[] backs = {1, 3, 4, 1, 3};
System.out.println(minGoodInteger(fronts, backs));
}
}#include <iostream>
#include <vector>
#include <limits>
int minGoodInteger(std::vector<int>& fronts, std::vector<int>& backs) {
int minFront = std::numeric_limits<int>::max();
int result = std::numeric_limits<int>::max();
for (size_t i = 0; i < fronts.size(); ++i) {
if (fronts[i] == backs[i]) continue;
if (backs[i] < result) result = backs[i];
if (fronts[i] < minFront) minFront = fronts[i];
}
if (result >= minFront) result = 0;
return result;
}
int main() {
std::vector<int> fronts = {1, 2, 4, 4, 7};
std::vector<int> backs = {1, 3, 4, 1, 3};
std::cout << minGoodInteger(fronts, backs) << std::endl;
return 0;
}function minGoodInteger(fronts, backs) {
let minFront = Infinity;
let result = Infinity;
for (let i = 0; i < fronts.length; ++i) {
if (fronts[i] === backs[i]) continue;
if (backs[i] < result) result = backs[i];
if (fronts[i] < minFront) minFront = fronts[i];
}
return result >= minFront ? 0 : result;
}
let fronts = [1, 2, 4, 4, 7];
let backs = [1, 3, 4, 1, 3];
console.log(minGoodInteger(fronts, backs));#include <limits.h>
#include <stdio.h>
int minGoodInteger(int* fronts, int* backs, int n) {
int minFront = INT_MAX;
int result = INT_MAX;
for (int i = 0; i < n; i++) {
if (fronts[i] == backs[i]) continue;
if (backs[i] < result) result = backs[i];
if (fronts[i] < minFront) minFront = fronts[i];
}
if (result >= minFront) result = 0;
return result;
}
int main() {
int fronts[] = {1, 2, 4, 4, 7};
int backs[] = {1, 3, 4, 1, 3};
int n = 5;
printf("%d\n", minGoodInteger(fronts, backs, n));
return 0;
}using System;
class CardFlippingGame {
public static int MinGoodInteger(int[] fronts, int[] backs) {
int minFront = int.MaxValue;
int result = int.MaxValue;
for (int i = 0; i < fronts.Length; i++) {
if (fronts[i] == backs[i]) continue;
if (backs[i] < result) result = backs[i];
if (fronts[i] < minFront) minFront = fronts[i];
}
return (result >= minFront) ? 0 : result;
}
static void Main() {
int[] fronts = {1, 2, 4, 4, 7};
int[] backs = {1, 3, 4, 1, 3};
Console.WriteLine(MinGoodInteger(fronts, backs));
}
}In Python, this method applies 'zip' to seamlessly iterate over paired items. It assigns the current backs and selects from fronts' minimum comparative with math reduction, yielding resolved outcomes.
Time Complexity: O(n), single traversal.
Space Complexity: O(1), constant due to direct comparisons.
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.
function flipgame(fronts: number[], backs: number[]): number {
const s: Set<number> = new Set();
const n = fronts.length;
for (let i = 0; i < n; ++i) {
if (fronts[i] === backs[i]) {
s.add(fronts[i]);
}
}
let ans = 9999;
for (const v of fronts) {
if (!s.has(v)) {
ans = Math.min(ans, v);
}
}
for (const v of backs) {
if (!s.has(v)) {
ans = Math.min(ans, v);
}
}
return ans % 9999;
}func flipgame(fronts []int, backs []int) int {
s := map[int]struct{}{}
for i, a := range fronts {
if a == backs[i] {
s[a] = struct{}{}
}
}
ans := 9999
for _, v := range fronts {
if _, ok := s[v]; !ok {
ans = min(ans, v)
}
}
for _, v := range backs {
if _, ok := s[v]; !ok {
ans = min(ans, v)
}
}
return ans % 9999
}use std::collections::HashSet;
impl Solution {
pub fn flipgame(fronts: Vec<i32>, backs: Vec<i32>) -> i32 {
let n = fronts.len();
let mut s: HashSet<i32> = HashSet::new();
for i in 0..n {
if fronts[i] == backs[i] {
s.insert(fronts[i]);
}
}
let mut ans = 9999;
for &v in fronts.iter() {
if !s.contains(&v) {
ans = ans.min(v);
}
}
for &v in backs.iter() {
if !s.contains(&v) {
ans = ans.min(v);
}
}
if ans == 9999 {
0
} else {
ans
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Set-Based Approach | Time Complexity: O(n), given n cards processed. |
| Direct Comparison Approach | Time Complexity: O(n), single traversal. |
| Hash Table | – |
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. |
Frequently asked questions
Is Card Flipping Game easy or hard?
Card Flipping Game is typically rated Medium difficulty. The coding portion is simple, but the challenge is recognizing that identical front/back cards create unavoidable numbers that must be excluded before searching for the smallest valid candidate.
Card Flipping Game Python/Java solution
Most implementations follow the same structure: build a set of banned values from cards where fronts[i] == backs[i], then scan both arrays to find the minimum number not in the set. This logic translates directly into Python, Java, C++, and JavaScript with O(n) time complexity.
How to solve Card Flipping Game in O(n)?
First identify numbers where fronts[i] equals backs[i] and store them in a hash set of banned values. These numbers can never be hidden from the front. Then iterate through all numbers in both arrays and track the smallest value not present in the banned set. This produces the answer in linear time.
What is the best approach for Card Flipping Game?
The optimal solution uses a hash set to track numbers that appear on both sides of the same card. These values are impossible to hide from the front after flipping. After collecting these banned values, scan both arrays and return the smallest number not in the set. This runs in O(n) time with O(n) space.
Is Card Flipping Game asked at Google/Amazon/Meta?
Card Flipping Game represents the type of hash-set filtering and constraint reasoning commonly seen in interviews at companies like Amazon and Google. While the exact question may vary, the pattern of eliminating invalid candidates with a set is frequently tested.
What data structure is used in Card Flipping Game?
The main data structure is a hash set used to store banned values where the front and back of a card are identical. The set allows constant-time membership checks when filtering valid candidate numbers.
What is the time complexity of Card Flipping Game?
The optimal set-based approach runs in O(n) time because it scans the cards twice—once to build the banned set and once to find the smallest valid value. Hash set lookups are O(1) on average, giving linear complexity overall.