algoadvance

Leetcode 822. Card Flipping Game

Problem Statement

You are given two arrays of integers fronts and backs of the same length. You can choose any card i (0-indexed) and flip it, so that the back of the card becomes the front and vice versa. You need to find the smallest possible number X assigned to the front of a card that isn’t at the back of any card after flipping. If no such number exists, return 0.

Here’s the problem link: Card Flipping Game

Clarifying Questions

  1. Can fronts and backs have different lengths?
    • No, fronts and backs always have the same length as per the problem statement.
  2. Can elements in fronts and backs be negative or zero?
    • As per the problem description and usual constraint, the card numbers are positive integers.
  3. Are there any constraints on the values of the integers in fronts and backs?
    • Typically, the values are within a reasonable range appropriate for a card-flipping game, such as 1 to 2000 or so.

Strategy

The main idea is to identify numbers that appear on both the front and back of the same card because these numbers cannot be the answer as flipping the card doesn’t avoid them.

  1. Identify invalid numbers:
    • These are the numbers which are both in the front and back side of the same card.
  2. Find the minimum valid number:
    • Consider all numbers that are not among the invalid numbers and find the minimum.

Code

Here’s the Java code to solve the problem:

import java.util.HashSet;
import java.util.Set;

public class CardFlippingGame {
    public int flipgame(int[] fronts, int[] backs) {
        Set<Integer> invalidNumbers = new HashSet<>();
        
        // Identify invalid numbers which are the same in front and back of a card.
        for (int i = 0; i < fronts.length; i++) {
            if (fronts[i] == backs[i]) {
                invalidNumbers.add(fronts[i]);
            }
        }

        int minimumNumber = Integer.MAX_VALUE;
        for (int i = 0; i < fronts.length; i++) {
            if (!invalidNumbers.contains(fronts[i])) {
                minimumNumber = Math.min(minimumNumber, fronts[i]);
            }
            if (!invalidNumbers.contains(backs[i])) {
                minimumNumber = Math.min(minimumNumber, backs[i]);
            }
        }

        // If no valid number found, return 0
        return minimumNumber == Integer.MAX_VALUE ? 0 : minimumNumber;
    }

    public static void main(String[] args) {
        CardFlippingGame cfg = new CardFlippingGame();
        int[] fronts = {1, 2, 4, 4, 7};
        int[] backs = {1, 3, 4, 1, 3};
        System.out.println(cfg.flipgame(fronts, backs)); // Output should be 2
    }
}

Time Complexity

Overall, the time complexity is O(n).

This solution also uses O(n) extra space for storing invalid numbers in a HashSet.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI