X of a Kind in a Deck of Cards - Video Solutions
X of a kind in a deck || Leetcode
X of a Kind in a Deck of Cards - Video Solution
Watch 10 video solutions for X of a Kind in a Deck of Cards, a easy level problem involving Array, Hash Table, Math. This walkthrough by Pepcoding has 4,856 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer array deck where deck[i] represents the number written on the ith card.
Partition the cards into one or more groups such that:
- Each group has exactly
xcards wherex > 1, and - All the cards in one group have the same integer written on them.
Return true if such partition is possible, or false otherwise.
Example 1:
Input: deck = [1,2,3,4,4,3,2,1] Output: true Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].
Example 2:
Input: deck = [1,1,1,2,2,2,3,3] Output: false Explanation: No possible partition.
Constraints:
1 <= deck.length <= 1040 <= deck[i] < 104
Approach Overview
Problem Overview: You receive an integer array where each value represents a card. The goal is to split the deck into groups where every group has exactly the same number of cards (X ≥ 2) and all cards inside a group have the same value. The question becomes a frequency problem: can all card counts be divided by a common group size?
Approach 1: Frequency Counting and GCD (Time: O(n), Space: O(n))
This is the most reliable solution. Start by counting how many times each card value appears using a hash table. Once you have the frequency of every card, compute the GCD (Greatest Common Divisor) across all frequencies. The key insight: if a valid group size exists, it must divide every frequency count. The largest such divisor shared across all counts is the GCD. If the final GCD is at least 2, the deck can be partitioned into groups of that size. If the GCD becomes 1, at least one frequency breaks the grouping constraint and partitioning is impossible.
This method works because any valid group size must be a common divisor of every frequency. Using the GCD compresses the check into a single number instead of testing many candidates. The algorithm performs a single pass to count frequencies and then iterates through the counts to compute the GCD. This makes it linear time and efficient even for large decks.
Approach 2: Counting Elements and Checking Lowest Frequency (Time: O(n + k), Space: O(n))
Another way to reason about the problem is to first count the occurrences of each card using a counting approach. Then find the smallest frequency among all card values. That minimum count limits the maximum possible group size. Iterate through candidate group sizes from 2 up to the minimum frequency and check whether every frequency is divisible by the candidate size.
This approach is conceptually simple and directly mirrors the problem statement: test whether a group size divides every frequency. However, it may perform extra checks when the minimum frequency is large, since multiple candidate sizes are tested. In practice it still runs fast for typical constraints, but it is less elegant than the mathematical GCD reduction.
The core ideas rely on array traversal, frequency maps, and basic number theory. Recognizing that grouping constraints translate into a common divisor problem is the main trick.
Recommended for interviews: Frequency Counting with GCD. It converts the grouping requirement into a single mathematical check and runs in O(n) time. Interviewers expect candidates to notice that all frequencies must share a common divisor ≥ 2. Implementing the GCD reduction demonstrates stronger algorithmic reasoning than brute checking every possible group size.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Counting and GCD | O(n) | O(n) | Best general solution; converts grouping constraint into a single GCD check |
| Counting Elements and Checking Lowest Frequency | O(n + k) | O(n) | Useful for understanding the grouping logic by testing candidate group sizes |