2294. Partition Array Such That Maximum Difference Is K

MediumGreedyArraySorting
Leetcode Link

Problem Description

In the given problem, we are presented with an array of integers named nums and an integer k. Our goal is to partition the array into one or more subsequences so that no number appears in more than one subsequence, and furthermore, within each subsequence, the largest difference between the maximum and minimum elements does not exceed k. The task is to determine the minimum number of such subsequences required.

A subsequence is defined as a sequence that can be obtained from the original sequence by possibly removing elements, without changing the order of the remaining elements.

Intuition

To solve this problem, we can take advantage of the property that if a sequence is sorted, the difference between consecutive elements will give us the smallest possible differences. Thus, an effective approach is to sort the nums array first. After sorting, we can iterate through the elements, starting a new subsequence whenever we encounter an element that would cause the difference between the current element and the smallest element of the current subsequence to exceed k.

By always tracking the smallest element, a, of the current subsequence as we traverse through the sorted list, we can simply increment the count of subsequences, ans, each time we need to start a new subsequence. The moment we need to create a new subsequence is identified when the difference between the current number b and the smallest number a in the subsequence is greater than k. When that happens, b becomes the starting element of the new subsequence, and therefore, a is updated to b, and ans is incremented to reflect the creation of a new subsequence.

This approach ensures that for each subsequence we form, every pair of elements within the subsequence has a difference less than or equal to k, and that we minimize the total number of subsequences needed by using the sorted nature of the array to keep each subsequence as long as possible before the condition necessitating a new subsequence is met.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Solution Approach

The solution to this problem leverages the sorting algorithm and basic iteration over the sorted array. Here is a step-by-step breakdown of the implementation:

  1. First, we sort the nums array. Sorting is a common pre-processing step when dealing with problems that require ordering or arranging of elements. In Python, this is easily done with the .sort() method, which sorts the list in place in ascending order. The sorted array allows us to consider elements in their natural order and make decisions based on their relative positions.

  2. We initialize two variables: ans and a. The ans is set to 1 since, at minimum, one subsequence is needed, irrespective of the value of k. The a is set to the first element of the sorted array; it represents the smallest element of the current subsequence.

  3. We iterate over each element b in the sorted nums array. During this iteration, we compare each element with a to determine if a new subsequence is needed. If b - a exceeds k, it means adding b to the current subsequence would violate the condition that the difference between the maximum and minimum values in any subsequence should be at most k.

  4. When the condition b - a > k is true, a new subsequence is started with b as the initial element. This is done by updating a to be b and incrementing ans by one, to account for this new subsequence.

  5. The iteration continues until all elements have been assigned to some subsequence. Since we are assured that elements in each subsequence satisfy the difference condition and that elements are not assigned to more than one subsequence, the process guarantees that the final value of ans is the minimum number of subsequences needed.

The algorithm's time complexity is dominated by the sorting step, which is (O(n \log n)), where (n) is the number of elements in nums. The iteration is a linear scan, adding only (O(n)) to the time complexity. Therefore, the total time complexity is (O(n \log n)). There's no additional significant space complexity overhead, as everything is done in place, making the space complexity (O(1)) aside from the input.

Overall, this is an efficient and straightforward approach that uses sorting to ensure the minimum number of subsequences by keeping track of the minimum element and incrementing the count of subsequences whenever a difference condition requires starting a new subsequence.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Problem Example:

Given an array nums = [3, 1, 2, 7, 4, 6] and an integer k = 3, we want to find the minimum number of subsequences such that the difference between the max and min elements in each subsequence is at most k.

Step-by-step Walkthrough:

  1. Sort the array nums: First, we sort the array to easily find subsequences where the differences between numbers are minimal. After sorting, our nums array becomes [1, 2, 3, 4, 6, 7].

  2. Initialize variables: We initialize ans to 1, as at least one subsequence is always required. We also take the first element of the sorted array as variable a, so a = 1.

  3. Iterate and check differences: We go through each sorted element b, starting from the second one, and check whether including b in the current subsequence would exceed the difference of k = 3.

    • b = 2: b - a = 2 - 1 = 1, which is not greater than k, so b is part of the current subsequence.
    • b = 3: b - a = 3 - 1 = 2, which, again, is not greater than k, so b remains in the current subsequence.
    • b = 4: b - a = 4 - 1 = 3, equal to k, but still not greater, so b is still in the current subsequence.
    • b = 6: b - a = 6 - 1 = 5, which is greater than k, so we cannot include b in this subsequence. Therefore, we increment ans by 1, making ans = 2, and update a to b, so now a = 6.
    • b = 7: b - a = 7 - 6 = 1, which is less than k, so b is included in this new subsequence.

  4. Incrementing counts of subsequences: Each time we find that b - a exceeds k, we start a new subsequence and increment ans. In this example, this only happened once.

Final result: After covering all elements, we've determined that a minimum of ans = 2 subsequences are needed to satisfy the stated conditions, resulting in subsequences, say, [1, 2, 3, 4] and [6, 7].

This example demonstrates that by sorting the array and smartly grouping elements, we minimize the number of subsequences needed while satisfying the conditions of the problem.

Solution Implementation

1from typing import List
2
3class Solution:
4    def partitionArray(self, nums: List[int], k: int) -> int:
5        # First, sort the array to allow for linear partitioning.
6        nums.sort()
7
8        # Initialize the number of partitions needed with at least 1.
9        partitions_count = 1
10      
11        # Set the first element as the initial value for comparison.
12        min_value_in_current_partition = nums[0]
13      
14        # Iterate over sorted numbers to determine the need for partitions.
15        for num in nums:
16            # If the current number minus the minimum value in the current
17            # partition exceeds k, this requires a new partition.
18            if num - min_value_in_current_partition > k:
19                # Set the current number as the new minimum value for the next partition.
20                min_value_in_current_partition = num
21              
22                # Increment the partitions count as we need another partition.
23                partitions_count += 1
24      
25        # Return the total number of partitions needed.
26        return partitions_count
27
1class Solution {
2
3    public int partitionArray(int[] nums, int k) {
4        // Sort the input array in ascending order
5        Arrays.sort(nums);
6      
7        // Initialize the count of partitions needed, starting with 1
8        int partitionCount = 1;
9      
10        // Store the first number as the starting point of the first partition
11        int partitionStart = nums[0];
12      
13        // Iterate through all numbers in the array
14        for (int currentNumber : nums) {
15            // If the current number minus the partition start is greater than k,
16            // a new partition is needed
17            if (currentNumber - partitionStart > k) {
18                // Update the starting point to the current number
19                partitionStart = currentNumber;
20                // Increment the partition count
21                ++partitionCount;
22            }
23        }
24      
25        // Return the total number of partitions required
26        return partitionCount;
27    }
28}
29
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to determine the minimum number of groups with each group having differences
7    // between numbers not greater than k.
8    int partitionArray(vector<int>& nums, int k) {
9        // Sort the input vector to make it easier to group elements.
10        sort(nums.begin(), nums.end());
11
12        // Initialize 'groupsCount' to 1 since the first element starts the first group.
13        int groupsCount = 1;
14        // The 'currentGroupStart' is the first element in the current group.
15        int currentGroupStart = nums[0];
16
17        // Iterate through the sorted numbers.
18        for (int& currentNum : nums) {
19            // If the difference between the current number and the start of the current group
20            // is greater than k, a new group must be started.
21            if (currentNum - currentGroupStart > k) {
22                // Update 'currentGroupStart' to the current number.
23                currentGroupStart = currentNum;
24                // Increment the 'groupsCount' as a new group is created.
25                groupsCount++;
26            }
27        }
28        // Return the total number of groups created.
29        return groupsCount;
30    }
31};
32
1function partitionArray(nums: number[], k: number): number {
2    // Sort the array in non-decreasing order to allow for partition counting based on the difference
3    nums.sort((a, b) => a - b);
4
5    // Initialize the partition count to 1, as there will be at least one partition
6    let partitionCount = 1;
7
8    // Set the current number to track from the first number in the sorted array
9    let currentNum = nums[0];
10
11    // Iterate through the sorted numbers
12    for (const nextNum of nums) {
13        // Check if the current number and the next number's difference is greater than 'k'
14        if (nextNum - currentNum > k) {
15            // If so, set the current tracking number to the next number
16            // and increment the partition count as we need a new partition
17            currentNum = nextNum;
18            partitionCount++;
19        }
20    }
21
22    // Return the total number of partitions needed
23    return partitionCount;
24}
25
Not Sure What to Study? Take the 2-min Quiz：

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

Time Complexity

The time complexity of the provided code primarily comes from sorting the nums list. The sort operation in Python typically has an average case time complexity of O(n log n), where n is the length of the list being sorted. After sorting, the code iterates through the sorted list once, which has a time complexity of O(n). Since O(n log n) dominates the overall time complexity, we can conclude that the total time complexity of the function is O(n log n).

Space Complexity

The space complexity of the code is the amount of additional memory space required by the algorithm as a function of the input size. The sorting of the list nums in place does not require extra space proportional to the size of the input, resulting in a space complexity of O(1), which means it is constant space complexity. However, it is worth mentioning that the sort algorithm may have a space complexity of O(log n) under the hood because of the stack frames used in recursive calls if the sort algorithm is based on recursion (like quicksort or mergesort). But this is not reflected in the auxiliary space usage as it is not part of the explicit space used by the program.

Thus, the space complexity is O(1) or O(log n) depending on the implementation details of the sorting algorithm which is an implementation detail of Python's sort() method.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫