# 945. Minimum Increment to Make Array Unique

- Given integer array "nums" of size n.
- You can pick an index i and increment nums[i] by 1
- Return the minimum number of moves to make every value in nums unique.
- 1 <= n <= 10^5
- 1 <= range <= 10^5

Example 1
nums = [1,2,2]
[1,2,3]
Output 1

Example 2
nums = [1,1,2,2,3,7]
already used max 1 2 3 4 5 7
[1,2,3,4,5,7]
Output 6

1. not sorted

set to record num occurs in array
loop array
1 {1}
1+1->2 {1, 2, 3, 4}

[1, 1, 1, 1] -> O(n*2)
...

def findMoves(nums):
    
    # sort
    nums.sort()
    
    # [1,1,2,2,3,7]
    # init set
    seen = set() # new a empty {'1', '2'}
    # {'1':2} 
    moves = 0
    usedMax = 0
    
    # loop n
    for n in nums:
        if n in seen:
            # use usedMax+1
            usedMax = usedMax+1 # 3
            diff = usedMax - n # 3 - 2
            moves += diff # 1+1
            seen.add(usedMax)
        else:
            usedMax = n
            seen.add(n)
        
        # set {1, 2, 3}
        # usedMax = 2

    return moves


def findMoves(nums):
    # init set
    seen = set()
    moves = 0
    # loop n
    # [1, 2, 2]
    for n in nums:
        while n in seen:
            n += 1 # 3
            moves += 1
        seen.add(n)
        # {1, 2, 3}
 
    return moves
    
    
def findMoves(nums):
    # init set
    costMap = defaultdict(list)
    # "":[]
    minValue = min(nums)
    maxValue = max(nums)
    for n, c in zip(nums, cost):
        heappush(costMap[n], c)
        
    moves = 0
    for cur in range(minValue, maxValue+len(nums)):
        if cur not in costMap:
            continue
        
        while len(costMap[cur]) > 1:
            cost = heappop(costMap[cur])
            moves += cost
            heappush(costMap[cur+1], cost)
    
    return moves
            

- Given integer array "nums" and "cost" of size n.
- You can pick an index i and increment nums[i] by 1 with cost[i]
- Return the minimum cost to make every value in nums unique.

nums [1,1,1,1,1,2,3]
cost [6,1,3,4,5,2,7]

cost += 1+3+4+5
nums [1,2,2,2,2,2,3]
cost [6,1,3,4,5,2,7]

1 {1,3,4,5,6}