Skip to main content
Talentd

Partition Array Into K-Distinct Groups - Solution & Explanation

MediumArrayHash TableCounting8 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • Each group contains exactly k elements.
  • All elements in each group are distinct.
  • Each element in 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:

  • Group 1: [1, 2]
  • Group 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:

  • Group 1: [2, 3]
  • Group 2: [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 <= 105
  • 1 <= nums[i] <= 105
  • ​​​​​​​1 <= k <= nums.length

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Simulation with HeapO(n log n)O(n)Useful for understanding the actual grouping process or when constraints require explicit construction of groups
Frequency Counting ObservationO(n)O(n)Best general solution when only feasibility needs to be checked

Video Solution

Leetcode 3659 | Partition Array Into K-Distinct Groups Detailed Solution with Dry run |Contest464 Q2 • Samrat Bhardwaj • 351 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Partition Array Into K-Distinct Groups easy or hard?
This problem is typically rated Medium because the implementation is simple but requires recognizing the key counting insight. Many candidates initially attempt simulation before realizing the maximum-frequency constraint.
Partition Array Into K-Distinct Groups Python/Java solution
Implement the solution by counting frequencies with a dictionary in Python or a HashMap in Java. Compute the number of groups n/k, track the maximum frequency, and return true if maxFreq <= n/k. The implementation runs in O(n) time.
How to solve Partition Array Into K-Distinct Groups in O(n)?
First compute n/k, which is the number of groups required. Build a frequency map of the array using a hash table. Track the maximum frequency of any element. If maxFreq <= n/k, each occurrence can be placed in a different group, so the partition is valid; otherwise it is impossible.
What is the best approach for Partition Array Into K-Distinct Groups?
The most efficient approach uses frequency counting with a hash map. If the array length is n, you must form n/k groups. Compute the frequency of each value and track the maximum frequency. If the maximum frequency is greater than the number of groups, partitioning is impossible. This runs in O(n) time and O(n) space.
Is Partition Array Into K-Distinct Groups asked at Google/Amazon/Meta?
Problems based on frequency counting, grouping constraints, and hash maps appear frequently in interviews at companies like Amazon, Google, and Meta. Variants that check feasibility of forming groups using frequency limits are common in array and counting interview questions.
What data structure is used in Partition Array Into K-Distinct Groups?
A hash map (or dictionary) is the primary data structure used to store element frequencies. The algorithm relies on counting occurrences and comparing the maximum frequency against the number of required groups.
What is the time complexity of Partition Array Into K-Distinct Groups?
The optimal solution runs in O(n) time because it requires a single pass to build the frequency map and another pass to determine the maximum frequency. Space complexity is O(n) in the worst case when all elements are distinct.

Ready to solve this problem?

Practice Partition Array Into K-Distinct Groups with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays