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.*

**Example 1:**

Input:nums = [1,1,2,3,5]Output:1Explanation:You can delete either`nums[0]`

or`nums[1]`

to make`nums`

= [1,2,3,5] which is beautiful. It can be proven you need at least 1 deletion to make`nums`

beautiful.

**Example 2:**

Input:nums = [1,1,2,2,3,3]Output:2Explanation:You can delete`nums[0]`

and`nums[5]`

to make nums = [1,2,2,3] which is beautiful. It can be proven you need at least 2 deletions to make nums beautiful.

**Constraints:**

`1 <= nums.length <= 10`

^{5}`0 <= nums[i] <= 10`

^{5}

**Solution: Greedy + Two Pointers**

If two consecutive numbers are the same, we must remove one. We don’t need to actually remove elements from array, just need to track how many elements have been removed so far.

i is the position in the original array, ans is the number of elements been removed. i – ans is the position in the updated array.

ans += nums[i – ans] == nums[i – ans + 1]

Remove the last element (just increase answer by 1) if the length of the new array is odd.

Time complexity: O(n)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int minDeletion(vector<int>& nums) { const int n = nums.size(); int ans = 0; for (int i = 0; i - ans + 1 < n; i += 2) ans += nums[i - ans] == nums[i - ans + 1]; ans += (n - ans) & 1; return ans; } }; |