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] < 104The key idea in #914 X of a Kind in a Deck of Cards is to determine whether the deck can be divided into groups of equal size where every group contains cards of the same value. Start by counting the frequency of each card using a hash table. This transforms the problem into checking whether all card frequencies share a common group size.
Once the frequencies are known, the challenge becomes a number theory problem. If there exists an integer X ≥ 2 that divides all frequencies, then the deck can be partitioned accordingly. A practical way to verify this is by computing the greatest common divisor (GCD) of all frequency counts. If the final GCD is at least 2, a valid grouping exists.
This approach leverages efficient counting and mathematical reasoning. The algorithm runs in linear time relative to the number of cards while using extra space for frequency storage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Counting + GCD of Frequencies | O(n) | O(n) |
Fireship
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.
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.
1function gcd(a, b) {
2 while (b !== 0) {
3 const temp = b;
4 b = a % b;
This JavaScript solution uses an object to track the frequency of each card. It computes the GCD of the frequencies and verifies that it's greater than 1 to confirm valid group size.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
GCD helps identify whether all card frequencies share a common divisor greater than 1. If such a divisor exists, it means the cards can be split into groups of equal size with identical values in each group.
Yes, variations of counting and grouping problems like this appear in coding interviews at major tech companies. The question tests understanding of hash maps, frequency counting, and applying number theory concepts such as GCD.
A hash table (or dictionary) is the best data structure because it allows quick counting of how many times each card appears. Once the frequencies are stored, mathematical operations like computing the GCD can determine whether a valid group size exists.
The optimal approach counts the frequency of each card using a hash map and then computes the greatest common divisor (GCD) of those counts. If the GCD of all frequencies is at least 2, the deck can be partitioned into equal groups. This method runs in linear time and efficiently verifies the grouping condition.
The Python code computes card frequencies with the Counter class, then tries potential group sizes iteratively. Success denotes a successful partition, returning true.