Watch 9 video solutions for Partition Array Into K-Distinct Groups, a medium level problem involving Array, Hash Table, Counting. This walkthrough by ExpertFunda has 426 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums and an integer k.
Your task is to determine whether it is possible to partition all elements of nums into one or more groups such that:
k elements.nums must be assigned to exactly one group.Return true if such a partition is possible, otherwise return false.
Example 1:
Input: nums = [1,2,3,4], k = 2
Output: true
Explanation:
One possible partition is to have 2 groups:
[1, 2][3, 4]Each group contains k = 2 distinct elements, and all elements are used exactly once.
Example 2:
Input: nums = [3,5,2,2], k = 2
Output: true
Explanation:
One possible partition is to have 2 groups:
[2, 3][2, 5]Each group contains k = 2 distinct elements, and all elements are used exactly once.
Example 3:
Input: nums = [1,5,2,3], k = 3
Output: false
Explanation:
We cannot form groups of k = 3 distinct elements using all values exactly once.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105​​​​​​​1 <= k <= nums.lengthProblem Overview: You are given an integer array and an integer k. The task is to determine whether the array can be partitioned into groups where each group contains exactly k distinct elements. Elements may repeat across different groups, but duplicates are not allowed inside the same group.
Approach 1: Greedy Simulation with Frequency Tracking (O(n log n) time, O(n) space)
Count the frequency of each value using a hash map from hash table. Repeatedly build groups by selecting up to k different numbers whose frequency is still positive. Each time you place a number in a group, decrement its count. Using a priority queue or sorted structure helps pick available numbers while maintaining counts. The approach simulates the grouping process directly, which is intuitive but slightly heavier because each group formation may require sorting or heap operations.
Approach 2: Counting Observation (O(n) time, O(n) space)
The key observation: if the array length is n, you must create exactly n / k groups. Since each group must contain k distinct elements, the same number cannot appear more than once in a single group. That means a value appearing f times must be distributed across at least f different groups. Using a frequency map from hash table or counting, compute the maximum frequency of any element. If maxFreq is less than or equal to the number of groups (n / k), the partition is possible. Otherwise, at least one value would need to appear twice in a group, which violates the distinct constraint.
This observation eliminates the need to simulate grouping. A single pass builds the frequency map, and another pass checks the maximum frequency.
Recommended for interviews: The counting approach. Interviewers expect you to recognize that the constraint is driven by the maximum frequency relative to the number of groups. Brute simulation shows understanding of the grouping process, but the counting insight demonstrates stronger problem‑solving and familiarity with array frequency patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation with Heap | O(n log n) | O(n) | Useful for understanding the actual grouping process or when constraints require explicit construction of groups |
| Frequency Counting Observation | O(n) | O(n) | Best general solution when only feasibility needs to be checked |