LeetCode Entry

945. Minimum Increment to Make Array Unique

14.06.2024 medium 2024 kotlin rust

Min increments to make items unique

945. Minimum Increment to Make Array Unique medium blog post substack youtube 2024-06-14_06-25_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/639

Problem TLDR

Min increments to make items unique #medium

Intuition

Let’s observe an example.

    // 1 2 2         delta   diff
    //   i           0       1
    //     i         1       0
    //
    // 1 1 2 2 3 7
    //   i           1       0
    //     i         1       1
    //       i       2       0
    //         i     2       1
    //           i   0       4
    //              (2 - (4-1))

First, sort, then maintain the delta:

  • increase if there is a duplicate
  • decrease by adjucent items diff

Approach

Let’s use iterators: windowed, sumOf.

Complexity

  • Time complexity: \(O(nlog(n))\)

  • Space complexity: \(O(1)\), but O(n) for sorted in Kotlin

Code


    fun minIncrementForUnique(nums: IntArray): Int {
        var delta = 0
        return nums.sorted().windowed(2).sumOf { (a, b) ->
            if (a < b) delta = max(0, delta + a - b + 1) else delta++
            delta
        }
    }



    pub fn min_increment_for_unique(mut nums: Vec<i32>) -> i32 {
        nums.sort_unstable(); let mut delta = 0;
        nums[..].windows(2).map(|w| {
            delta = if w[0] < w[1] { 0.max(delta + w[0] - w[1] + 1) } else { delta + 1 };
            delta
        }).sum()
    }