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:
x cards where x > 1, andReturn 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] < 104Problem 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.
This approach involves counting the frequency of each card number. Once we have the frequencies, the problem reduces to checking if there exists a number x greater than 1 that divides all these frequencies. This is efficiently achieved by calculating the GCD of the list of frequencies.
This C solution first counts the frequency of each number in the deck using an array. It then calculates the GCD of these frequencies. If the GCD is greater than 1, it returns true, otherwise false.
Time Complexity: O(n + m log m), where n is the length of the deck and m is the number of unique numbers.
Space Complexity: O(m), where m is the number of unique numbers due to the frequency array.
This approach also involves counting the frequency of each card in the deck. However, rather than immediately calculating the GCD, it sorts the frequency list and iteratively checks for the smallest divisor of these frequencies greater than 1.
This solution starts by counting frequencies and finding the smallest non-zero frequency. It attempts to divide all frequencies by each integer from 2 to `min_freq`. If successful, it returns true; otherwise, returns false.
Time Complexity: O(n + m√n), where n is the number of cards and m is the number of unique cards.
Space Complexity: O(m) for the frequency array.
First, we use an array or hash table cnt to count the occurrence of each number. Only when X is a divisor of the greatest common divisor of all cnt[i], can it satisfy the problem's requirement.
Therefore, we find the greatest common divisor g of the occurrence of all numbers, and then check whether it is greater than or equal to 2.
The time complexity is O(n times log M), and the space complexity is O(n + log M). Where n and M are the length of the array deck and the maximum value in the array deck, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Counting and GCD | Time Complexity: O(n + m log m), where n is the length of the deck and m is the number of unique numbers. |
| Approach 2: Counting Elements and Checking Lowest Frequency | Time Complexity: O(n + m√n), where n is the number of cards and m is the number of unique cards. |
| Greatest Common Divisor | — |
| 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 |
LeetCode 914. X of a Kind in a Deck of Cards • Happy Coding • 3,553 views views
Watch 9 more video solutions →Practice X of a Kind in a Deck of Cards with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor