Problem Description
You are given a 0-indexed integer array nums. The array nums is beautiful if:
- nums.length is even.
- nums[i] != nums[i + 1] for all i % 2 == 0.
Note that an empty array is considered beautiful. You can delete any number of elements from nums. When you delete an element, all the elements to the right of the deleted element will be shifted one unit to the left to fill the gap created and all the elements to the left of the deleted element will remain unchanged.
Return the minimum number of elements to delete from nums to make it beautiful.
Key Insights
- The length of the final array must be even.
- Elements at even indices must be distinct from their immediate next elements.
- Deleting duplicates or ensuring distinct elements at required indices is necessary to meet the beauty criteria.
- The problem can be solved in a single pass through the array.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The solution involves iterating through the array while keeping track of the current count of deletions needed. We check every pair of elements to ensure that they meet the beautiful condition. If an element at an even index is the same as the next element, we increment our deletion count. Finally, we ensure that the length of the resulting array is even by adjusting the count if necessary. This approach uses a greedy method with constant space.