Skip to main content
Talentd

Partition Array Such That Maximum Difference Is K - Solution & Explanation

MediumArrayGreedySorting15 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

You are given an integer array nums and an integer k. You may partition nums into one or more subsequences such that each element in nums appears in exactly one of the subsequences.

Return the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at most k.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: nums = [3,6,1,2,5], k = 2
Output: 2
Explanation:
We can partition nums into the two subsequences [3,1,2] and [6,5].
The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2.
The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1.
Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.

Example 2:

Input: nums = [1,2,3], k = 1
Output: 2
Explanation:
We can partition nums into the two subsequences [1,2] and [3].
The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1.
The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0.
Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences [1] and [2,3].

Example 3:

Input: nums = [2,2,4,5], k = 0
Output: 3
Explanation:
We can partition nums into the three subsequences [2,2], [4], and [5].
The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0.
The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0.
The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0.
Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
  • 0 <= k <= 105

Approach Overview

Problem Overview: Given an integer array nums and an integer k, split the array into the minimum number of subsequences such that the difference between the maximum and minimum element in each subsequence is at most k. Order inside a subsequence does not matter. The goal is minimizing the number of groups.

Approach 1: Greedy Approach by Sorting (Time: O(n log n), Space: O(1) or O(n) depending on sort)

Sorting simplifies the constraint. Once nums is sorted, the smallest value in a group determines how far the group can extend. Start a group at the first element and keep adding numbers while current - start <= k. The moment the difference exceeds k, start a new group from the current element. This greedy rule works because using the smallest available value as the group's base maximizes how many elements can fit in that group. Each element is processed exactly once after sorting. Sorting dominates the runtime at O(n log n), while the scan itself is O(n). Space is O(1) if the sort is in-place.

This method relies heavily on ordering, which is why the sorting step is essential. The decision rule is purely greedy: extend the current partition as much as possible before creating a new one.

Approach 2: Sliding Window on Sorted Array (Time: O(n log n), Space: O(1))

This version frames the same idea using a window. First sort the array. Maintain two pointers: left marks the start of the current group and right expands the group. As long as nums[right] - nums[left] <= k, keep expanding right. When the difference exceeds k, the current window forms a valid subsequence. Increment the group count, move left to right, and begin forming the next group.

This interpretation highlights the technique used: a sliding window over a sorted structure. Both pointers only move forward, so the traversal remains linear after sorting. The advantage of this formulation is clarity when reasoning about range constraints, which appears frequently in array partitioning problems.

Recommended for interviews: The greedy sorted approach is the expected solution. Interviewers want to see the key observation: once the array is sorted, the smallest element in a group determines the maximum allowable element. Greedily expanding each group guarantees the minimum number of partitions. Explaining the naive idea of checking combinations helps demonstrate understanding, but the sorted greedy scan shows strong problem-solving instincts and knowledge of common array optimization patterns.

Approach 1: Greedy Approach by Sorting

Sort the array first. Then iterate through the sorted numbers to form subsequences. Whenever the difference between the current element and the starting element of this subsequence exceeds k, start a new subsequence. This greedy method ensures that each subsequence uses the minimum elements possible under the condition.

This solution sorts the array and then initializes a counter for subsequences. It iterates over the sorted array, checking the current element's difference with the start of the subsequence. If the difference exceeds k, a new subsequence starts.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) or O(n) depending on the sorting implementation.

Try this approach in the editor →

Approach 2: Sliding Window Approach

A less optimal sorting and sliding technique. First, sort the array. Then use a sliding window approach to manage subsequences efficiently. For each start of the window, expand it until the condition of maximum difference within k becomes false. This solution is insightful but is closer to the greedy approach.

The Python code above first sorts the array, then uses two indices to create a sliding window to determine the range of the current subsequence until the difference condition is breached, then continues.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting plus O(n) scan of the array.
Space Complexity: O(1) as no additional space is used.

Try this approach in the editor →

Approach 3: Greedy + Sorting

The problem requires dividing into subsequences, not subarrays, so the elements in a subsequence can be non-continuous. We can sort the array nums. Assuming the first element of the current subsequence is a, the difference between the maximum and minimum values in the subsequence will not exceed k. Therefore, we can iterate through the array nums. If the difference between the current element b and a is greater than k, then update a to b and increase the number of subsequences by 1. After the iteration, we can obtain the minimum number of subsequences, noting that the initial number of subsequences is 1.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach by Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) or O(n) depending on the sorting implementation.

Sliding Window Approach

Time Complexity: O(n log n) due to sorting plus O(n) scan of the array.
Space Complexity: O(1) as no additional space is used.

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy After SortingO(n log n)O(1) extraBest general solution. Simple scan after sorting guarantees minimum groups.
Sliding Window on Sorted ArrayO(n log n)O(1)Useful when thinking about range constraints or window-based partitioning.

Video Solution

Partition Array Such That Maximum Difference Is K | Simple Thought Process | Leetcode 2294 | MIK • codestorywithMIK • 6,947 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Partition Array Such That Maximum Difference Is K easy or hard?
The problem is rated Medium but conceptually straightforward once you recognize the greedy insight. Many candidates initially overcomplicate it with dynamic programming or brute force. Sorting followed by a linear greedy scan leads directly to the optimal solution.
Partition Array Such That Maximum Difference Is K Python/Java solution
The typical Python or Java implementation sorts the array and iterates once while tracking the start of the current group. If nums[i] - start > k, increment the group count and reset start to nums[i]. The logic is short, usually under 10–15 lines of code.
How to solve Partition Array Such That Maximum Difference Is K in O(n)?
Pure O(n) time is not achievable for arbitrary input because you must know the relative ordering of elements. The standard solution sorts the array first in O(n log n), then performs a linear greedy scan. If the input array were already sorted, the grouping step alone would run in O(n).
What is the best approach for Partition Array Such That Maximum Difference Is K?
The best approach is a greedy strategy after sorting the array. Sort the numbers, start a group with the smallest element, and keep adding elements until the difference between the current value and the group start exceeds k. Once it exceeds k, start a new group. This guarantees the minimum number of partitions with O(n log n) time complexity.
Is Partition Array Such That Maximum Difference Is K asked at Google/Amazon/Meta?
Array partitioning and greedy range grouping problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of sorting first and greedily forming valid groups is a common interview concept.
What data structure is used in Partition Array Such That Maximum Difference Is K?
The solution primarily uses arrays along with sorting and simple pointer variables. Some explanations frame the logic as a sliding window using two pointers on the sorted array. No advanced data structures like heaps or hash maps are required.
What is the time complexity of Partition Array Such That Maximum Difference Is K?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a single linear scan groups elements using a greedy rule, which takes O(n). Space complexity is O(1) if the sort is done in-place.

Ready to solve this problem?

Practice Partition Array Such That Maximum Difference Is K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Next

Maximum Beauty of an Array After Applying Operation