Skip to main content
Talentd

X of a Kind in a Deck of Cards - Solution & Explanation

EasyArrayHash TableMathCounting16 min readAsked at: Amazon, Google
Practice this problem

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 x cards where x > 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 <= 104
  • 0 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(m), where m is the number of unique numbers due to the frequency array.

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.
Space Complexity: O(m) for the frequency array.

Greatest Common Divisor—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Counting and GCDO(n)O(n)Best general solution; converts grouping constraint into a single GCD check
Counting Elements and Checking Lowest FrequencyO(n + k)O(n)Useful for understanding the grouping logic by testing candidate group sizes

Video Solution

X of a kind in a deck || Leetcode • Pepcoding • 4,856 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice X of a Kind in a Deck of Cards with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays