Minimum Deletions to Make Array Beautiful - Solution & Explanation

Problem Overview: You receive an integer array and must delete the minimum number of elements so the resulting array becomes beautiful. A beautiful array requires that for every even index i, the condition nums[i] != nums[i+1] holds. After all deletions, the final array length must also be even.

The challenge is that deletions shift indices. Removing an element changes which indices are even, so you cannot simply compare neighbors once and be done. The solution must simulate the resulting array while deciding which elements to keep or discard.

Approach 1: Two-Pointer Technique (Greedy) (Time: O(n), Space: O(1))

This approach scans the array once while tracking the length of the array that would remain after deletions. Think of it as constructing the valid array on the fly. When the current position in the simulated array is even, you must ensure the next kept value differs from the previous element. If two consecutive values are equal at an even position, delete one of them (increment deletion count) and continue scanning. Otherwise, keep the element and extend the valid sequence.

The key insight is that you only care about equality when the constructed index is even. Odd positions have no restriction. After the scan, if the resulting length is odd, delete one more element to ensure the final length is even. This greedy strategy works because keeping the earliest valid pair always preserves maximum flexibility later. This method uses simple iteration over the array and is the optimal interview solution.

Approach 2: Selective Removal and Reposition (Stack-like Construction) (Time: O(n), Space: O(n))

Another way to reason about the problem is to explicitly build the resulting array using a structure similar to a stack or dynamic list. Iterate through the input and append elements to the result unless doing so would violate the beautiful condition. If the current result size is even and the last appended value equals the incoming value, skip the element instead of pushing it. Otherwise append it normally.

This approach makes the constraint easier to visualize because the partially built array always remains valid. The tradeoff is extra memory to store the temporary array. Conceptually this is still a greedy strategy: each decision keeps the earliest valid configuration while minimizing deletions.

Recommended for interviews: The two-pointer greedy solution is the expected answer. It runs in linear time with constant space and demonstrates that you understand how index shifts affect constraints after deletions. Building a temporary array first shows correct reasoning but does not achieve the optimal space complexity.