Handle cards, islands, Trie, median
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 914. X of a Kind in a Deck of Cards LeetCode 694. Number of Distinct Islands LeetCode 208. Implement Trie (Prefix Tree) LeetCode 295. Find Median from Data Stream
https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/description/ https://leetcode.com/problems/number-of-distinct-islands/description/ https://leetcode.com/problems/implement-trie-prefix-tree/description/ https://leetcode.com/problems/find-median-from-data-stream/description/
Quick Answer: These problems evaluate proficiency in core data structures and algorithmic problem-solving, covering grouping/counting techniques, grid-based island detection, trie (prefix tree) design, and streaming median computation within the domain of data structures and algorithms.
Given an integer array deck where deck[i] is the value of the i-th card, return true if the deck can be partitioned into one or more groups of size X (X >= 2) such that each group has exactly X cards and all cards in each group have the same value. Otherwise, return false.
Constraints
- 1 <= len(deck) <= 10000
- 0 <= deck[i] <= 10000
- Return a boolean indicating whether such a partition exists
- Time expectation: O(n) where n = len(deck)
Solution
from typing import List
from collections import Counter
from math import gcd
def can_partition_deck(deck: List[int]) -> bool:
if len(deck) < 2:
return False
counts = Counter(deck).values()
g = 0
for c in counts:
g = gcd(g, c)
if g == 1:
return False
return g >= 2
Explanation
Compute the frequency of each value. If the gcd of all frequencies is at least 2, then there exists a group size X equal to that gcd (or a divisor thereof >= 2) such that each count is divisible by X, enabling a partition into groups of equal size with identical values. If the gcd ever reduces to 1, no such X >= 2 exists.
Time complexity: O(n). Space complexity: O(k) where k is the number of distinct card values.
Hints
- Count the frequency of each distinct card value.
- A partition into equal-sized same-value groups is possible if and only if the greatest common divisor (gcd) of all frequencies is at least 2.
- Use a running gcd over frequency counts to short-circuit when it becomes 1.