Minimum Deletions to Make Array Beautiful

medium stack greedy parity

Problem

An array is beautiful when its length is even and nums[i] != nums[i+1] for every even index i. Deleting an element shifts everything to its right one slot left. Return the minimum number of deletions needed to make nums beautiful (an empty array counts as beautiful).

Inputnums = [1,1,2,3,5]

Output1

Delete one of the leading 1s to get [1,2,3,5], which is beautiful.

Inputnums = [1,1,2,2,3,3]

Output2

Delete nums[0] and a trailing element to leave [1,2,2,3].

nums (comma-separated)

def min_deletions(nums):
    deletions = 0
    stack = []                    # kept elements
    for v in nums:
        if len(stack) % 2 == 1 and stack[-1] == v:
            deletions += 1        # equal pair start, delete v
        else:
            stack.append(v)       # keep v
    if len(stack) % 2 == 1:
        deletions += 1            # drop the lone trailing element
    return deletions

function minDeletions(nums) {
  let deletions = 0;
  const stack = [];                       // kept elements
  for (const v of nums) {
    if (stack.length % 2 === 1 && stack[stack.length - 1] === v) {
      deletions++;                         // equal pair start, delete v
    } else {
      stack.push(v);                       // keep v
    }
  }
  if (stack.length % 2 === 1) deletions++; // drop lone trailing element
  return deletions;
}

int minDeletions(int[] nums) {
    int deletions = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int v : nums) {
        if (stack.size() % 2 == 1 && stack.peekLast() == v) {
            deletions++;                     // equal pair start, delete v
        } else {
            stack.addLast(v);                // keep v
        }
    }
    if (stack.size() % 2 == 1) deletions++;  // drop lone trailing element
    return deletions;
}

int minDeletions(vector<int>& nums) {
    int deletions = 0;
    vector<int> stk;                          // kept elements
    for (int v : nums) {
        if (stk.size() % 2 == 1 && stk.back() == v) {
            deletions++;                       // equal pair start, delete v
        } else {
            stk.push_back(v);                  // keep v
        }
    }
    if (stk.size() % 2 == 1) deletions++;      // drop lone trailing element
    return deletions;
}

Explanation

The result is built as pairs. Reading left to right, a kept element either opens a new pair (it lands at an even position in the result) or closes the pair opened just before it (an odd position).

We scan once and keep a running list of the elements we have decided to keep — think of it as a stack. The parity of the stack's size tells us what role the next element would play: even size means the next element opens a pair, odd size means it must close the open pair.

The only thing that can go wrong is a closing element equal to the opening element of its pair, since a beautiful array forbids nums[i] == nums[i+1] at an even i. When the stack size is odd and the incoming value equals the top of the stack, we cannot place it there, so we delete it (increment the counter) and the pair stays open for the next candidate.

Every other element is kept and pushed. Because each pair must be valid the moment it closes, this greedy choice is optimal — no future element could fix an equal pair, so deleting now is forced and minimal.

After the scan, if the stack has odd size one element is left without a partner. Beautiful arrays have even length, so we delete that lone trailing element too.

Time: O(n) Space: O(n)