Card Flipping Game

medium array hash-set

Problem

Each card has a front number and a back number. After flipping any subset of cards, a number x is 'good' if it appears on the back of some card but not on the front of any card. Return the minimum good number, or 0 if none.

Inputfronts = [1,2,4,4,7], backs = [1,3,4,1,3]

Output2

Card 0 has fronts[0]=backs[0]=1 so 1 can never be good. The smallest other number not on a same-card pair is 2.

input

def flipgame(fronts, backs):
    same = {f for f, b in zip(fronts, backs) if f == b}
    best = float('inf')
    for x in fronts + backs:
        if x not in same:
            best = min(best, x)
    return 0 if best == float('inf') else best

function flipgame(fronts, backs) {
  const same = new Set();
  for (let i = 0; i < fronts.length; i++)
    if (fronts[i] === backs[i]) same.add(fronts[i]);
  let best = Infinity;
  for (const x of fronts) if (!same.has(x)) best = Math.min(best, x);
  for (const x of backs)  if (!same.has(x)) best = Math.min(best, x);
  return best === Infinity ? 0 : best;
}

import java.util.*;
class Solution {
  public int flipgame(int[] fronts, int[] backs) {
    Set<Integer> same = new HashSet<>();
    for (int i = 0; i < fronts.length; i++)
      if (fronts[i] == backs[i]) same.add(fronts[i]);
    int best = Integer.MAX_VALUE;
    for (int x : fronts) if (!same.contains(x)) best = Math.min(best, x);
    for (int x : backs)  if (!same.contains(x)) best = Math.min(best, x);
    return best == Integer.MAX_VALUE ? 0 : best;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int flipgame(vector<int>& fronts, vector<int>& backs) {
        unordered_set<int> same;
        for (int i = 0; i < (int)fronts.size(); i++)
            if (fronts[i] == backs[i]) same.insert(fronts[i]);
        int best = INT_MAX;
        for (int x : fronts) if (!same.count(x)) best = min(best, x);
        for (int x : backs)  if (!same.count(x)) best = min(best, x);
        return best == INT_MAX ? 0 : best;
    }
};

Explanation

The key insight is figuring out which numbers can never be good. If a card has the same number on both sides (fronts[i] == backs[i]), that number is stuck — no matter how you flip, it will always show on some front. So it can never qualify.

First we collect all those "stuck" numbers into a hash set called same. Any value in same is disqualified for good.

Then every other number that appears anywhere (on a front or a back) can be made good — you can always flip cards so that it shows only on backs. So we just scan all the numbers in fronts and backs, skip the ones in same, and keep the smallest survivor.

Example: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]. Card 0 has 1 on both sides, so same = {1}. Scanning the rest, the smallest number not in same is 2, so the answer is 2.

If every number turned out to be stuck, we return 0. The set gives instant lookups, so this is a quick linear scan.

Time: O(n) Space: O(n)