D
DevExCode

LeetCode 945: Minimum Increment to Make Array Unique Solution

Master LeetCode problem 945 (Minimum Increment to Make Array Unique), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

945. Minimum Increment to Make Array Unique

Medium
ArrayGreedySortingCounting

Problem Explanation

Explanation:

To make every value in the array unique, we can iterate through the array and keep track of the current maximum value encountered so far. For each element in the array, if it is less than or equal to the current maximum value, we need to increment it to be greater than the current maximum value. The minimum number of moves required is equal to the total number of increments made.

Algorithm:

  1. Sort the array nums.
  2. Initialize a variable moves to 0 and maxVal to -1.
  3. Iterate through the sorted array:
    • If the current element is less than or equal to maxVal, increment it to be maxVal + 1 and add the difference to moves.
    • Update maxVal to be the maximum of the current element and maxVal.
  4. Return moves.

Time Complexity: O(nlogn) - Sorting the array Space Complexity: O(1) - Constant space is used

:

Solution Code

class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        int maxVal = -1;
        
        for (int num : nums) {
            if (num <= maxVal) {
                moves += maxVal - num + 1;
                maxVal++;
            } else {
                maxVal = num;
            }
        }
        
        return moves;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 945 (Minimum Increment to Make Array Unique)?

This page provides optimized solutions for LeetCode problem 945 (Minimum Increment to Make Array Unique) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 945 (Minimum Increment to Make Array Unique)?

The time complexity for LeetCode 945 (Minimum Increment to Make Array Unique) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 945 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 945 in Java, C++, or Python.

Back to LeetCode Solutions