algoadvance

Leetcode 822. Card Flipping Game

Problem Statement:

LeetCode Problem 822: Card Flipping Game

On a table, you have cards with the integers fronts and backs written on them. A card (i) has two numbers written on it: fronts[i] on the front and backs[i] on the back. We can flip the card so that the number backs[i] becomes the new front.

You need to choose a card that you can flip such that after one or no flips, the number on the front is not the same as the number on the back.

Return the minimum possible number you can pick to do so. If there is no possible number, return 0.

Clarifying Questions:

  1. Are the numbers on the cards all non-negative integers?
    • Yes, assume all integers are non-negative.
  2. Can the cards be empty?
    • No, you will at least have one card.

Strategy:

  1. Identify numbers that are the same on both sides of any card (both sides of these cards have restricted values that cannot be valid).
  2. Traverse all numbers in fronts and backs arrays to find the minimum number that is not in the set of restricted values.

Code:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

int flipgame(std::vector<int>& fronts, std::vector<int>& backs) {
    std::unordered_set<int> restricted; // Numbers that are same on both sides of any card
    for (size_t i = 0; i < fronts.size(); ++i) {
        if (fronts[i] == backs[i]) {
            restricted.insert(fronts[i]);
        }
    }
    
    int min_valid = INT_MAX;
    // Check all numbers for potential valid minimum
    for (size_t i = 0; i < fronts.size(); ++i) {
        if (restricted.find(fronts[i]) == restricted.end()) {
            min_valid = std::min(min_valid, fronts[i]);
        }
        if (restricted.find(backs[i]) == restricted.end()) {
            min_valid = std::min(min_valid, backs[i]);
        }
    }
    return (min_valid == INT_MAX) ? 0 : min_valid;
}

int main() {
    std::vector<int> fronts = {1, 2, 4, 4, 7};
    std::vector<int> backs = {1, 3, 4, 1, 3};
    std::cout << "Minimum number you can pick: " << flipgame(fronts, backs) << std::endl;
    return 0;
}

Time Complexity:

The time complexity of this solution is (O(n)), where (n) is the number of cards. The algorithm involves two primary loops:

  1. The first loop collects restricted numbers, which takes (O(n)) time.
  2. The second loop checks the minimum number that’s not restricted, which also takes (O(n)) time.

Thus, the overall complexity is (O(n)).

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