LeetCode 914 - X of a Kind in a Deck of Cards

The problem asks whether it is possible to partition a deck of cards, represented as an integer array deck, into groups such that each group contains exactly x cards, all of which have the same integer value, and x is greater than 1.

leetcodeeasyarrayhash-tablemathcountingnumber-theory

LeetCode Problem 914

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Counting, Number Theory

Solution

Problem Understanding

The problem asks whether it is possible to partition a deck of cards, represented as an integer array deck, into groups such that each group contains exactly x cards, all of which have the same integer value, and x is greater than 1. Essentially, we need to find a number x that evenly divides the count of each distinct card in the deck. If such an x exists, we return true; otherwise, we return false.

The input deck is a list of integers, each representing a card's value. The output is a boolean indicating whether a valid partition exists. Constraints tell us that the deck can be up to 10,000 cards, and values range from 0 to 10,000, which means solutions must scale linearly or near-linearly in practice. Edge cases include decks with all cards identical, decks where counts are prime numbers, or decks with only one card, which cannot form a valid group (x > 1).

Important edge cases to consider include a single unique card repeated many times, multiple unique cards with counts that do not share a common factor greater than one, and decks with only one card, which cannot be partitioned.

Approaches

The brute-force approach involves checking all possible group sizes starting from 2 up to the size of the deck. For each potential group size, we check whether it divides the count of each card in the deck. If we find a group size that works for all counts, we return true; otherwise, we return false. While this is correct, it is inefficient because we may check many unnecessary group sizes, especially for large decks, leading to poor performance.

The optimal approach uses a key insight from number theory. Instead of checking every potential group size, we can calculate the greatest common divisor (GCD) of all card counts. If the GCD is greater than 1, it means there exists a number x that divides all counts, satisfying the problem's requirement. This approach leverages the mathematical property that any common divisor of all counts must divide their GCD, making it both elegant and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(N * K) O(N) N = length of deck, K = range of possible group sizes (up to max count)
Optimal O(N) O(N) Count occurrences with a hash map, compute GCD of all counts

Algorithm Walkthrough

  1. First, count the occurrences of each distinct card in the deck using a hash map or dictionary. This step allows us to know exactly how many of each card exist.
  2. Extract all the counts from the dictionary into a list for further processing.
  3. Compute the GCD of all the counts. Start with the first count as the initial GCD and iteratively compute the GCD with each subsequent count. This ensures that the final GCD is the largest number that evenly divides all counts.
  4. Check if the final GCD is greater than 1. If it is, return true, as it is possible to partition the deck into groups of size equal to the GCD. Otherwise, return false.

Why it works: The GCD represents the largest number that divides all card counts. If this number is greater than 1, it is guaranteed that each card count can be split into groups of this size, meeting the problem requirements. If the GCD is 1, no such grouping is possible.

Python Solution

from collections import Counter
from math import gcd
from functools import reduce
from typing import List

class Solution:
    def hasGroupsSizeX(self, deck: List[int]) -> bool:
        if not deck:
            return False
        
        count = Counter(deck)
        counts = list(count.values())
        
        deck_gcd = reduce(gcd, counts)
        
        return deck_gcd > 1

In this implementation, Counter counts the occurrences of each card efficiently. The reduce function iteratively computes the GCD of all counts. We check if the GCD is greater than 1 to decide if a valid partition exists.

Go Solution

package main

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

func hasGroupsSizeX(deck []int) bool {
    if len(deck) == 0 {
        return false
    }
    
    countMap := make(map[int]int)
    for _, card := range deck {
        countMap[card]++
    }
    
    var deckGCD int
    first := true
    for _, c := range countMap {
        if first {
            deckGCD = c
            first = false
        } else {
            deckGCD = gcd(deckGCD, c)
        }
    }
    
    return deckGCD > 1
}

In Go, we implement a gcd function manually because the standard library does not provide one for integers. We use a map to count occurrences and iteratively compute the GCD.

Worked Examples

Example 1: deck = [1,2,3,4,4,3,2,1]

Counting card occurrences:

Card Count
1 2
2 2
3 2
4 2

GCD of counts: gcd(2, 2, 2, 2) = 2

Since 2 > 1, return true.

Example 2: deck = [1,1,1,2,2,2,3,3]

Counting card occurrences:

Card Count
1 3
2 3
3 2

GCD of counts: gcd(3, 3, 2) = 1

Since 1 ≤ 1, return false.

Complexity Analysis

Measure Complexity Explanation
Time O(N) Counting occurrences takes O(N) and computing GCD of at most N counts is O(N)
Space O(N) Storing the counts in a hash map requires O(N) space in the worst case

The time complexity is linear because each card is processed once for counting and each count participates in the GCD computation. Space complexity is linear due to storing counts in a dictionary.

Test Cases

# Basic examples
assert Solution().hasGroupsSizeX([1,2,3,4,4,3,2,1]) == True  # standard partition
assert Solution().hasGroupsSizeX([1,1,1,2,2,2,3,3]) == False  # no common divisor > 1

# Edge cases
assert Solution().hasGroupsSizeX([1]) == False  # single card
assert Solution().hasGroupsSizeX([2,2]) == True  # two identical cards
assert Solution().hasGroupsSizeX([1,1,2,2,2,2]) == True  # counts 2, 4 => GCD = 2
assert Solution().hasGroupsSizeX([1,1,1,1,2,2,2,2,2,2]) == True  # counts 4, 6 => GCD = 2
assert Solution().hasGroupsSizeX([1,2,3,4]) == False  # counts all 1 => cannot partition
Test Why
[1,2,3,4,4,3,2,1] Valid standard grouping with equal counts
[1,1,1,2,2,2,3,3] Counts do not share a GCD > 1
[1] Single card cannot form group of size >1
[2,2] Minimal valid grouping
[1,1,2,2,2,2] Counts have common divisor 2
[1,1,1,1,2,2,2,2,2,2] Counts 4 and 6 share GCD 2
[1,2,3,4] All counts 1, cannot partition

Edge Cases

A key edge case is a deck with a single card. Since a valid group requires more than one card, the solution correctly returns false without attempting GCD computation.

Another edge case involves counts that are prime numbers. For example, [1,1,1,2,2,2,3,3,3] results in counts [3,3,3] with GCD 3, so it returns true. This highlights that prime counts can still be valid if they are equal.

A third edge case occurs when counts vary and share no common divisor greater than one. For instance, [1,1,2,2,2,3,3,3,3] has counts [2,3,4] with GCD 1. The solution must return false as no group size >1 divides all counts. This case demonstrates the importance of using the GCD rather than trying arbitrary group sizes.