⚡Flashcard Drill➔
NeetCode #774LC-945MediumGreedy
← Back to All Problems

#774 · #945 · Minimum Increment to Make Array Unique(使数组唯一的最小增量)

📌 Problem Statement & Constraints

Given an integer array nums, in one move you may increment any element by 1. Return the minimum number of moves to make every value in nums unique. Constraints: 1 <= nums.length <= 10^5, 0 <= nums[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Sort the array so equal values become adjacent.
  2. Scan left to right, ensuring each element is strictly greater than the previous one.
  3. If nums[i] <= nums[i-1], raise it to nums[i-1] + 1 and add the difference to the answer.
  4. Incrementing only (never decrementing) is what makes raising to the previous value plus one optimal.

💻 Benchmark Python3 Implementation

class Solution:
    def minIncrementForUnique(self, nums: List[int]) -> int:
        nums.sort()
        res = 0
        for i in range(1, len(nums)):
            if nums[i] <= nums[i - 1]:
                need = nums[i - 1] + 1
                res += need - nums[i]
                nums[i] = need         # raise this element
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Decrementing elements: only increments are allowed, so a smaller value must always move up.
  • Raising to nums[i-1] rather than nums[i-1] + 1: uniqueness requires strictly greater, not equal.
  • Not sorting: the greedy needs adjacent equal values to be processed in order.
  • Using a counter of used values instead: it works but is slower and more code than the sorted scan.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems