LeetCode 2294 - Partition Array Such That Maximum Difference Is K

The problem gives us an integer array nums and an integer k. We must divide the array into one or more subsequences such that every number belongs to exactly one subsequence, and for every subsequence, the difference between its maximum value and minimum value is at most k.

leetcodemediumarraygreedysorting

LeetCode Problem 2294

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an integer array nums and an integer k. We must divide the array into one or more subsequences such that every number belongs to exactly one subsequence, and for every subsequence, the difference between its maximum value and minimum value is at most k.

The goal is to minimize the number of subsequences.

A very important detail is that the subsequences do not need to remain contiguous. Since we are free to choose any elements while preserving relative order, the actual order of the elements becomes much less important than their values. This observation is the key to the optimal solution.

For any subsequence:

  • max(subsequence) - min(subsequence) <= k

We want to group as many values together as possible while respecting this constraint.

For example:

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

If we sort the values:

[1,2,3,5,6]

We can group:

[1,2,3]
[5,6]

The first group has difference 3 - 1 = 2, and the second has difference 6 - 5 = 1.

The answer is therefore 2.

The constraints are important:

  • nums.length can be as large as 10^5
  • Values can also be as large as 10^5

This immediately tells us that exponential or quadratic partitioning approaches will be too slow. We need something close to O(n log n) or better.

There are several important edge cases to keep in mind:

  • Arrays with only one element
  • k = 0, where only equal values can belong to the same subsequence
  • Arrays where all values already fit into one valid subsequence
  • Arrays where every element must become its own subsequence
  • Duplicate values
  • Unsorted input

The problem guarantees that the array is non-empty, so we never need to handle an empty input.

Approaches

Brute Force Approach

A brute force solution would attempt to explore all possible ways to partition the array into subsequences.

For each element, we could try placing it into every existing subsequence where it remains valid, or start a new subsequence. We would recursively explore every possible grouping and track the minimum number of subsequences used.

This approach is correct because it exhaustively checks every valid partition.

However, it is computationally infeasible. The number of possible partitions grows exponentially with the size of the array. Even for moderate input sizes, the runtime becomes enormous.

Since n can be 100000, brute force is completely impractical.

Key Insight

The critical observation is that only the minimum and maximum values inside a subsequence matter.

If we sort the array, then values that are close together naturally belong in the same subsequence.

Suppose we have sorted values:

a <= b <= c

If:

c - a <= k

then all three can safely belong to the same subsequence.

But if:

current_value - group_min > k

then the current value cannot belong to the current subsequence, and we must start a new one.

This leads to a greedy strategy:

  1. Sort the array.
  2. Start a subsequence with the smallest remaining number.
  3. Keep adding numbers while the difference from the subsequence minimum stays within k.
  4. Once the difference exceeds k, start a new subsequence.

This works because sorting ensures that extending the current group greedily is always optimal.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries all possible partitions
Optimal Greedy + Sorting O(n log n) O(1) or O(log n) Sorts values and greedily forms groups

Algorithm Walkthrough

  1. Sort the array in non-decreasing order.

Sorting allows us to process values from smallest to largest. Once sorted, every valid subsequence corresponds to a contiguous range in sorted order. 2. Initialize the subsequence count.

We start with one subsequence because the first element must belong somewhere. 3. Track the minimum value of the current subsequence.

Let group_start represent the smallest value in the current subsequence. 4. Iterate through the sorted array.

For each number:

  • If:
current_number - group_start <= k

then the number can safely belong to the current subsequence.

  • Otherwise, the current number cannot fit into the existing subsequence, so we:

  • Start a new subsequence

  • Increment the answer

  • Set group_start to the current number

  1. Return the total number of subsequences formed.

Why it works

After sorting, all numbers between the minimum and maximum of a subsequence are naturally grouped together.

The greedy strategy always maximizes the size of the current subsequence before starting a new one. Starting a new subsequence earlier would only increase the number of groups without providing any benefit.

Therefore, the greedy partitioning produces the minimum possible number of subsequences.

Python Solution

from typing import List

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()

        subsequences = 1
        group_start = nums[0]

        for num in nums:
            if num - group_start > k:
                subsequences += 1
                group_start = num

        return subsequences

The implementation begins by sorting the array. This is the most important step because it transforms the problem into grouping nearby values together.

We initialize subsequences to 1 because at least one subsequence is needed for a non-empty array.

The variable group_start stores the minimum value of the current subsequence. Since the array is sorted, this value never changes unless we start a new subsequence.

As we iterate through the sorted numbers, we check whether the current number can still fit into the current subsequence:

num - group_start <= k

If the condition fails, we must create a new subsequence. We increment the answer and reset group_start.

At the end, subsequences contains the minimum number of valid subsequences.

Go Solution

package main

import "sort"

func partitionArray(nums []int, k int) int {
	sort.Ints(nums)

	subsequences := 1
	groupStart := nums[0]

	for _, num := range nums {
		if num-groupStart > k {
			subsequences++
			groupStart = num
		}
	}

	return subsequences
}

The Go implementation follows the exact same greedy logic as the Python version.

The main difference is the use of:

sort.Ints(nums)

to sort the slice in place.

Go slices behave similarly to dynamic arrays, so no special handling is required for memory management here.

Integer overflow is not a concern because values are limited to 10^5.

Worked Examples

Example 1

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

After sorting:

[1,2,3,5,6]
Current Number group_start Difference Action Subsequences
1 1 0 Continue current group 1
2 1 1 Continue current group 1
3 1 2 Continue current group 1
5 1 4 Start new group 2
6 5 1 Continue current group 2

Final answer:

2

Example 2

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

Sorted array:

[1,2,3]
Current Number group_start Difference Action Subsequences
1 1 0 Continue current group 1
2 1 1 Continue current group 1
3 1 2 Start new group 2

Final answer:

2

Example 3

nums = [2,2,4,5]
k = 0

Sorted array:

[2,2,4,5]
Current Number group_start Difference Action Subsequences
2 2 0 Continue current group 1
2 2 0 Continue current group 1
4 2 2 Start new group 2
5 4 1 Start new group 3

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Depends on sorting implementation

The greedy scan after sorting is linear, O(n).

The sorting step costs O(n log n), which dominates the overall runtime.

The algorithm itself only uses a few variables, so auxiliary space is constant. However, the underlying sorting implementation may use recursion stack space.

Test Cases

from typing import List

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> int:
        nums.sort()

        subsequences = 1
        group_start = nums[0]

        for num in nums:
            if num - group_start > k:
                subsequences += 1
                group_start = num

        return subsequences

solution = Solution()

assert solution.partitionArray([3, 6, 1, 2, 5], 2) == 2  # Example 1
assert solution.partitionArray([1, 2, 3], 1) == 2  # Example 2
assert solution.partitionArray([2, 2, 4, 5], 0) == 3  # Example 3

assert solution.partitionArray([1], 0) == 1  # Single element
assert solution.partitionArray([5, 5, 5], 0) == 1  # All equal
assert solution.partitionArray([1, 10, 20], 0) == 3  # Every element separate
assert solution.partitionArray([1, 2, 3, 4, 5], 10) == 1  # Entire array fits
assert solution.partitionArray([4, 1, 7, 3], 3) == 2  # Unsorted input
assert solution.partitionArray([1, 1, 1, 2, 2, 2], 0) == 2  # Duplicate groups
assert solution.partitionArray([1, 4, 7, 10], 2) == 4  # No adjacent pair fits
assert solution.partitionArray([1, 3, 5, 7], 2) == 2  # Alternating grouping

Test Case Summary

Test Why
[3,6,1,2,5], k=2 Validates standard grouping behavior
[1,2,3], k=1 Tests boundary where one value exceeds limit
[2,2,4,5], k=0 Ensures only equal values can group
[1], k=0 Smallest valid input
[5,5,5], k=0 All identical values
[1,10,20], k=0 Every element becomes its own subsequence
[1,2,3,4,5], k=10 Entire array fits into one group
[4,1,7,3], k=3 Confirms sorting is necessary
[1,1,1,2,2,2], k=0 Duplicate value grouping
[1,4,7,10], k=2 No neighboring values fit together
[1,3,5,7], k=2 Multiple optimal groups

Edge Cases

Single Element Array

If the array contains only one number, the answer must always be 1 because a single value automatically satisfies:

max - min = 0

A careless implementation might incorrectly initialize the answer to 0, but this solution correctly starts with one subsequence.

k = 0

When k is zero, every subsequence must contain only identical values.

For example:

[2,2,4,5]

must become:

[2,2], [4], [5]

The implementation handles this naturally because any difference greater than zero forces a new subsequence.

Entire Array Fits Into One Subsequence

If:

max(nums) - min(nums) <= k

then the whole array belongs in one subsequence.

For example:

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

The algorithm never triggers the condition to start a new group, so the answer correctly remains 1.

Every Element Requires Its Own Subsequence

If neighboring sorted values differ by more than k, every element must become its own subsequence.

For example:

nums = [1,4,7,10]
k = 2

Every iteration triggers creation of a new subsequence.

The implementation correctly increments the counter each time the allowed range is exceeded.