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] <= 1051 <= 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.
We denote the length of the array as n. If n is not divisible by k, then we cannot partition the array into groups where each group contains k elements, so we directly return false.
Next, we calculate the size of each group m = n / k and count the occurrence of each element in the array. If the occurrence count of any element exceeds m, then it cannot be distributed to any group, so we directly return false.
Finally, if the occurrence count of all elements does not exceed m, then we can partition the array into groups where each group contains k elements, and we return true.
Time complexity O(n), space complexity O(n) or O(M). Where n is the length of the array, and M is the maximum value of elements in the array.
Python
Java
C++
Go
TypeScript
| 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 |
Partition Array Into K-Distinct Groups | Q2 - Weekly Contest 464 • ExpertFunda • 426 views views
Watch 8 more video solutions →Practice Partition Array Into K-Distinct Groups with our built-in code editor and test cases.
Practice on FleetCode