X of a Kind in a Deck of Cards solution and explanation
Google
9 more videos on this problem
LeetCode 914. X of a Kind in a Deck of CardsHappy Coding · 15:48 · 3K views
914. X of a Kind in a Deck of Cards (Leetcode Easy)Programming Live with Larry · 7:50 · 919 views
914. X of a Kind in a Deck of Cards (LeetCode)hakunamatasq · 3:55 · 839 views
X OF A KIND IN A DECK OF CARD | LEETCODE 914 | SOMENDRA TIWARISomendra Tiwari · 11:25 · 801 views
X of a Kind in a Deck of Cards | Programming Questions [ for Service Company] | PART 31Knowledge Amplifier · 3:40 · 556 views
L10. X of a Kind in a Deck of Cards | Leetcode | HashMap | C++ | Java | #90dayschallenge | #day10Jasmeen Kaur · 17:39 · 554 views
LeetCode 914 | X of a Kind in a Deck of Cards | HashMap | JavaSleepy Cracker · 5:09 · 529 views
Leetcode solving: 914. X of a Kind in a Deck of CardsMath Geeks · 2:57 · 312 views
Leetcode 914: X of a Kind in a Deck of Cards in Telugu | Bruteforce, GCD | Python DSA | srkcodesSrk Codes · 11:35 · 148 views
X of a kind in a deck || LeetcodePepcoding · 13:44 · 4K views
The problem
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.
Approach 1: Approach 1: Frequency Counting and GCD
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.
from collections import Counter
from math import gcd
from functools import reduce
def hasGroupsSizeX(deck):
def GCD(arr):
return reduce(gcd, arr)
count = Counter(deck)
return GCD(count.values()) > 1
if __name__ == "__main__":
deck = [1,2,3,4,4,3,2,1]
print(hasGroupsSizeX(deck))import java.util.HashMap;
public class Solution {
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public boolean hasGroupsSizeX(int[] deck) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : deck) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int X = 0;
for (int count : freq.values()) {
X = gcd(X, count);
}
return X > 1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] deck = {1,2,3,4,4,3,2,1};
System.out.println(sol.hasGroupsSizeX(deck) ? "true" : "false");
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
bool hasGroupsSizeX(std::vector<int>& deck) {
std::unordered_map<int, int> freq;
for (int num : deck) {
freq[num]++;
}
int X = 0;
for (auto entry : freq) {
X = gcd(X, entry.second);
}
return X > 1;
}
int main() {
std::vector<int> deck = {1,2,3,4,4,3,2,1};
std::cout << (hasGroupsSizeX(deck) ? "true" : "false") << std::endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
const temp = b;
b = a % b;
a = temp;
}
return a;
}
function hasGroupsSizeX(deck) {
const freq = {};
for (const card of deck) {
if (!freq[card]) freq[card] = 0;
freq[card]++;
}
const values = Object.values(freq);
let X = values[0];
for (const count of values) {
X = gcd(X, count);
}
return X > 1;
}
console.log(hasGroupsSizeX([1,2,3,4,4,3,2,1]));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
bool hasGroupsSizeX(int* deck, int deckSize) {
int freq[10000] = {0};
for (int i = 0; i < deckSize; i++) {
freq[deck[i]]++;
}
int X = 0;
for (int i = 0; i < 10000; i++) {
if (freq[i] > 0) {
if (X == 0) {
X = freq[i];
} else {
X = gcd(X, freq[i]);
}
}
}
return X > 1;
}
int main() {
int deck[] = {1,2,3,4,4,3,2,1};
int deckSize = sizeof(deck)/sizeof(deck[0]);
printf("%s\n", hasGroupsSizeX(deck, deckSize) ? "true" : "false");
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public bool HasGroupsSizeX(int[] deck) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int num in deck) {
if (!freq.ContainsKey(num)) freq[num] = 0;
freq[num]++;
}
int X = 0;
foreach (int count in freq.Values) {
X = GCD(X, count);
}
return X > 1;
}
public static void Main() {
Solution sol = new Solution();
int[] deck = {1,2,3,4,4,3,2,1};
Console.WriteLine(sol.HasGroupsSizeX(deck) ? "true" : "false");
}
}This Python solution uses the `Counter` to tally frequencies quickly. It uses the math and functools libraries to calculate the GCD of all frequency counts to determine if a valid grouping is possible.
Time Complexity: O(n log n) with efficient GCD computation.
Space Complexity: O(n) for storing the frequency count of deck elements.
Approach 2: Approach 2: Counting Elements and Checking Lowest Frequency
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.
from collections import Counter
def hasGroupsSizeX(deck):
count = Counter(deck)
min_freq = min(count.values())
for x in range(2, min_freq + 1):
if all(freq % x == 0 for freq in count.values()):
return True
return False
if __name__ == "__main__":
deck = [1,1,1,2,2,2,3,3]
print(hasGroupsSizeX(deck))import java.util.HashMap;
public class Solution {
public boolean hasGroupsSizeX(int[] deck) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : deck) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int min_freq = Integer.MAX_VALUE;
for (int count : freq.values()) {
if (count < min_freq) {
min_freq = count;
}
}
for (int x = 2; x <= min_freq; x++) {
boolean canDivide = true;
for (int count : freq.values()) {
if (count % x != 0) {
canDivide = false;
break;
}
}
if (canDivide) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] deck = {1,1,1,2,2,2,3,3};
System.out.println(sol.hasGroupsSizeX(deck) ? "true" : "false");
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
bool hasGroupsSizeX(std::vector<int>& deck) {
std::unordered_map<int, int> freq;
for (int num : deck) {
freq[num]++;
}
int min_freq = INT_MAX;
for (auto& entry : freq) {
if (entry.second < min_freq) {
min_freq = entry.second;
}
}
for (int x = 2; x <= min_freq; x++) {
bool canDivide = true;
for (auto& entry : freq) {
if (entry.second % x != 0) {
canDivide = false;
break;
}
}
if (canDivide) {
return true;
}
}
return false;
}
int main() {
std::vector<int> deck = {1,1,1,2,2,2,3,3};
std::cout << (hasGroupsSizeX(deck) ? "true" : "false") << std::endl;
return 0;
}function hasGroupsSizeX(deck) {
const freq = {};
for (const card of deck) {
if (!freq[card]) freq[card] = 0;
freq[card]++;
}
const values = Object.values(freq);
const minFreq = Math.min(...values);
outer:
for (let x = 2; x <= minFreq; x++) {
for (const count of values) {
if (count % x !== 0) {
continue outer;
}
}
return true;
}
return false;
}
console.log(hasGroupsSizeX([1,1,1,2,2,2,3,3]));#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool hasGroupsSizeX(int* deck, int deckSize) {
int freq[10000] = {0};
for (int i = 0; i < deckSize; i++) {
freq[deck[i]]++;
}
int min_freq = 10000;
for (int i = 0; i < 10000; i++) {
if (freq[i] > 0 && freq[i] < min_freq) {
min_freq = freq[i];
}
}
for (int x = 2; x <= min_freq; x++) {
bool canDivide = true;
for (int i = 0; i < 10000; i++) {
if (freq[i] > 0 && freq[i] % x != 0) {
canDivide = false;
break;
}
}
if (canDivide) {
return true;
}
}
return false;
}
int main() {
int deck[] = {1,1,1,2,2,2,3,3};
int deckSize = sizeof(deck)/sizeof(deck[0]);
printf("%s\n", hasGroupsSizeX(deck, deckSize) ? "true" : "false");
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public bool HasGroupsSizeX(int[] deck) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int num in deck) {
if (!freq.ContainsKey(num)) freq[num] = 0;
freq[num]++;
}
int min_freq = int.MaxValue;
foreach (int count in freq.Values) {
if (count < min_freq) {
min_freq = count;
}
}
for (int x = 2; x <= min_freq; x++) {
bool canDivide = true;
foreach (int count in freq.Values) {
if (count % x != 0) {
canDivide = false;
break;
}
}
if (canDivide) {
return true;
}
}
return false;
}
public static void Main() {
Solution sol = new Solution();
int[] deck = {1,1,1,2,2,2,3,3};
Console.WriteLine(sol.HasGroupsSizeX(deck) ? "true" : "false");
}
}The Python code computes card frequencies with the Counter class, then tries potential group sizes iteratively. Success denotes a successful partition, returning true.
Time Complexity: O(n + m√n), accounting for counting and checking divisibility.
Space Complexity: O(n), due to storage in Counter.
Approach 3: Greatest Common Divisor
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.
function hasGroupsSizeX(deck: number[]): boolean {
const cnt: Record<number, number> = {};
for (const x of deck) {
cnt[x] = (cnt[x] || 0) + 1;
}
const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
let g = cnt[deck[0]];
for (const [_, x] of Object.entries(cnt)) {
g = gcd(g, x);
}
return g >= 2;
}func hasGroupsSizeX(deck []int) bool {
cnt := map[int]int{}
for _, x := range deck {
cnt[x]++
}
g := cnt[deck[0]]
for _, x := range cnt {
g = gcd(g, x)
}
return g >= 2
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Frequency Counting and GCD | Time Complexity: O(n log n) with efficient GCD computation. |
| Approach 2: Counting Elements and Checking Lowest Frequency | Time Complexity: O(n + m√n), accounting for counting and checking divisibility. |
| Greatest Common Divisor | – |
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 |
Frequently asked questions
Is X of a Kind in a Deck of Cards easy or hard?
The problem is rated Easy on LeetCode but requires recognizing the GCD insight. Many beginners attempt brute-force grouping checks first. Once you realize that all frequencies must share a common divisor greater than 1, the solution becomes straightforward.
How to solve X of a Kind in a Deck of Cards in O(n)?
Count the frequency of each card using a hash map. Then compute the GCD of all frequency values. If the resulting GCD is greater than or equal to 2, the deck can be partitioned into equal groups. Otherwise, forming valid groups is impossible.
X of a Kind in a Deck of Cards Python or Java solution
Python and Java implementations both follow the same idea: build a frequency map, then compute the GCD across all counts. Python typically uses collections.Counter and math.gcd, while Java uses HashMap with a helper GCD function. Both achieve O(n) time complexity.
What is the best approach for X of a Kind in a Deck of Cards?
The most efficient approach is frequency counting combined with the Greatest Common Divisor (GCD). Count how many times each card appears, then compute the GCD across all frequencies. If the GCD is at least 2, the deck can be split into groups of that size. This runs in O(n) time and O(n) space.
What data structure is used in X of a Kind in a Deck of Cards?
A hash table (hash map) is used to count how many times each card value appears. After building the frequency map, number theory operations like GCD are applied to those counts to determine whether a common group size exists.
What is the time complexity of X of a Kind in a Deck of Cards?
The optimal solution runs in O(n) time where n is the number of cards. One pass builds a frequency map, and another pass computes the GCD across counts. Space complexity is O(n) in the worst case when all cards are different.
Is X of a Kind in a Deck of Cards asked at Google, Amazon, or Meta?
This problem represents a typical interview pattern involving counting and number theory. Variants of frequency grouping and GCD checks have appeared in interviews at companies like Amazon and Google, especially for screening rounds focused on hash maps and mathematical reasoning.