Problem Description

You have an integer array nums that is 0-indexed. The goal is to make this array "beautiful" by deleting the minimum number of elements.

An array is considered beautiful if it meets two conditions:

1. The array has an even number of elements (length is even)
2. For every even index i (where i % 2 == 0), the element at position i must be different from the element at position i + 1

In other words, if you pair up consecutive elements starting from index 0 (like [nums[0], nums[1]], [nums[2], nums[3]], etc.), each pair must contain two different values.

When you delete an element from the array:

• All elements to the right of the deleted element shift one position to the left
• All elements to the left remain in their original positions

An empty array is also considered beautiful by definition.

Your task is to find the minimum number of deletions needed to transform the given array into a beautiful array.

For example, if nums = [1, 1, 2, 3, 5], you would need to delete 1 element to make it beautiful. After deleting one of the 1s, you get [1, 2, 3, 5], which has even length (4) and satisfies the condition that nums[0] ≠ nums[1] and nums[2] ≠ nums[3].

Intuition

Let's think about what makes an array beautiful. We need pairs of elements where each pair has different values. This means we're essentially grouping elements as (element0, element1), (element2, element3), and so on.

The key insight is that we should process the array greedily from left to right, trying to form valid pairs as we go. Why does greedy work here? Because once we form a valid pair, those elements occupy their positions and we can move on to form the next pair.

As we traverse the array, we're essentially in one of two states:

1. Looking for the first element of a pair (at an even position in the final array)
2. Looking for the second element of a pair (at an odd position in the final array)

When we find two consecutive elements that are equal, we know they can't form a valid pair. So we delete one of them (increment our deletion counter) and continue looking. When we find two consecutive elements that are different, they can form a valid pair, so we skip both and move to find the next pair.

The clever part of the solution is that we don't actually need to delete elements from the array. We just simulate the process by:

• Moving index by 1 when we "delete" (this element can't be used, so we skip it)
• Moving index by 2 when we find a valid pair (both elements are used)

After processing all elements, we might end up with an odd number of remaining elements. Since a beautiful array must have even length, we need one more deletion if the final length is odd. This is why we add (n - ans) % 2 at the end - if the remaining elements form an odd-length array, we need to delete one more element.

Learn more about Stack and Greedy patterns.

Solution Approach

The solution uses a greedy algorithm that simulates the pairing process without actually modifying the array.

We initialize two variables:

• i: current index for traversing the array
• ans: count of elements to delete

The main algorithm works as follows:

1. Traverse the array with a while loop (while i < n - 1):

   • We stop at n - 1 because we always check pairs of consecutive elements

2. Check consecutive elements (nums[i] == nums[i + 1]):

   • If they are equal: These two elements cannot form a valid pair in a beautiful array. We "delete" the second element by:
     • Incrementing ans by 1 (counting this deletion)
     • Moving i forward by 1 (the first element might pair with the next element)
   • If they are different: These two elements can form a valid pair. We:
     • Move i forward by 2 (skip both elements as they form a valid pair)

3. Handle odd-length result (ans += (n - ans) % 2):

   • After processing, n - ans gives us the number of remaining elements
   • If this number is odd, we need one more deletion to make the array length even
   • (n - ans) % 2 equals 1 if odd, 0 if even

Let's trace through an example with nums = [1, 1, 2, 2, 3, 3]:

• i = 0: nums[0] = 1, nums[1] = 1 (equal) → delete one, ans = 1, i = 1
• i = 1: nums[1] = 1, nums[2] = 2 (different) → valid pair, i = 3
• i = 3: nums[3] = 2, nums[4] = 3 (different) → valid pair, i = 5
• Loop ends
• Remaining elements: 6 - 1 = 5 (odd) → need one more deletion, ans = 2

The algorithm efficiently finds the minimum deletions in O(n) time with O(1) space complexity.

Example Walkthrough

Let's walk through the solution with nums = [4, 2, 4, 2, 1, 1].

Initial state:

• Array: [4, 2, 4, 2, 1, 1]
• i = 0, ans = 0 (no deletions yet)
• Array length n = 6

Step 1: Check positions 0 and 1

• nums[0] = 4, nums[1] = 2
• They are different → can form a valid pair
• Skip both elements: i = 2
• Deletions: ans = 0

Step 2: Check positions 2 and 3

• nums[2] = 4, nums[3] = 2
• They are different → can form a valid pair
• Skip both elements: i = 4
• Deletions: ans = 0

Step 3: Check positions 4 and 5

• nums[4] = 1, nums[5] = 1
• They are equal → cannot form a valid pair
• Delete one element: ans = 1
• Move to next element: i = 5

Step 4: Exit loop

• i = 5 is not less than n - 1 = 5, so we exit the while loop

Step 5: Check if remaining array has even length

• Remaining elements: n - ans = 6 - 1 = 5
• 5 is odd, so we need one more deletion
• ans = ans + (5 % 2) = 1 + 1 = 2

Final answer: 2 deletions needed

The resulting beautiful array would be [4, 2, 4, 2] (after deleting both 1s), which has:

• Even length (4 elements)
• nums[0] = 4 ≠ nums[1] = 2 ✓
• nums[2] = 4 ≠ nums[3] = 2 ✓

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm uses a single while loop that traverses through the array once. In each iteration, the index i advances by either 1 (when nums[i] == nums[i + 1]) or 2 (when nums[i] != nums[i + 1]). Since the loop continues while i < n - 1, each element is visited at most once, resulting in linear time complexity.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables n, i, and ans, regardless of the input size. No additional data structures are created that scale with the input, making the space usage constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Index Tracking Logic

The Pitfall: Many developers mistakenly think the index variable represents the actual index in the modified array after deletions. This leads to confusion about why we increment index by 1 when we find equal elements.

Why it happens: The variable name index suggests it's tracking positions in the final array, but it's actually tracking positions in the original array while simulating the pairing process.

The Fix: Rename the variable to better reflect its purpose and add clear comments:

def minDeletion(self, nums: List[int]) -> int:
    n = len(nums)
    original_pos = 0  # Position in the ORIGINAL array
    deletions = 0
    virtual_pos = 0    # Track position in the virtual "result" array
  
    while original_pos < n - 1:
        # Check if this element would be at an even position in result
        if (virtual_pos % 2 == 0):
            if nums[original_pos] == nums[original_pos + 1]:
                # Delete current element, don't increment virtual position
                deletions += 1
                original_pos += 1
            else:
                # Valid pair found
                original_pos += 2
                virtual_pos += 2
        else:
            original_pos += 1
            virtual_pos += 1
  
    # Check if result has even length
    deletions += (n - deletions) % 2
    return deletions

2. Forgetting the Final Even-Length Check

The Pitfall: Developers often forget the line deletions += (n - deletions) % 2, assuming that the main loop handles everything.

Example of the bug:

# WRONG: Missing the final check
def minDeletion(self, nums: List[int]) -> int:
    n = len(nums)
    index = 0
    deletions = 0
  
    while index < n - 1:
        if nums[index] == nums[index + 1]:
            deletions += 1
            index += 1
        else:
            index += 2
  
    return deletions  # Bug: doesn't ensure even length!

For input [1, 2, 3], this would return 0, but the correct answer is 1 (we need to delete one element to make the length even).

3. Off-by-One Error in Loop Condition

The Pitfall: Using while index < n instead of while index < n - 1, causing an index out of bounds error when checking nums[index + 1].

The Fix: Always ensure the loop condition prevents accessing nums[index + 1] when index is at the last position:

# Correct loop condition
while index < n - 1:  # Ensures nums[index + 1] is valid
    if nums[index] == nums[index + 1]:
        # ...

4. Incorrectly Simulating the Deletion Process

The Pitfall: Some developers try to actually modify the array or create a new array to track deletions, which complicates the logic and increases space complexity:

# INEFFICIENT AND ERROR-PRONE
def minDeletion(self, nums: List[int]) -> int:
    result = []
    deletions = 0
  
    for num in nums:
        if len(result) % 2 == 0:
            result.append(num)
        elif result[-1] != num:
            result.append(num)
        else:
            deletions += 1
  
    if len(result) % 2 == 1:
        deletions += 1
  
    return deletions

This approach is harder to debug and understand compared to the greedy simulation approach.