Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2294.html
2294. Partition Array Such That Maximum Difference Is K
- Difficulty: Medium.
- Related Topics: Array, Greedy, Sorting.
- Similar Questions: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
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 <= 105
-
0 <= nums[i] <= 105
-
0 <= k <= 105
Solution (Java, C++, Python)
-
class Solution { public int partitionArray(int[] nums, int k) { Arrays.sort(nums); int partitions = 1; int j = 0; for (int i = 1; i < nums.length; i++) { if (nums[i] - nums[j] > k) { partitions++; j = i; } } return partitions; } } ############ class Solution { public int partitionArray(int[] nums, int k) { Arrays.sort(nums); int ans = 1, a = nums[0]; for (int b : nums) { if (b - a > k) { a = b; ++ans; } } return ans; } }
-
class Solution: def partitionArray(self, nums: List[int], k: int) -> int: nums.sort() ans, a = 1, nums[0] for b in nums: if b - a > k: a = b ans += 1 return ans ############ # 2294. Partition Array Such That Maximum Difference Is K # https://leetcode.com/problems/partition-array-such-that-maximum-difference-is-k/ class Solution: def partitionArray(self, nums: List[int], k: int) -> int: n = len(nums) nums.sort() res = 1 mmin = mmax = nums[0] for i in range(1, n): if nums[i] > mmax: mmax = nums[i] if nums[i] < mmin: mmin = nums[i] if mmax - mmin > k: res += 1 mmax = mmin = nums[i] return res
-
class Solution { public: int partitionArray(vector<int>& nums, int k) { sort(nums.begin(), nums.end()); int ans = 1, a = nums[0]; for (int& b : 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 }
-
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; }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).