3397.maximum-number-of-distinct-elements-after-operations.md

3397. Maximum Number of Distinct Elements After Operations

Greedy

Symbols: We use A to represent the previous number nums[i - 1] and B to represent the current number nums[i]. And A', B' to represent the modified number.

Greedy Idea!! We want to make previous number as small as possible so that the current number has more space to move to make it unique.

For every B, it can move in the range of [B - k..B + k]. We want to make B as small as possible, so we can set B to

• A + 1 if A + 1 <= B - k (A + 1 is within the range of [B - k..B + k]):

----A, A+1---------B, ...
        |----------|
 |-----------------|  
        B' = A + 1

• Otherwise, we can set B to B - k.

----A, A+1---------B, ...
             |--k--|
             B' = B - k

And we have to ensure that B' is in the range of [B - k..B + k]. So the final result is B' = min(max(A' + 1, B - k), B + k).

• 貪心思維：对于 nums[i] 来说要变得尽量小，这样 nums[i+1] 才有更好的操作空间使 nums[i+1] != nums[i]
• 要讓數字都不同，我們要盡量製造出空間，所以最左邊的數字要盡量往最左邊移動，後面的數字可以盡可能緊接著前面的數字排 (B' = A' + 1)，以此類推。但是要考慮到 k 的限制，如果 A' + 1 不在範圍內，那麼隔壁數字最多只能到 B - k，兩者我們取最大值。然而 B' 也不能超過 B + k，所以我們要取最小值。

// B 遠大於 A，超過 `k` 的範圍，所以 B' 只能 B - k
----A, A+1-------------B, ...
               |---k---|

fun maxDistinctElements(nums: IntArray, k: Int): Int {
    var count = 1
    val n = nums.size
    nums.sort()
    nums[0] = nums.first() - k
    for (i in 1 until n) {
        nums[i] = minOf(
            maxOf(nums[i - 1] + 1, nums[i] - k),
            nums[i] + k
        )
        if (nums[i - 1] != nums[i]) count++
    }
    return count
}

Greedy (My AC Solution)

If k == 0, we can simply count the distinct elements and return the answer directly.

Next, we can handle when k is non-zero which we have ability to add or subtract k from any element. To maximize the number of distinct elements, we should try to maximize the possible range of the array. We can set the smallest number as low as possible and the largest number as high as possible.

Then we iterate the array and modify the elements based on the difference between the current element (B) and the previous (A) element. We want to set the element as low as possible.

We can consider the following cases after the modification (nums[i - 1] should <= nums[i], but we can modify the element, so it's possible that nums[i - 1] >= nums[i] after modification):

• nums[i-1] < nums[i]:

diff = B - A

// diff < k: We can touch A, and set B' = A + 1
----A--B----
 |--k--|

// diff == k: We can touch A, and set B' = A + 1
--A-----B----
  |--k--|

// diff > k: We can touch A, and set B' = B - k
--A--------B----
     |--k--|
     B' = B - k

• nums[i-1] == nums[i]: To make the element distinct, we can set nums[i] = nums[i-1] + 1.

• nums[i-1] > nums[i]:

diff = A - B

// diff < k: We can touch A, and set B' = A + 1
--B--A----
  |--k--|

// diff == k: It's impossible to make B' > A, we discard B by setting B' = A (Let it duplicate)
--B-----A----
  |--k--|
        B'

// diff > k: We can NOT touch A, because B' = B + K is still < A after modification, and we want to set B as low as possible, so we stay at B.
--B--------A----
  |--k--| 
  B'

Finally, we can count the number of distinct elements in the array and return the answer.

fun maxDistinctElements(nums: IntArray, k: Int): Int {
    if (k > 0) {
        nums.sort()
        nums[0] = nums[0] - k
        for (i in 1 until nums.size) {
            val previous = nums[i - 1]  // A
            val current = nums[i]       // B
            if (previous < current) {
                val diff = current - previous
                if (diff < k) {
                    /**
                    ----A--B----
                     |--k--|
                    */
                    nums[i] = previous + 1
                } else if (diff == k) {
                    /**
                    --A-----B----
                      |--k--|
                    */
                    nums[i] = previous + 1
                } else if (diff > k) {
                    /**
                    --A--------B----
                         |--k--|
                         B'
                    */
                    nums[i] = nums[i] - k
                }
            } else if (previous == current) {
                nums[i] = previous + 1
            } else if (previous > current) {
                val diff = previous - current
                if (diff < k) {
                    /**
                    ----B--A----
                        |--k--|
                    */
                    nums[i] = previous + 1
                } else if (diff == k) {
                    /**
                    --B-----A----
                      |--k--|
                            B'
                    */
                    nums[i] = previous
                } else if (diff > k) {
                    /**
                    --B--------A----
                      |--k--|
                      B' We want to set B as low as possible, so we stay at B.
                    */
                    nums[i] = nums[i]
                }
            }
        }
    }
    val count = HashMap<Int, Int>()
    for (num in nums) {
        count[num] = (count[num] ?: 0) + 1
    }
    return count.keys.size
}