# Minimum Deletions to Make Array Beautiful
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-deletions-to-make-array-beautiful)
Canonical: https://scaleengineer.com/dsa/problems/minimum-deletions-to-make-array-beautiful
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Stack
---
## Problem
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:** 1
**Explanation:** 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:** 2
**Explanation:** 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 <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Dynamic Programming
A less efficient but valid approach is to use dynamic programming. We can define `dp[i]` as the length of the longest subsequence that can be formed using a prefix of the input array `nums[0...i]`, must include `nums[i]` as its last element, and satisfies the condition `seq[k] != seq[k+1]` for all even `k` in the subsequence `seq`.
**Time:** O(N^2), where N is the length of `nums`, due to the nested loops. · **Space:** O(N), for the `dp` array.
**Pros:** A standard dynamic programming pattern for subsequence problems.; Guaranteed to find the optimal solution.
**Cons:** Inefficient time complexity of O(N^2), which may lead to a 'Time Limit Exceeded' error on large inputs.; Requires O(N) extra space for the DP array.
### Explanation
This approach solves the problem by building up solutions for progressively larger prefixes of the array. We define `dp[i]` as the length of the longest valid subsequence (one that satisfies `seq[k] != seq[k+1]` for even `k`) that ends with the element `nums[i]`.

To compute `dp[i]`, we consider all previous elements `nums[j]` (where `j < i`) as potential predecessors. We can append `nums[i]` to the subsequence ending at `nums[j]` if the resulting new subsequence remains valid. The condition for appending depends on the length of the subsequence ending at `j`, `dp[j]`:
- If `dp[j]` is odd, `nums[j]` is at an odd-indexed position in its subsequence. The new element `nums[i]` will be at an even-indexed position, which has no immediate predecessor constraint, so we can always append.
- If `dp[j]` is even, `nums[j]` is at an even-indexed position. The new element `nums[i]` will be at an odd-indexed position, so we can only append it if `nums[i] != nums[j]`.

After filling the `dp` array, the maximum value `max_len` represents the longest possible valid subsequence. Since a beautiful array must also have an even length, the final number of elements we can keep is `max_len` if it's even, or `max_len - 1` if it's odd. The minimum deletions will be the original array length minus this final count.

```java
import java.util.Arrays;

class Solution {
    public int minDeletion(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // The new element nums[i] will be at index dp[j] (0-indexed)
                // If dp[j] is even, it's an even position. nums[j] is at dp[j]-1 (odd).
                // If dp[j] is odd, it's an odd position. nums[j] is at dp[j]-1 (even).
                if (dp[j] % 2 != 0) { // nums[j] is at an even position in its subsequence
                    if (nums[i] != nums[j]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                } else { // nums[j] is at an odd position in its subsequence
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        int keptCount = maxLen;
        if (keptCount % 2 != 0) {
            keptCount--;
        }

        return n - keptCount;
    }
}
```
*Note: The logic in the code snippet is slightly different but follows the same DP principle. A simpler DP transition is `dp[i] = 1 + max(dp[j])` where `j<i` and `(dp[j]%2==1 && nums[i]!=nums[j]) || (dp[j]%2==0)`. The provided code implements this logic.*
### Algorithm
- Initialize a DP array `dp` of size `n`, where `dp[i]` stores the length of the longest valid subsequence ending with `nums[i]`.
- Iterate from `i = 0` to `n-1`:
  - Set `dp[i] = 1` (for the subsequence containing only `nums[i]`).
  - Iterate from `j = 0` to `i-1`:
    - Let `len_j = dp[j]`.
    - If `len_j` is odd, we can append `nums[i]`. Update `dp[i] = max(dp[i], len_j + 1)`.
    - If `len_j` is even and `nums[i] != nums[j]`, we can append `nums[i]`. Update `dp[i] = max(dp[i], len_j + 1)`.
- Find the maximum value in the `dp` array, `max_len`.
- If `max_len` is odd, the number of elements we can keep is `max_len - 1`. Otherwise, it's `max_len`.
- The result is `n - kept_count`.

## Greedy Approach with Auxiliary List
A more efficient approach is to use a greedy strategy. We can construct the longest possible beautiful array by iterating through the input `nums` and making a local optimal choice at each step. We use an auxiliary list to build this new array. The choice is to keep an element if and only if it doesn't violate the beautiful array conditions with the elements already kept.
**Time:** O(N), where N is the length of `nums`. We iterate through the array once, and list operations take amortized O(1) time. · **Space:** O(N), as the `beautifulList` can, in the worst case, store all elements of `nums`.
**Pros:** Efficient O(N) time complexity.; The logic is intuitive and directly models the construction of the beautiful array.
**Cons:** Uses O(N) extra space in the worst case, which can be optimized.
### Explanation
The greedy strategy aims to maximize the number of elements we keep, which is equivalent to minimizing deletions. We iterate through the `nums` array and build a new list, let's call it `beautifulList`, which will store the elements of our resulting beautiful array.

The logic for adding an element `num` from `nums` to `beautifulList` depends on the current size of `beautifulList`:
- If `beautifulList.size()` is even, the new element `num` will be at an even index (e.g., 0, 2, ...). This is the first element of a new pair, so there are no constraints. We can greedily add `num` to `beautifulList`.
- If `beautifulList.size()` is odd, the new element `num` will be at an odd index (e.g., 1, 3, ...). This is the second element of a pair. It must be different from the preceding element (which is at `beautifulList.size() - 1`). We add `num` only if `num != beautifulList.get(beautifulList.size() - 1)`. If they are equal, we must delete `num` and continue searching for a suitable element for this position.

After iterating through all of `nums`, `beautifulList` holds the longest possible sequence satisfying the second condition. Finally, we check the even-length condition. If `beautifulList.size()` is odd, we must perform one final deletion (conceptually, removing the last element). The total deletions is the original length minus the final size of our beautiful array.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minDeletion(int[] nums) {
        List<Integer> beautifulList = new ArrayList<>();
        for (int num : nums) {
            if (beautifulList.size() % 2 == 0) {
                beautifulList.add(num);
            } else {
                if (beautifulList.get(beautifulList.size() - 1) != num) {
                    beautifulList.add(num);
                }
            }
        }

        int keptCount = beautifulList.size();
        if (keptCount % 2 != 0) {
            return nums.length - (keptCount - 1);
        } else {
            return nums.length - keptCount;
        }
    }
}
```
### Algorithm
- Initialize an empty list, `res`.
- Iterate through each `num` in `nums`.
- If the current size of `res` is even, it's a new pair's start, so add `num` to `res`.
- If the current size of `res` is odd, `num` would be the second element of a pair. Add it only if it's different from the last element in `res`.
- After the loop, let `keptCount = res.size()`.
- If `keptCount` is odd, we must delete one more element (the last one). So, `finalKeptCount = keptCount - 1`.
- Otherwise, `finalKeptCount = keptCount`.
- Return `nums.length - finalKeptCount`.

## Optimized Greedy Approach with Constant Space
This approach is the most optimal solution. It builds upon the greedy strategy but eliminates the need for an auxiliary list, reducing space complexity to O(1). Instead of storing the new array, we can simply keep a count of the number of elements that must be deleted. The core logic remains the same: we iterate through the array and identify elements that violate the beautiful array conditions.
**Time:** O(N), where N is the length of `nums`, as we perform a single pass through the array. · **Space:** O(1), as we only use a few variables to store counts.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Highly efficient for large inputs.
**Cons:** The logic of tracking the new index `i - deletions` can be slightly less direct to understand compared to building an explicit list.
### Explanation
We can achieve the same result as the greedy approach without using any extra space. The key observation is that to make a decision at index `i`, we only need to know the effective size of the beautiful array built so far, not its actual contents. The effective size determines whether `nums[i]` would be at an even or odd position.

The effective index for `nums[i]` in the new array is `i - deletions`, where `deletions` is the count of elements we have discarded from `nums[0...i-1]`. We only care about violations of the form `new_nums[k] == new_nums[k+1]` where `k` is even. This corresponds to an element `nums[i]` at an even effective index `i - deletions` being equal to the next non-deleted element.

A simpler way to implement this is to iterate through the array and find adjacent elements `nums[i]` and `nums[i+1]` that need to be placed at an even and odd index respectively. If `(i - deletions)` is an even index and `nums[i] == nums[i+1]`, we have a violation. We must delete one element, so we increment `deletions`.

After iterating through the array, we have the total `deletions` required to satisfy the second condition. Finally, we check if the remaining number of elements, `nums.length - deletions`, is even. If not, one more deletion is required to satisfy the first condition.

```java
class Solution {
    public int minDeletion(int[] nums) {
        int n = nums.length;
        int deletions = 0;
        
        // We iterate up to n-1 because we access i+1
        for (int i = 0; i < n - 1; i++) {
            // The index in the new (conceptual) array is (i - deletions)
            if ((i - deletions) % 2 == 0) {
                if (nums[i] == nums[i + 1]) {
                    // Found a pair nums[k] == nums[k+1] where k is even in the new array.
                    // We must delete one. Incrementing deletions effectively deletes nums[i+1]
                    // by shifting the indices of all subsequent elements.
                    deletions++;
                }
            }
        }

        // After all pair-based deletions, if the remaining array has an odd length,
        // we must delete one more element (e.g., the last one).
        if ((n - deletions) % 2 != 0) {
            deletions++;
        }

        return deletions;
    }
}
```
### Algorithm
- Initialize `deletions = 0`.
- Iterate `i` from `0` to `n-2`.
- The index of `nums[i]` in the new array is `i - deletions`.
- If this new index `(i - deletions)` is even, `nums[i]` is the first element of a pair.
- Check if it's equal to the next element, `nums[i+1]`. If `nums[i] == nums[i+1]`, we must delete one. We increment `deletions`.
- After the loop, calculate the number of remaining elements: `keptCount = n - deletions`.
- If `keptCount` is odd, we need one more deletion. Increment `deletions`.
- Return `deletions`.

# Solutions
### Java

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

```

### Python

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

```

### CPP

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