Quick Overview

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.

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/

Overview: 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)

Hints

  1. Count the frequency of each distinct card value.
  2. 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.
  3. Use a running gcd over frequency counts to short-circuit when it becomes 1.

Loading coding console...

Show the approach

Approach

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