Leetcode 2216: Minimum Deletions to Make Array Beautiful

Input: You are given a 0-indexed integer array nums.

Example: nums = [4, 4, 6, 7, 8, 9]

Constraints:

• 1 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^5

Output: Return the minimum number of elements to delete from nums to make it beautiful.

Example: Output: 1

Constraints:

• The array may have duplicates that need to be removed.

Goal: Find the minimum number of deletions required to make the array beautiful.

Steps:

• Iterate through the array and identify the elements that need to be removed.

• Check for pairs of adjacent elements where nums[i] == nums[i + 1] and ensure the length remains even.

• Count the number of deletions required and return the result.

Goal: Ensure the input is within the defined range and handle the array efficiently.

Steps:

• 1 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^5

Assumptions:

• The array may contain duplicate elements.

• The array must be modified by deletion of elements only.

• Input: Input: nums = [4, 4, 6, 7, 8, 9]

• Explanation: For this input, the first two elements are the same, so one of them must be deleted. The final beautiful array will be [4, 6, 7, 8, 9]. Hence, the minimum number of deletions required is 1.

Approach: To solve this problem, we need to find and remove adjacent duplicate elements in the array while ensuring the final array length is even.

Observations:

• Adjacent duplicates should be deleted to meet the criteria of a beautiful array.

• After deletion, the array should still maintain an even length.

• We can use a greedy approach to iterate through the array, checking adjacent elements, and remove them when necessary.

Steps:

• Iterate through the array and check if the current element equals the next one.

• If they are equal, increment the deletion count and skip the next element.

• Ensure that the final array has an even length by adjusting the result if needed.

Empty Inputs:

• An empty array is considered beautiful by definition.

Large Inputs:

• The solution should efficiently handle arrays with up to 100,000 elements.

Special Values:

• The array may have all elements identical, or no duplicates at all.

Constraints:

• Ensure that the input size is within the constraints and handle edge cases appropriately.

int minDeletion(vector<int>& nums) {
    int ans = 0;
    for(int i = 0; i < nums.size() - 1; i++)
        if(nums[i] == nums[i + 1] && (i - ans) % 2 == 0) ans++;
    
    return ans + (nums.size() - ans) % 2;
}

1 : Function Declaration

int minDeletion(vector<int>& nums) {

This is the function declaration for `minDeletion`, which takes a vector of integers `nums` and returns an integer representing the minimum deletions required.

2 : Variable Initialization

    int ans = 0;

The variable `ans` is initialized to 0. This will keep track of the number of deletions made to ensure the array alternates.

3 : For Loop

    for(int i = 0; i < nums.size() - 1; i++)

This loop iterates through the array `nums`, stopping at the second-to-last element to compare each element with the next one.

4 : Conditional Check

        if(nums[i] == nums[i + 1] && (i - ans) % 2 == 0) ans++;

This conditional checks if two consecutive elements are equal and if the difference between the current index `i` and `ans` is even. If both conditions are true, it increments `ans` to indicate a necessary deletion.

5 : Return Statement

    return ans + (nums.size() - ans) % 2;

Return the result by adding the number of deletions (`ans`) to the parity correction, which ensures the final array has an even number of elements after deletions.

Best Case: O(n) where n is the length of the input array, as we only iterate through the array once.

Average Case: O(n) where n is the length of the input array.

Worst Case: O(n) where n is the length of the input array.

Description: The solution processes the array in a single pass.

Best Case: O(1) for the space used during the iteration.

Worst Case: O(1) for the space used during the iteration.

Description: The solution only uses a constant amount of extra space.

Leetcode 2216: Minimum Deletions to Make Array Beautiful

Explore →