945 Minimum Increment to Make Array Unique

Link Minimum Increment to Make Array Unique

Thought

Firstly, I try to enumerate all existing number, and I got TLE :(. Then I realized I could sort the origin array and maintain a upper boundary, for any number, if it smaller than upper boundary, means I can only move it to upper boundary + 1 and count the moves. Otherwise, set the upper boundary to that number and keep going. 

Code

class Solution(object):
    def minIncrementForUnique(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if not A:
            return 0
        p = dict()
        A.sort()
        cnt = 0
        upper = A[0]
        for i in A[1:]:
            if i <= upper:
                upper +=1
                cnt += upper - i
            else:
                upper = i 
        return cnt

Runtime

Time: O(nlogn)
Space: O(1)