Code Implementation

class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        count = 0
        i = 0
        n = len(nums)
        while i < n - 1:
            if (i - count) % 2 == 0 and nums[i] == nums[i+1]:
                count += 1
                i += 1
            else:
                i += 1
        if (n - count) % 2 == 1:
            count += 1
        return count
      

class Solution {
public:
    int minDeletion(vector<int>& nums) {
        int count = 0;
        int n = nums.size();
        int i = 0;
        while (i < n - 1) {
            if ((i - count) % 2 == 0 && nums[i] == nums[i + 1]) {
                count++;
                i++;
            } else {
                i++;
            }
        }
        if ((n - count) % 2 == 1) {
            count++;
        }
        return count;
    }
};
      

class Solution {
    public int minDeletion(int[] nums) {
        int count = 0;
        int n = nums.length;
        int i = 0;
        while (i < n - 1) {
            if ((i - count) % 2 == 0 && nums[i] == nums[i + 1]) {
                count++;
                i++;
            } else {
                i++;
            }
        }
        if ((n - count) % 2 == 1) {
            count++;
        }
        return count;
    }
}
      

var minDeletion = function(nums) {
    let count = 0;
    let n = nums.length;
    let i = 0;
    while (i < n - 1) {
        if ((i - count) % 2 === 0 && nums[i] === nums[i + 1]) {
            count++;
            i++;
        } else {
            i++;
        }
    }
    if ((n - count) % 2 === 1) {
        count++;
    }
    return count;
};
      

Problem Description

You are given an array of integers called nums. Your task is to make the array beautiful by deleting the minimum number of elements. An array is considered beautiful if:

• For every even index i (0-based), nums[i] != nums[i + 1] (if i + 1 is within bounds).
• The length of the resulting array is even.

Return the minimum number of deletions required to make the array beautiful. You may delete any elements, but you cannot reorder or reuse elements.

Constraints:

• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁹

Thought Process

At first glance, one might consider brute-force: try all possible deletions and check if the resulting array is beautiful. However, this is computationally infeasible for large arrays due to the exponential number of possibilities.

Instead, we observe that we only need to ensure that for every even index, the current element is different from the next one, and the final length is even. This suggests a greedy, linear approach: iterate through the array and whenever we find a pair at even index where nums[i] == nums[i+1], we must delete one of them to avoid violating the condition.

After this process, if the resulting array has odd length, we need to remove one more element to make the length even. This can be done by incrementing our deletion count by one.

The key insight is to count deletions as we traverse, adjusting our even/odd index tracking based on how many deletions have occurred so far.

Solution Approach

• Initialize a counter count to track the number of deletions.
• Iterate through the array using an index i from 0 to n - 1 (where n is the length of nums).
• For each index:
  • Calculate the "current" index in the beautiful array as i - count.
  • If this "current" index is even and nums[i] == nums[i+1], increment count (since we need to delete one to avoid having equal elements at even index).
  • Otherwise, move to the next index.
• After the loop, check if the final length (n - count) is odd. If so, increment count by 1 to ensure the final array is even-length.
• Return count as the minimum number of deletions required.

This approach is efficient because it processes the array in a single pass and only considers necessary deletions.

Example Walkthrough

Let's consider the input nums = [1, 1, 2, 3, 5].

1. Start with count = 0, i = 0.
2. i - count = 0 (even). nums[0] == nums[1] (1 == 1), so delete one. count = 1, move i to 1.
3. i = 1, i - count = 0 (even). nums[1] == nums[2] (1 != 2), no deletion. Move i to 2.
4. i = 2, i - count = 1 (odd). No check needed, move i to 3.
5. i = 3, i - count = 2 (even). nums[3] == nums[4] (3 != 5), no deletion. Move i to 4.
6. Loop ends. Final length is 5 - 1 = 4 (even), so no extra deletion needed.
7. Return 1.

Thus, only one deletion is required to make the array beautiful.

Time and Space Complexity

• Brute-force approach:
  • Would involve generating all possible subsequences and checking each, leading to O(2ⁿ) time complexity, which is infeasible for large arrays.
• Optimized approach (as above):
  • Time Complexity: O(n), since we traverse the array once.
  • Space Complexity: O(1), as only a few variables are used regardless of input size.

The optimized solution is highly efficient and suitable for large inputs.

Summary

To make the array beautiful, we need to ensure that for every even index, the current and next elements are different, and the final array length is even. A greedy, single-pass approach that counts necessary deletions as we traverse the array leads to an elegant and efficient solution. The key insight is to adjust our index tracking based on how many deletions have occurred, ensuring both conditions are met with minimal effort.