LeetCode Problem 3659

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting

Solution

LeetCode 3659 - Partition Array Into K-Distinct Groups

Problem Understanding

We are given an integer array nums and an integer k. The goal is to determine whether all elements of the array can be partitioned into one or more groups such that every group satisfies two conditions:

1. Each group contains exactly k elements.
2. All elements within a group are distinct.

Every element in the original array must be used exactly once. No element can be omitted, and no element can appear in multiple groups.

The input consists of an array that may contain duplicate values. The output is a boolean indicating whether a valid partition exists.

A key observation is that if the array contains n elements, then the total number of groups must be:

$$\text{groups} = \frac{n}{k}$$

Therefore, if n is not divisible by k, it is immediately impossible to partition the array into groups of size exactly k.

The constraints allow up to 10^5 elements, which means any solution that attempts to explicitly construct groups through backtracking or exhaustive search will be far too slow. We need an efficient approach that runs in roughly linear time.

Several edge cases are important:

• The array length may not be divisible by k.
• Some values may appear many times.
• k may be 1, in which case every element forms its own group.
• A value may appear so frequently that there are not enough groups available to place all copies separately.
• The array may contain all identical values.

Understanding how duplicate frequencies interact with the number of groups is the central challenge of the problem.

Approaches

Brute Force

A brute force solution would attempt to explicitly build groups.

One possibility is to repeatedly choose k distinct unused elements to form a group, then recurse on the remaining elements. Another approach would try every possible assignment of elements into groups while checking the distinctness condition.

This approach is correct because it explores all possible valid partitions and returns true if any valid arrangement exists.

Unfortunately, the number of possible groupings grows exponentially. Even for relatively small arrays, the number of ways to distribute elements among groups becomes enormous. Since nums.length can reach 100000, any search-based solution is completely infeasible.

Key Insight

Suppose there are:

$$g = \frac{n}{k}$$

groups.

Because elements within a group must be distinct, copies of the same value cannot appear in the same group.

Therefore, if some value appears f times, those f copies must be distributed across different groups.

Since there are only g groups available, we must have:

$$f \le g$$

for every value.

Remarkably, this condition is not only necessary, it is also sufficient.

Why?

If no value appears more than the number of groups, then each occurrence of a value can be placed into a different group. Since every group has capacity exactly k, and the total number of elements equals g × k, a valid arrangement always exists.

Thus the problem reduces to two checks:

1. n must be divisible by k.
2. The maximum frequency of any value must not exceed n / k.

If both conditions hold, the answer is true.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible group assignments
Optimal	O(n)	O(n)	Count frequencies and verify constraints

Algorithm Walkthrough

1. Let n be the length of nums.
2. Check whether n % k != 0. If the array size is not divisible by k, then it is impossible to create groups containing exactly k elements. Return false.
3. Compute the number of groups:

$$g = \frac{n}{k}$$

This represents the total number of groups that must exist in any valid partition. 4. Count the frequency of every value using a hash map. A hash map is ideal because it provides expected O(1) insertion and lookup time. 5. Iterate through all frequencies. 6. For each frequency f, check whether f > g.

If this happens, there are more copies of that value than there are groups available. Since duplicates cannot coexist within the same group, at least two copies would have to occupy the same group, violating the distinctness requirement. 7. If any frequency exceeds g, return false. 8. If all frequencies satisfy f <= g, return true.

Why it works

Let g = n / k be the required number of groups.

Any value appearing f times must place each occurrence into a different group because groups require distinct elements. Therefore f ≤ g is necessary.

It is also sufficient because once every value appears at most g times, its occurrences can be distributed across the g groups without creating duplicates inside any group. Since the total number of element slots is exactly g × k = n, all elements can be assigned while filling every group completely. Therefore the algorithm returns true exactly when a valid partition exists.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        if n % k != 0:
            return False

        groups = n // k
        frequencies = Counter(nums)

        for count in frequencies.values():
            if count > groups:
                return False

        return True

The implementation begins by computing the array length and verifying that the length is divisible by k. If not, the required groups cannot be formed.

Next, it computes the number of groups that must exist. A Counter is used to count occurrences of every value efficiently.

The algorithm then scans all frequency counts. If any frequency exceeds the number of groups, a valid partition is impossible because duplicates of that value would need to share a group.

If no such frequency exists, all constraints are satisfied and the function returns True.

Go Solution

func partitionArray(nums []int, k int) bool {
	n := len(nums)

	if n%k != 0 {
		return false
	}

	groups := n / k

	freq := make(map[int]int)

	for _, num := range nums {
		freq[num]++
	}

	for _, count := range freq {
		if count > groups {
			return false
		}
	}

	return true
}

The Go solution follows the same logic as the Python version. A map[int]int is used to store frequencies. Go slices naturally handle the input array, and integer arithmetic is sufficient because all values remain well within Go's integer range under the given constraints.

Worked Examples

Example 1

Input

nums = [1,2,3,4]
k = 2

Compute basic values:

Variable	Value
n	4
k	2
groups	2

Frequency table:

Value	Frequency
1	1
2	1
3	1
4	1

Check frequencies:

Frequency	Compare to groups=2	Valid
1	1 ≤ 2	Yes
1	1 ≤ 2	Yes
1	1 ≤ 2	Yes
1	1 ≤ 2	Yes

All frequencies satisfy the condition.

Result: true

Example 2

Input

nums = [3,5,2,2]
k = 2

Compute basic values:

Variable	Value
n	4
groups	2

Frequency table:

Value	Frequency
3	1
5	1
2	2

Check frequencies:

Frequency	Compare to groups=2	Valid
1	1 ≤ 2	Yes
1	1 ≤ 2	Yes
2	2 ≤ 2	Yes

All frequencies satisfy the condition.

One valid arrangement is:

[2,3]
[2,5]

Result: true

Example 3

Input

nums = [1,5,2,3]
k = 3

Compute basic values:

Variable	Value
n	4
k	3

Divisibility check:

4 % 3 = 1

Since the length is not divisible by k, forming groups of size exactly 3 is impossible.

Result: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count frequencies and one pass over distinct values
Space	O(n)	Hash map may store every distinct value

The frequency counting phase processes each element exactly once. The subsequent validation phase iterates through the distinct values. Since the number of distinct values is at most n, the overall time complexity is O(n). The frequency map can contain up to n entries in the worst case, resulting in O(n) auxiliary space.

Test Cases

from typing import List

s = Solution()

assert s.partitionArray([1, 2, 3, 4], 2) is True      # Example 1
assert s.partitionArray([3, 5, 2, 2], 2) is True      # Example 2
assert s.partitionArray([1, 5, 2, 3], 3) is False     # Example 3

assert s.partitionArray([1], 1) is True               # Single element
assert s.partitionArray([1, 1], 1) is True            # Each element alone

assert s.partitionArray([1, 1, 1, 1], 2) is False    # Frequency exceeds groups
assert s.partitionArray([1, 1, 2, 2], 2) is True     # Exactly enough groups

assert s.partitionArray([1, 1, 1], 3) is False       # Same value in one group
assert s.partitionArray([1, 2, 3], 3) is True        # Single valid group

assert s.partitionArray([1, 2, 3, 4, 5, 6], 4) is False  # Length not divisible

assert s.partitionArray([1, 1, 2, 2, 3, 3], 3) is True  # Balanced duplicates

assert s.partitionArray([7] * 100000, 1) is True         # Large input, k=1
assert s.partitionArray([7] * 100000, 2) is False        # Massive frequency violation

Test Summary

Test	Why
[1,2,3,4], k=2	Basic valid partition
[3,5,2,2], k=2	Duplicate values distributed across groups
[1,5,2,3], k=3	Length not divisible by k
[1], k=1	Minimum input size
[1,1], k=1	Every element forms its own group
[1,1,1,1], k=2	Frequency exceeds available groups
[1,1,2,2], k=2	Frequencies exactly match group count
[1,1,1], k=3	Single group cannot contain duplicates
[1,2,3], k=3	One valid group with distinct elements
[1,2,3,4,5,6], k=4	Divisibility failure
[1,1,2,2,3,3], k=3	Balanced duplicate distribution
Large identical array, k=1	Performance and boundary validation
Large identical array, k=2	Extreme frequency violation

Edge Cases

Array Length Not Divisible by k

A common mistake is to focus only on duplicate frequencies while ignoring group sizes. If n is not divisible by k, some group would necessarily contain fewer or more than k elements. The implementation handles this immediately with the check n % k != 0.

A Value Appears More Times Than the Number of Groups

Consider:

nums = [1,1,1,1]
k = 2

There must be 2 groups, but the value 1 appears 4 times. Since each group can contain at most one 1, only two copies can be placed. The remaining copies make a valid partition impossible. The frequency check correctly detects this situation.

k Equals 1

When k = 1, every element forms its own group. Distinctness inside a group is automatically satisfied because each group contains only one element. The number of groups equals n, and every frequency is at most n, so the algorithm correctly returns true for all valid inputs.

All Elements Are Distinct

If every element appears exactly once, the maximum frequency is 1. As long as the array length is divisible by k, a valid partition always exists. The algorithm naturally handles this case because all frequencies are well below the number of groups.

All Elements Are Identical

Consider:

nums = [5,5,5,5,5,5]
k = 3

There must be 2 groups, but the value 5 appears 6 times. Since each group can contain only one 5, the maximum usable copies are 2. The frequency check immediately rejects the input, avoiding any unnecessary group construction.