Minimum Deletions to Make Array Beautiful

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 _theminimum number of elements to delete from _nums to make it beautiful.

Examples

Example 1

Input: nums = [1,1,2,3,4,4]
Output: 2
Explanation: After deleting the first `1` and the last `4`, nums = [1,2,3,4].
It is beautiful because nums.length is even and nums[0] != nums[1], nums[2] != nums[3].

Example 2

Input: nums = [1,1,1,1,1]
Output: 2
Explanation: After deleting any two elements, nums = [1,1,1].
It is beautiful because nums.length is even and nums[0] != nums[1].

Example 3

Input: nums = [1,2,2,3,3,4,4,5]
Output: 2
Explanation: After deleting two elements, nums = [1,2,3,4,5].
It is beautiful because nums.length is even and nums[0] != nums[1], nums[2] != nums[3].

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Solution

Method 1 – Greedy Pairing

Intuition

We want to build the longest beautiful array by greedily pairing elements such that no two adjacent elements are equal at even indices. We iterate through the array, skipping elements that would violate the condition, and ensure the final array has even length.

Approach

1. Initialize a counter for deletions and a variable to track the previous element added to the beautiful array.
2. Iterate through nums:
   • For each element, if the current index is even and the element is equal to the previous, increment deletions and skip adding it.
   • Otherwise, add the element to the beautiful array.
3. If the length of the beautiful array is odd, increment deletions by 1 to make it even.
4. Return the total deletions.

Code

C++

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

Go

func minDeletion(nums []int) int {
    del, n, i := 0, len(nums), 0
    for i < n-1 {
        if nums[i] == nums[i+1] {
            del++
            i++
        } else {
            i += 2
        }
    }
    if (n-del)%2 != 0 { del++ }
    return del
}

Java

class Solution {
    public int minDeletion(int[] nums) {
        int del = 0, n = nums.length, i = 0;
        while (i < n-1) {
            if (nums[i] == nums[i+1]) {
                del++;
                i++;
            } else {
                i += 2;
            }
        }
        if ((n-del)%2 != 0) del++;
        return del;
    }
}

Kotlin

class Solution {
    fun minDeletion(nums: IntArray): Int {
        var del = 0; var i = 0; val n = nums.size
        while (i < n-1) {
            if (nums[i] == nums[i+1]) {
                del++
                i++
            } else {
                i += 2
            }
        }
        if ((n-del)%2 != 0) del++
        return del
    }
}

Python

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

Rust

impl Solution {
    pub fn min_deletion(nums: Vec<i32>) -> i32 {
        let mut del = 0;
        let n = nums.len();
        let mut i = 0;
        while i < n-1 {
            if nums[i] == nums[i+1] {
                del += 1;
                i += 1;
            } else {
                i += 2;
            }
        }
        if (n-del)%2 != 0 { del += 1; }
        del as i32
    }
}

TypeScript

class Solution {
    minDeletion(nums: number[]): number {
        let del = 0, i = 0, n = nums.length;
        while (i < n-1) {
            if (nums[i] === nums[i+1]) {
                del++;
                i++;
            } else {
                i += 2;
            }
        }
        if ((n-del)%2 !== 0) del++;
        return del;
    }
}

Complexity

• ⏰ Time complexity: O(n) where n is the length of nums.
• 🧺 Space complexity: O(1).