Minimum Deletions to Make Array Beautiful

Problem Description

Ah, the classic dilemma of making arrays beautiful! The problem at hand is to ensure that no two adjacent elements in an array are the same. If they are, we need to perform some deletions. Imagine you’re at a party, and you see two people wearing the same outfit. Awkward! In the world of arrays, we can’t just ignore it; we have to delete elements to make it beautiful.

Code Solution


class Solution {
  public int minDeletion(int[] nums) {
    int ans = 0;

    for (int i = 0; i + 1 < nums.length; ++i)
      if (nums[i] == nums[i + 1] && (i - ans) % 2 == 0)
        ++ans;

    return ans + (((nums.length - ans) & 1) == 1 ? 1 : 0);
  }
}

Approach

The approach here is straightforward. We iterate through the array and check for adjacent elements. If they are the same and the index (after accounting for deletions) is even, we increment our deletion count. Finally, we check if the remaining elements are odd, in which case we need to delete one more element to maintain the beauty of the array.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

Real-World Example

Let’s say you’re organizing a family reunion, and you have a list of attendees. If Uncle Bob and Aunt Betty show up wearing the same Hawaiian shirt, you might have to ask one of them to change. In array terms, that’s a deletion! The goal is to ensure that everyone stands out in their unique outfits, just like we want unique elements in our array.