Scale Engineer

X of a Kind in a Deck of Cards

Easy
#0868Time: O(N + U * C_min), where N is the number of cards, U is the number of unique cards, and C_min is the minimum frequency. Counting frequencies takes O(N). The outer loop runs C_min times, and the inner loop runs U times. In the worst case, this can be close to O(N^2).Space: O(U), where U is the number of unique cards. This is for storing the frequency map. In the worst case, U can be equal to N (the total number of cards), making the space complexity O(N).
Patterns
MathCountingNumber Theory
Data structures
ArrayHash Table

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first counts the occurrences of each card number. Then, it iterates through all possible group sizes x (from 2 up to the minimum count of any card) and checks if x can divide all the card counts evenly. If such an x is found, it means a valid partition is possible.

Algorithm

  • Create a frequency map (e.g., a HashMap) to store the count of each card in the deck.
  • Iterate through the deck to populate the frequency map.
  • Find the minimum frequency, min_freq, among all the values in the map.
  • If min_freq is less than 2, it's impossible to form groups of size x > 1, so return false.
  • Iterate through all possible group sizes x from 2 up to min_freq.
  • For each x, check if it divides every frequency in the map.
    • If x divides all frequencies, a valid partition is found. Return true.
    • If x fails to divide any frequency, it's not a valid group size, so continue to the next x.
  • If the loop completes without finding a suitable x, return false.

Walkthrough

The most straightforward way to solve this problem is to simulate the check for every possible group size x.

First, we need to know the counts of each type of card. A hash map is a suitable data structure for this, mapping each card number to its frequency in the deck.

Once we have the counts, we know that any valid group size x must divide every single one of these counts. The smallest possible group size is 2, and the largest possible group size cannot exceed the count of the least frequent card. Let's call this minimum frequency min_freq.

So, we can simply test every integer x from 2 to min_freq. For each x, we iterate through all the frequencies we counted and check if count % x == 0. If this condition holds true for all counts, we have found a valid x and can immediately return true. If we check all possible values of x up to min_freq and none of them work, then no such partition is possible, and we return false.

import java.util.HashMap;import java.util.Map; class Solution {    public boolean hasGroupsSizeX(int[] deck) {        if (deck.length < 2) {            return false;        }        Map<Integer, Integer> counts = new HashMap<>();        for (int card : deck) {            counts.put(card, counts.getOrDefault(card, 0) + 1);        }         int minFreq = Integer.MAX_VALUE;        for (int count : counts.values()) {            minFreq = Math.min(minFreq, count);        }         if (minFreq < 2) {            return false;        }         for (int x = 2; x <= minFreq; x++) {            boolean isDivisible = true;            for (int count : counts.values()) {                if (count % x != 0) {                    isDivisible = false;                    break;                }            }            if (isDivisible) {                return true;            }        }         return false;    }}

Complexity

Time

O(N + U * C_min), where N is the number of cards, U is the number of unique cards, and C_min is the minimum frequency. Counting frequencies takes O(N). The outer loop runs C_min times, and the inner loop runs U times. In the worst case, this can be close to O(N^2).

Space

O(U), where U is the number of unique cards. This is for storing the frequency map. In the worst case, U can be equal to N (the total number of cards), making the space complexity O(N).

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • Straightforward to implement without requiring advanced mathematical concepts.

Cons

  • Inefficient for large inputs, especially when the minimum frequency is large.

  • The time complexity can be high, potentially leading to a 'Time Limit Exceeded' error on competitive programming platforms.

Solutions

class Solution {public  boolean hasGroupsSizeX(int[] deck) {    int[] cnt = new int[10000];    for (int v : deck) {      ++cnt[v];    }    int g = -1;    for (int v : cnt) {      if (v > 0) {        g = g == -1 ? v : gcd(g, v);      }    }    return g >= 2;  }private  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem