Leetcode 0945. Minimum Increment to Make Array Unique

Problem statement

https://leetcode.com/problems/minimum-increment-to-make-array-unique/

Solution

Sort our array and traverse it from start, each next element should be maximum among original one and previous, increased by one.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def minIncrementForUnique(self, nums):
        nums = sorted(nums)
        nums2 = nums[:]
        n = len(nums)
        for i in range(1, n):
            nums2[i] = max(nums2[i-1] + 1, nums[i])
            
        return sum(x - y for x, y in zip(nums2, nums))