2779.maximum-beauty-of-an-array-after-applying-operation.md

2779. Maximum Beauty of an Array After Applying Operation

Test Cases

Edge / Corner Cases

• Single element: [1].
• All elements are the same: [1, 1, 1, 1].
• Huge gap between elements: [1, 1000000000].

Breakdowns

1. How to find the longest subsequence (not subarray) that consists of the same elements?

nums = [1, 2, 3, 2, 3, 2]
        |                   // For 1   
           |-----------|    // For 2
              |-----|       // For 3

2. If the array is sorted, the answer is?

nums = [1, 2, 2, 2, 3, 3]
        |                   // For 1
           |-----|          // For 2
                    |--|    // For 3
        

We can use a sliding window or the same approach as above.

3. If the array is sorted, and we can change the element in the range [nums[i] - k..nums[i] + k], the answer is?

This is the solution to the problem, see below.

Prework + Key Insights

The problem is to find the maximum length of the longest subsequence consisting of equal elements. We can modify the elements to make them to be equal, the order of the elements doesn't matter. [3, 1] could be changed to [3, 3] or [1, 1], the same result of [1, 3]. We can sort the array so that the closer (equal) elements can be grouped together easily. We can have a window size 2 * k (<--k--|--k-->) to find the longest subarray.

Idea 1: Longest subsequence -> Sort -> Longest subarray.

After sorting the array, how can we decide if the two adjacent numbers can be changed to be equal?

Idea 2: If the diff(A, B) <= 2 * k, then we can change the two numbers to be equal.

|--|--|--|--|--|--|
A           B
 ------>
     <------   
      X // The equal number can be changed to be equal

// diff(A, B) > 2 * k, it's impossible to make the two numbers to be equal.
|--|--|--|--|--|--|
A                 B
 ------>   <------

Binary Search

We iterate all the elements and search its upper bound (2 * k) that the input array can cover. The maximum length of the subarray is the answer.

k = 2
1, 1, 2, 3, 3, 5, 6, 6, 7, 9
^                 * // Upper bound of 1 + 2 * k     
|--------------|    // 1 and 5 can be changed to be equal with k = 2, [1, 5] => [3, 3]
         ^                 *
         |--------------|

fun maximumBeauty(nums: IntArray, k: Int): Int {
    nums.sort()
    var ans = 0
    for (i in nums.indices) {
        val upperBound = binarySearch(nums, nums[i] + 2 * k)
        ans = maxOf(ans, upperBound - i)
    }   
    return ans
}

// Find the first element that condition: "A[i] > target" (the current implementation)
// Or
// We can find the last element that condition: "A[i] <= target"
private fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        val meet = nums[middle] > target
        if (meet) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

• Time Complexity: O(n log n) for sorting and binary search.
• Space Complexity: O(log n) for sorting.

Sliding Window

The two numbers can be changed to be equal if diff(A, B) <= 2 * k from above: It's impossible to make the two numbers to be equal if diff(A, B) > 2 * k. To find the maximum length of the subarray, we can use a sliding window in sorted array.

• Window: The number in this window can be changed to be equal, that is the the maximum difference of the two numbers in the window is <= 2 * k.
• We expand the window until the condition is broken the condition. Then we shrink the window from the left until the condition is satisfied.

k = 2
[1, 3, 25, 26, 27, 28, 100, 1010]
    R    
 L // 3 - 1 <= 2 * 2, valid

[1, 3, 25, 26, 27, 28, 100, 1010]
        R
 L          // 25 - 1 > 2 * 2, invalid, shrink the window
    L       // 25 - 3 > 2 * 2, invalid, shrink the window
        L   // 25 - 25 <= 2 * 2, valid

[1, 3, 25, 26, 27, 28, 100, 1010]
                    R
        L   // ans = 4 (final answer)

[1, 3, 25, 26, 27, 28, 100, 1010]
                       R
        L                   // 100 - 25 > 2 * 2, invalid, shrink the window
            L               // 100 - 26 > 2 * 2, invalid, shrink the window
                L           // 100 - 27 > 2 * 2, invalid, shrink the window
                    L       // 100 - 28 > 2 * 2, invalid, shrink the window
                        L   // 100 - 100 <= 2 * 2, valid

fun maximumBeauty(nums: IntArray, k: Int): Int {
    nums.sort()
    var left = 0
    var ans = 0
    var maxCount = 0
    for (right in nums.indices) {
        // Shrinking the window when breakding the condition: diff(A, B) <= 2 * k
        while (nums[right] - nums[left] > 2 * k) {
            left++
        }
        ans = maxOf(ans, right - left + 1)
    }
    return ans
}

• Time Complexity: O(n log n) for sorting.
• Space Complexity: O(log n) for sorting.

Line Sweep

We can use line sweep algorithm to solve this problem, for each element A[i], we can create a interval of [A[i] - k, A[i] + k], we can make the two numbers to be equal if the two intervals overlap. So we want to find the maximum number of overlapping intervals at any given time.

[3, 4, 5, 7] k = 2

1, 2, 3, 4, 5, 6, 7, 8, 9
|-----*-----|
   |-----*-----|
      |-----*-----|
            |-----*-----|
            ^
// Calculate the difference array
1, 2, 3, 4, 5, 6, 7, 8, 9, 10   // index
1  0  0  0  0 -1  0  0  0  0    // [3 - k, 3 + k] = [1, 5]
1  1  0  0  0 -1 -1  0  0  0    // [4 - k, 4 + k] = [2, 6]
1  1  1  0  0 -1 -1 -1  0  0    // [5 - k, 5 + k] = [3, 7]
1  1  1  0  1 -1 -1 -1  0 -1    // [7 - k, 7 + k] = [5, 9]

// Prefix sum of differnce array
1  2  3  3  4  3  2  1  1  0 
            ^ // The maximum overlap

fun maximumBeauty(nums: IntArray, k: Int): Int {
    val min = nums.minOf { it } - k
    val max = nums.maxOf { it } + k
    val diff = IntArray(max - min + 2)

    for (num in nums) {
        diff[num - k - min]++
        diff[num + k + 1 - min]--
    }
    var value = 0
    var maxOverlap = 0
    for (i in diff.indices) {
        value += diff[i]
        maxOverlap = maxOf(maxOverlap, value)
    }
    return maxOverlap
}

• Time Complexity: O(n + r), where n is the length of the array nums, where r is the range of the elements.
• Space Complexity: O(r).