2294. Partition Array Such That Max Difference Is K

Q: 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.

Q: 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.

The problem

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 <= 10⁵
0 <= nums[i] <= 10⁵
0 <= k <= 10⁵

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.

Python

def min_subsequences(nums, k):
    nums.sort()
    subsequences = 1
    start = nums[0]

    for num in nums[1:]:
        if num - start > k:
            subsequences += 1
            start = num

    return subsequences

print(min_subsequences([3, 6, 1, 2, 5], 2))

Java

import java.util.Arrays;

public class PartitionArray {

    public static int minSubsequences(int[] nums, int k) {
        Arrays.sort(nums);
        int subsequences = 1;
        int start = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - start > k) {
                subsequences++;
                start = nums[i];
            }
        }
        return subsequences;
    }

    public static void main(String[] args) {
        int[] nums = {3, 6, 1, 2, 5};
        int k = 2;
        System.out.println(minSubsequences(nums, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int minSubsequences(std::vector<int>& nums, int k) {
    std::sort(nums.begin(), nums.end());
    int subsequences = 1;
    int start = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] - start > k) {
            subsequences++;
            start = nums[i];
        }
    }
    return subsequences;
}

int main() {
    std::vector<int> nums = {3, 6, 1, 2, 5};
    int k = 2;
    std::cout << minSubsequences(nums, k) << std::endl;
    return 0;
}

JavaScript

function minSubsequences(nums, k) {
    nums.sort((a, b) => a - b);
    let subsequences = 1;
    let start = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] - start > k) {
            subsequences++;
            start = nums[i];
        }
    }
    return subsequences;
}

console.log(minSubsequences([3, 6, 1, 2, 5], 2));

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int minSubsequences(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare);
    int subsequences = 1;
    int start = nums[0];

    for (int i = 1; i < numsSize; i++) {
        if (nums[i] - start > k) {
            subsequences++;
            start = nums[i];
        }
    }
    return subsequences;
}

int main() {
    int nums[] = {3, 6, 1, 2, 5};
    int k = 2;
    printf("%d\n", minSubsequences(nums, sizeof(nums) / sizeof(nums[0]), k));
    return 0;
}

using System;

public class PartitionArray {
    public static int MinSubsequences(int[] nums, int k) {
        Array.Sort(nums);
        int subsequences = 1;
        int start = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] - start > k) {
                subsequences++;
                start = nums[i];
            }
        }
        return subsequences;
    }

    public static void Main(string[] args) {
        int[] nums = new int[] { 3, 6, 1, 2, 5 };
        int k = 2;
        Console.WriteLine(MinSubsequences(nums, k));
    }
}

In this Python solution, the input list is sorted, after which it iterates over each element, checking the difference between the current element and the start of the subsequence before possibly starting a new subsequence.

Complexity

Time Complexity: O(n log n) with list sorting.
Space Complexity: O(1).

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.

Python

def min_subsequences(nums, k):
    nums.sort()
    n = len(nums)
    subsequences = 0
    i = 0

    while i < n:
        j = i
        while j < n and nums[j] - nums[i] <= k:
            j += 1
        subsequences += 1
        i = j
    return subsequences

print(min_subsequences([3, 6, 1, 2, 5], 2))

JavaScript

function minSubsequences(nums, k) {
    nums.sort((a, b) => a - b);
    let n = nums.length;
    let i = 0;
    let subsequences = 0;

    while (i < n) {
        let j = i;
        while (j < n && nums[j] - nums[i] <= k) {
            j++;
        }
        subsequences++;
        i = j;
    }
    return subsequences;
}

console.log(minSubsequences([3, 6, 1, 2, 5], 2));

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.

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.

TypeScript

function partitionArray(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = 1;
    let a = nums[0];
    for (const b of nums) {
        if (b - a > k) {
            a = b;
            ++ans;
        }
    }
    return ans;
}

func partitionArray(nums []int, k int) int {
	sort.Ints(nums)
	ans, a := 1, nums[0]
	for _, b := range nums {
		if b-a > k {
			a = b
			ans++
		}
	}
	return ans
}

Rust

public class Solution {
    public int PartitionArray(int[] nums, int k) {
        Array.Sort(nums);
        int ans = 1;
        int a = nums[0];

        foreach (int b in nums) {
            if (b - a > k) {
                a = b;
                ans++;
            }
        }

        return ans;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach by Sorting	Time Complexity: O(n log n) with list sorting. Space Complexity: O(1).
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	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy After Sorting	O(n log n)	O(1) extra	Best general solution. Simple scan after sorting guarantees minimum groups.
Sliding Window on Sorted Array	O(n log n)	O(1)	Useful when thinking about range constraints or window-based partitioning.

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.

Partition Array Such That Maximum Difference Is K solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach by Sorting

Approach 2: Sliding Window Approach

Approach 3: Greedy + Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Partition Array Such That Maximum Difference Is K solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach by Sorting

Approach 2: Sliding Window Approach

Approach 3: Greedy + Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems