Card Flipping Game
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible combination of card flips. Since each of the n cards can either be in its original state or flipped, there are 2^n total configurations. For each configuration, we determine the set of numbers facing up and the set of numbers facing down. We then find the minimum number that is in the "down" set but not in the "up" set. The overall minimum across all 2^n configurations is the answer.
Algorithm
- Initialize
min_goodto a very large value. - Loop through all integers
maskfrom0to2^n - 1.- Create an empty set
up_numbersanddown_numbers. - For each card
jfrom0ton-1:- If the
j-th bit ofmaskis set, it means flip cardj. Addbacks[j]toup_numbersandfronts[j]todown_numbers. - Otherwise, do not flip. Add
fronts[j]toup_numbersandbacks[j]todown_numbers.
- If the
- Initialize
current_min_goodto a very large value. - For each
numindown_numbers:- If
numis not inup_numbers, updatecurrent_min_good = min(current_min_good, num).
- If
- Update
min_good = min(min_good, current_min_good).
- Create an empty set
- If
min_goodis still the large initial value, return 0. Otherwise, returnmin_good.
Walkthrough
We use a bitmask, an integer from 0 to 2^n - 1, to represent a specific configuration of flips. If the j-th bit is 0, card j is not flipped. If it's 1, card j is flipped. The algorithm iterates through all 2^n masks. For each mask, it constructs two sets: up_numbers and down_numbers. It iterates through each card j from 0 to n-1. Based on the j-th bit of the mask, it adds the appropriate fronts[j] or backs[j] to the up_numbers and down_numbers sets. After building the sets for a configuration, it finds the minimum "good" number for that specific configuration by iterating through all numbers in down_numbers and checking if they are absent from up_numbers. A global minimum is maintained and updated after processing each of the 2^n configurations. If no good number is ever found, we return 0.
import java.util.HashSet;import java.util.Set; class Solution { public int flipgame(int[] fronts, int[] backs) { int n = fronts.length; int minGood = Integer.MAX_VALUE; for (int i = 0; i < (1 << n); i++) { // Iterate through all 2^n flip combinations Set<Integer> upNumbers = new HashSet<>(); Set<Integer> downNumbers = new HashSet<>(); for (int j = 0; j < n; j++) { if ((i >> j & 1) == 1) { // Card j is flipped upNumbers.add(backs[j]); downNumbers.add(fronts[j]); } else { // Card j is not flipped upNumbers.add(fronts[j]); downNumbers.add(backs[j]); } } int currentMinGood = Integer.MAX_VALUE; for (int num : downNumbers) { if (!upNumbers.contains(num)) { currentMinGood = Math.min(currentMinGood, num); } } minGood = Math.min(minGood, currentMinGood); } return minGood == Integer.MAX_VALUE ? 0 : minGood; }}Complexity
Time
O(2^n * n). There are `2^n` configurations. For each, we iterate through `n` cards to build the sets (O(n)) and then iterate through the down-facing numbers (at most `n`) to find the minimum good number (O(n)). Thus, the total time is O(2^n * n).
Space
O(n). The sets `up_numbers` and `down_numbers` can store up to `n` elements each.
Trade-offs
Pros
Conceptually simple, as it directly models the problem statement by trying all possibilities.
Cons
Extremely inefficient. The exponential time complexity makes it infeasible for the given constraints (
nup to 1000). It will result in a "Time Limit Exceeded" error.
Instead of iterating through all possible flip configurations, we can iterate through all possible numbers that could be the answer. The candidates for a good number must be numbers that appear on the cards. We can collect all unique numbers from both fronts and backs arrays and test each one to see if it can be a "good" number.
Algorithm
- Create a
Setcalledcandidatesand populate it with all unique numbers fromfrontsandbacks. - Initialize
min_goodto a very large value. - For each
candidatein thecandidatesset:- Assume it's possible to make
candidatea good number (is_possible = true). - Iterate through each card
ifrom0ton-1.- If
fronts[i] == candidateandbacks[i] == candidate, it's impossible. Setis_possible = falseand break the inner loop.
- If
- If
is_possibleremainstrue, it meanscandidatecan be a good number. Updatemin_good = min(min_good, candidate).
- Assume it's possible to make
- If
min_goodis still the large initial value, return 0. Otherwise, returnmin_good.
Walkthrough
A number x can be a good number if and only if we can arrange the cards such that x is never facing up. This is impossible only if there is a card that has x on both its front and back. If fronts[i] == backs[i] == x, then card i will always have x facing up, regardless of flips. The algorithm first gathers all unique numbers from fronts and backs into a candidate set. Then, for each candidate number c, it checks if there exists any card i where fronts[i] == backs[i] == c. If no such card exists for c, it means c can be made a good number. We can always flip any card showing c on its front to hide it on the back. Since c is a candidate, it's present on at least one card, so it can be made to face down. We keep track of the minimum candidate that satisfies this condition.
import java.util.HashSet;import java.util.Set; class Solution { public int flipgame(int[] fronts, int[] backs) { Set<Integer> candidates = new HashSet<>(); for (int num : fronts) { candidates.add(num); } for (int num : backs) { candidates.add(num); } int minGood = Integer.MAX_VALUE; for (int candidate : candidates) { boolean isPossible = true; for (int i = 0; i < fronts.length; i++) { if (fronts[i] == candidate && backs[i] == candidate) { isPossible = false; break; } } if (isPossible) { minGood = Math.min(minGood, candidate); } } return minGood == Integer.MAX_VALUE ? 0 : minGood; }}Complexity
Time
O(U * n), where `U` is the number of unique values on the cards and `n` is the number of cards. In the worst case, `U` can be `2n`, leading to O(n^2). This is acceptable for the given constraints.
Space
O(U) or O(n), where U is the number of unique values on the cards. This is for storing the `candidates` set.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Solves the problem within typical time limits.
Cons
Not the most optimal solution as it involves a nested loop structure. The logic can be streamlined.
This is the most efficient approach. The key insight is that a number can be a "good" number if and only if it does not appear on both sides of the same card. If a number x is on both the front and back of a card, it's impossible to hide it, so it can never be good. We can first identify all such "invalid" numbers. Then, the answer is simply the minimum number among all card faces that is not in our set of invalid numbers.
Algorithm
- Create an empty
HashSetcalledinvalid. - Iterate through the cards from
i = 0ton-1. Iffronts[i] == backs[i], addfronts[i]to theinvalidset. - Initialize
min_goodto a very large value (e.g.,Integer.MAX_VALUE). - Iterate through the
frontsarray. For eachnum, ifnumis not ininvalid, updatemin_good = min(min_good, num). - Iterate through the
backsarray. For eachnum, ifnumis not ininvalid, updatemin_good = min(min_good, num). - If
min_goodremains at its initial large value, return 0. Otherwise, returnmin_good.
Walkthrough
The algorithm works in two main steps. First, it identifies all numbers that are impossible to make "good". It iterates through all the cards once. If for any card i, fronts[i] == backs[i], the number fronts[i] is added to a HashSet of invalid numbers. Second, it finds the minimum possible good number. It iterates through all numbers in both the fronts and backs arrays. For each number, it checks if it is present in the invalid set. If it's not, it's a valid candidate for a good number. The algorithm keeps track of the minimum such valid candidate found. If after checking all numbers, no valid candidate was found, it means no good number exists, and we return 0. Otherwise, we return the minimum found.
import java.util.HashSet;import java.util.Set; class Solution { public int flipgame(int[] fronts, int[] backs) { Set<Integer> invalid = new HashSet<>(); for (int i = 0; i < fronts.length; i++) { if (fronts[i] == backs[i]) { invalid.add(fronts[i]); } } int minGood = Integer.MAX_VALUE; for (int num : fronts) { if (!invalid.contains(num)) { minGood = Math.min(minGood, num); } } for (int num : backs) { if (!invalid.contains(num)) { minGood = Math.min(minGood, num); } } return minGood == Integer.MAX_VALUE ? 0 : minGood; }}Complexity
Time
O(n). The first pass to populate the `invalid` set takes O(n). The next two passes to check all numbers in `fronts` and `backs` also take O(n). Set operations (add, contains) take O(1) on average. The total time is linear.
Space
O(k), where `k` is the number of cards with the same number on both sides. In the worst case, `k` can be up to `n`, so the space complexity is O(n).
Trade-offs
Pros
Optimal time complexity. It solves the problem in a single effective pass over the data.
Simple and elegant logic.
Cons
Requires extra space for the
HashSet, although this is necessary for the time efficiency.
Solutions
Solution
public class Solution { public int Flipgame(int[] fronts, int[] backs) { var s = new HashSet < int > (); int n = fronts.Length; for (int i = 0; i < n; ++i) { if (fronts[i] == backs[i]) { s.Add(fronts[i]); } } int ans = 9999; for (int i = 0; i < n; ++i) { if (!s.Contains(fronts[i])) { ans = Math.Min(ans, fronts[i]); } if (!s.Contains(backs[i])) { ans = Math.Min(ans, backs[i]); } } return ans % 9999; }}class Solution {public int flipgame(int[] fronts, int[] backs) { Set<Integer> s = new HashSet<>(); int n = fronts.length; for (int i = 0; i < n; ++i) { if (fronts[i] == backs[i]) { s.add(fronts[i]); } } int ans = 9999; for (int v : fronts) { if (!s.contains(v)) { ans = Math.min(ans, v); } } for (int v : backs) { if (!s.contains(v)) { ans = Math.min(ans, v); } } return ans % 9999; }}class Solution {public: int flipgame(vector<int> &fronts, vector<int> &backs) { unordered_set<int> s; int n = fronts.size(); for (int i = 0; i < n; ++i) { if (fronts[i] == backs[i]) { s.insert(fronts[i]); } } int ans = 9999; for (int &v : fronts) { if (!s.count(v)) { ans = min(ans, v); } } for (int &v : backs) { if (!s.count(v)) { ans = min(ans, v); } } return ans % 9999; }};class Solution: def flipgame(self, fronts: List[int], backs: List[int]) -> int: s = {a for a, b in zip(fronts, backs) if a == b} return min((x for x in chain(fronts, backs) if x not in s), default=0)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.