Minimum Deletions To Make Array Beautiful - Leetcode Solution

Problem Statement:

You are given an array nums that consists of non-negative integers. Let us define a beautiful arrangement as an array that is sorted in non-decreasing order and no two adjacent integers are equal.

For example, nums = [1,3,2,2,1,2]. One possible beautiful arrangement is [1,2,3,1,2,2], but another beautiful arrangement is [1,2,1,2,2,3]. It can be proven that the latter arrangement is more beautiful than the former.

Return the minimum possible number of deletions to make nums beautiful.

Solution Approach:

The first step that we need to take for solving this problem is to sort the given array nums in non-decreasing order. Why do we need to do this? We want to find the minimum number of deletions we need to make to obtain a beautiful array. A beautiful array is defined as an array that is sorted in non-decreasing order and no two adjacent integers are equal. Thus, we can assume that the given array will be sorted in non-decreasing order and then start processing it.

Once the given array is sorted, we can start iterating through it and count the number of deletions that we need to make to obtain a beautiful array. We can keep a count of the number of deletions that we have made so far (let's call it deletionsCount).

Let's take an example to illustrate the approach. Consider an array nums = [1,3,2,2,1,2]. After sorting this array, we get nums = [1,1,2,2,2,3]. Now, we can start iterating through the sorted array. The first element in the array is 1. Since no two adjacent elements are equal in a beautiful array, we can move to the next element (which is also 1). Now, we have two adjacent elements that are equal. We need to delete one of these elements to obtain a beautiful array. We can delete the second element (since it is adjacent to the first element that we have kept). We can increment our deletionsCount by 1 and move to the next element in the array (which is 2). Since the next element is not equal to 1, we can keep it in the array. We move to the next element (which is also 2). Since no two adjacent elements are equal in a beautiful array, we can keep this element as well. We move to the next element (which is also 2). Since no two adjacent elements are equal in a beautiful array, we can keep this element as well. We move to the next element (which is 3). Since no two adjacent elements are equal in a beautiful array, we can keep this element as well.

After processing the entire array, we would have made 1 deletion (removing the second element in the array). Thus, the minimum number of deletions that we need to make to obtain a beautiful array is 1.

Algorithm:

1. Sort the given array in non-decreasing order.
2. Initialize a variable deletionsCount to 0.
3. Iterate through the sorted array.
4. If the current element is equal to the previous element, delete the current element and increment deletionsCount by 1.
5. If the current element is not equal to the previous element, keep it in the array.
6. Return deletionsCount as the minimum number of deletions needed.

Code:

Here is the code for the solution approach we just discussed:

class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int deletionsCount = 0;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] == nums[i-1]){
                deletionsCount++;
            }
        }
        return deletionsCount;
    }
};

Time Complexity:

The time complexity of this algorithm is O(nlogn), where n is the size of the given array. This is because we need to sort the array before processing it.

Space Complexity:

The space complexity of this algorithm is O(1), because we are only using constant extra space (for storing deletionsCount).

1