Sponsored
This approach involves sorting the array first, and then iterating through it to ensure each element is greater than the previous. By keeping track of the necessary increments for each duplicate, we can ensure that every element in the array becomes unique.
Time Complexity: O(N log N) due to sorting and O(N) for linear traversal, resulting in O(N log N) overall.
Space Complexity: O(1) since no auxiliary space is used beyond input manipulation.
1import java.util.Arrays;
2
3public class Solution {
4 public int minIncrementForUnique(int[] nums) {
5 Arrays.sort(nums);
6 int moves = 0, need = nums[0];
7 for (int num : nums) {
8 moves += Math.max(0, need - num);
9 need = Math.max(need, num) + 1;
10 }
11 return moves;
12 }
13
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] nums = {3, 2, 1, 2, 1, 7};
17 System.out.println(sol.minIncrementForUnique(nums));
18 }
19}This Java solution sorts the input array, then iterates over it to find the minimum number of increments needed to ensure all elements are unique. It calculates necessary increments and maintains the next required unique number during the traversal.
Instead of sorting, this method uses an array to count occurrences of each integer and then processes the count. For duplicate values, increments are calculated to fill gaps until all numbers are unique.
Time Complexity: O(N + M) where M is the range of numbers, due to counting and traversal.
Space Complexity: O(M) where M is the maximum possible number in nums.
1
JavaScript solution employs a counting array to manage the allocation of duplicate numbers into unique positions, aiming to achieve minimal moves with sequential logic over the count array.