#2216

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Minimum Deletions to Make Array Beautiful

Determine the minimum deletions required to transform an array into a beautiful sequence using stack-based state management.

array stack greedy

Problem Statement

You are given a 0-indexed integer array nums. An array is considered beautiful if no two consecutive elements at even and odd indices are equal. You can delete elements to achieve this property.

Each deletion shifts elements to the left, leaving preceding elements unchanged. Determine the minimum number of deletions needed to make nums beautiful, considering all necessary adjustments for adjacent duplicates and array shifting.

Examples

Example 1

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

Output: 1

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

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

Solution Approach

Use a Stack to Track Beautiful State

Iterate through nums and push elements onto a stack while ensuring the beautiful property holds. If the current element violates the even-odd consecutive rule, count it as a deletion rather than pushing it.

Greedy Deletion of Adjacent Duplicates

Always delete the minimum number of elements required to restore the beautiful property when consecutive duplicates occur. This reduces unnecessary operations and guarantees minimal deletions.

Finalize with Parity Adjustment

After processing, check if the resulting stack length is even. If not, delete the last element to maintain the array's beautiful structure. This ensures the final array meets the problem's constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each element is processed once and stack operations are O(1). Space complexity is O(n) for the stack in the worst case when no deletions occur.

What Interviewers Usually Probe

Check for repeated adjacent elements violating even-odd indices.
Consider greedy deletions to maintain minimal operations.
Ask about edge cases with single-element or already beautiful arrays.

Common Pitfalls or Variants

Common pitfalls

Forgetting to adjust the last element for even-length requirement.
Deleting elements without checking parity, causing unnecessary removals.
Assuming empty arrays need deletions when they are already beautiful.

Follow-up variants

Compute minimum insertions to make array beautiful instead of deletions.
Apply similar stack-based approach to linked lists with consecutive duplicate constraints.
Modify problem to require alternating increases and decreases rather than duplicates.

FAQ

What is a beautiful array in this problem?

A beautiful array has no two consecutive elements at even and odd indices equal, and an empty array is considered beautiful.

How does the stack-based pattern apply here?

The stack tracks the current beautiful state and helps decide which elements must be deleted when violations occur.

Can I solve this without a stack?

Yes, but a stack simplifies tracking even-odd positions and required deletions, making the approach clearer and efficient.

What is the minimum deletions for nums = [1,1,2,3,5]?

Deleting one of the initial 1s results in [1,2,3,5], which is beautiful, so the minimum deletions is 1.

Does the problem allow multiple consecutive deletions?

Yes, you can delete any number of elements, but the goal is to minimize deletions while maintaining the beautiful property.

terminal

Solution

Solution 1: Greedy

According to the problem description, we know that a beautiful array has an even number of elements, and if we divide every two adjacent elements in this array into a group, then the two elements in each group are not equal. This means that the elements within a group cannot be repeated, but the elements between groups can be repeated.

1

2

3

4

5

6

7

8

9

10

11

12

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#1996 the number of weak characters in the game #2589 minimum time to complete all tasks #1673 find the most competitive subsequence