LeetCode 2216 - Minimum Deletions to Make Array Beautiful

LeetCode Problem 2216

Difficulty: 🟡 Medium
Topics: Array, Stack, Greedy

Solution

Problem Understanding

The problem asks us to transform a given integer array nums into a beautiful array using the minimum number of deletions. A beautiful array satisfies two conditions: its length is even, and no two consecutive elements at even indices are equal (nums[i] != nums[i + 1] for all i % 2 == 0). Deletions are performed such that elements to the right shift left, and elements to the left remain unchanged.

The input is a list of integers, with up to 10^5 elements, each ranging from 0 to 10^5. The expected output is a single integer representing the minimum number of deletions required to achieve a beautiful array. An empty array is trivially considered beautiful.

Key edge cases include arrays that are already beautiful, arrays with repeated consecutive elements, and arrays of length 1 (which require deletion to become even-length). The problem guarantees that the array is non-empty, but we must handle small arrays carefully.

Approaches

A brute-force approach would attempt to generate all subsequences of the array and check if each is beautiful. This is correct but computationally infeasible, as the number of subsequences grows exponentially with array length, resulting in O(2^n) time complexity.

The key insight for an optimal approach is that we only need to check adjacent pairs of elements at even indices. By maintaining a "virtual" length while iterating through the array and only appending elements that do not violate the beautiful condition, we can greedily count how many elements need to be removed. After processing, we also need to ensure the final array has an even length, potentially deleting the last element if necessary.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generates all subsequences and checks each for beauty
Optimal	O(n)	O(1)	Greedy traversal, counting deletions based on adjacent duplicates and final length parity

Algorithm Walkthrough

1. Initialize a variable deletions to 0 to count the number of elements removed.
2. Initialize a variable length to 0 representing the length of the "virtual" beautiful array being built.
3. Iterate through each element num in nums.
4. For each element, check if it violates the beautiful property: if the current length is even and num equals the last appended element in the virtual array, increment deletions and skip appending.
5. Otherwise, increment length to include num in the virtual array.
6. After iterating through all elements, check if length is odd. If so, increment deletions to remove the last element to ensure even length.
7. Return deletions as the minimum number of deletions required.

Why it works: By processing the array in a single pass and ensuring that no even-indexed pair violates the beautiful condition, we greedily maintain a valid array. The final adjustment for even length ensures completeness, guaranteeing the minimum deletions.

Python Solution

from typing import List

class Solution:
    def minDeletion(self, nums: List[int]) -> int:
        deletions = 0
        length = 0  # length of the virtual beautiful array
        
        for num in nums:
            if length % 2 == 0 and length > 0 and nums[length - deletions - 1] == num:
                deletions += 1
            else:
                length += 1
        
        if length % 2 == 1:
            deletions += 1
        
        return deletions

The implementation uses a single pass through nums, maintaining the virtual array length with length and incrementing deletions whenever an element would violate the beautiful property. The final parity check ensures the resulting array has even length.

Go Solution

func minDeletion(nums []int) int {
    deletions := 0
    length := 0

    for _, num := range nums {
        if length%2 == 0 && length > 0 && nums[length-deletions-1] == num {
            deletions++
        } else {
            length++
        }
    }

    if length%2 == 1 {
        deletions++
    }

    return deletions
}

The Go solution mirrors the Python version. Slices in Go allow direct indexing. The length-deletions-1 calculation ensures we compare the current element with the last element in the virtual array, similar to Python.

Worked Examples

Example 1: nums = [1,1,2,3,5]

Step	num	length	deletions	Notes
1	1	1	0	Append first element
2	1	1	1	Duplicate at even index, delete
3	2	2	1	Append
4	3	3	1	Append
5	5	4	1	Append

Final length is even, so no extra deletion. Result: 1.

Example 2: nums = [1,1,2,2,3,3]

Step	num	length	deletions	Notes
1	1	1	0	Append
2	1	1	1	Delete duplicate
3	2	2	1	Append
4	2	2	2	Delete duplicate
5	3	3	2	Append
6	3	3	3	Delete duplicate

Final length is odd, add one more deletion to make even. Result: 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Only counters deletions and length are used

Since we only traverse the array once and use constant extra space, this is optimal for the input constraints.

Test Cases

# Provided examples
assert Solution().minDeletion([1,1,2,3,5]) == 1  # minimal deletion to make beautiful
assert Solution().minDeletion([1,1,2,2,3,3]) == 2  # two deletions required

# Edge cases
assert Solution().minDeletion([1]) == 1  # length 1, must delete to be even
assert Solution().minDeletion([1,2]) == 0  # already beautiful
assert Solution().minDeletion([1,1,1,1]) == 2  # repeated duplicates
assert Solution().minDeletion([]) == 0  # empty array is beautiful

# Large array
assert Solution().minDeletion([i % 2 for i in range(100000)]) == 0  # alternating pattern

Test	Why
[1,1,2,3,5]	minimal deletion to fix duplicate at even index
[1,1,2,2,3,3]	multiple deletions needed across array
[1]	single-element edge case
[1,2]	already beautiful
[1,1,1,1]	repeated duplicates
[]	empty array case
large alternating array	tests algorithm efficiency on upper-bound

Edge Cases

One important edge case is a single-element array. Since the beautiful array must have even length, any single-element array requires deletion. The implementation handles this with the final parity check.

Another edge case is an array with alternating duplicates, such as [1,1,2,2,3,3,...]. These require deletions at multiple points; the greedy approach ensures we only delete when necessary without over-deleting.

A third edge case is an already beautiful array of even length. The algorithm correctly skips all elements and does not increment deletions, preserving the minimal deletion property.