Skip to content

← leetcode

Partition Array Such That Maximum Difference Is K

· Medium

LeetCode problem 2294

Basically, I wanted to follow a greedy algorithm, since from a logical standpoint, for any partition we set, we want to maximise the "useful" distance it covers.

For example, if the smallest number in nums is 10, it does not make sense to start a partition from 9 as we are effectively wasting 1 number.

Therefore, for a greedy algorithm to succeed, I decided to just sort nums first from smallest to largest. Then, I can start my first partition from the smallest number and just make new partitions once the consequent number exceeds the limits of the current partition.

This will allow us to minimise the number of partitions used, which we can count and then return at the end.

code

class Solution {
public:
    int partitionArray(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 1;
        int curr = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (curr + k < nums[i]) {
                curr = nums[i];
                ++ans;
            }
        }
        return ans;
    }
};

complexity

  • Time: O(n log(n))
  • Space: O(1)

time taken

  • 1 minute and 22 seconds