2216. Minimum Deletions to Make Array Beautiful

MediumStackGreedyArray
Leetcode Link

Problem Description

You are given an integer array nums with 0-based indexing. To be considered beautiful, the array must have the following properties:

  • nums.length is an even number.
  • nums[i] is not equal to nums[i + 1] for all i where i % 2 == 0.

An empty array also meets the criteria for being beautiful.

Your task is to remove the minimum number of elements from nums to make it beautiful. When you remove an element, all elements on the right shift one position to the left to fill the void, while the ones on the left stay unchanged.

You must return the smallest number of elements that need to be deleted for nums to become beautiful.

Intuition

The key to solving this problem involves a two-part approach. We need to:

  1. Identify and remove elements to ensure all even-indexed positions have different values than their immediate next (odd-indexed) neighbors.
  2. Ensure that after the above deletion, the length of the array is even.

We can achieve the first goal by iterating through the array and comparing the element at each even index i with its next element i + 1. If they are the same, we increment a counter (ans), representing the number of deletions required, and then move onto the next index. If they are different, we simply step over both indices and continue checking the subsequent pairs. By incrementing the counter only when necessary, we are effectively "deleting" elements to satisfy the pairing requirement.

The second goal is to check if the length of the modified array (original length minus total deletions) is even. If not, we must remove one more element to meet the criteria for a beautiful array. This check is conducted after the pairing loop with a simple modulo operation.

Combining these steps ensures that we return the minimum number of deletions necessary to make nums beautiful.

Learn more about Stack and Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Solution Approach

The implementation of the provided solution follows a straightforward index-based iterative approach to attain the desired beautiful array. Here is a detailed explanation of the algorithm:

  • We initialize two variables, n to hold the length of the array nums, and ans to keep track of the count of deletions, which is initially set to 0.
  • An index variable i is also initialized to 0, which is used to traverse the array.

The iterative process begins and continues while i is less than n - 1 because we always need to check the current element and its next element, and hence we can't process the last element if i were equal to n - 1.

Within the loop:

  • We first check if the current element nums[i] is the same as the next element nums[i + 1]. If they are the same:
    • We increment ans, since we would need to remove one of these elements to fulfill the condition where even-indexed elements (i % 2 == 0) must not be equal to their immediate next elements.
    • We then increment i by 1 to move past the duplicate element.
  • If the current element nums[i] is not the same as nums[i + 1], then no deletion is required here, and we increment i by 2 to skip both elements and move to the next pair.

After iterating through the array, we need to perform a final check to make sure the resulting array has an even number of elements. We calculate the potential new length of nums by subtracting the count of deletions (ans) from the original length (n). If this number is odd:

  • We increment ans by 1, implying one more element needs to be deleted to ensure even length.

The ans variable, which records the minimum number of deletions needed, is then returned.

Important to note is that there are no additional data structures required, and this solution is built upon simple variables and conditional logic, showcasing an in-place approach with a linear time complexity of O(n), where n is the number of elements in the array. This efficiency is due to the single-pass loop over the array elements.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Example Walkthrough

Let's consider the example array nums = [1, 1, 2, 3, 3, 4] and walk through the solution approach.

  • Initialize n to 6 (length of nums) and ans to 0.
  • Set the traversal index i to 0.

As we iterate:

  • For i = 0: nums[0] is 1 and nums[0 + 1] is also 1.
    • They are the same, so we must increment ans to 1, and i to 1.
  • Now, i = 1: we skip the check here because it's an odd index and increment i to 2.
  • For i = 2: nums[2] is 2 and nums[2 + 1] is 3.
    • They are different, so we move on to the next even index by incrementing i to 4.
  • For i = 4: nums[4] is 3 and nums[4 + 1] is 4.
    • They are different, so we increment i to 6 and exit the loop (since i is not less than n - 1).

After completing the loop, we do the final check on the length of the array after deletions:

  • n - ans would give us 6 - 1 = 5, an odd number.
  • Because it's not even, we increment ans by 1 to make it 2.

The array nums could be made beautiful by removing 2 elements. The final answer, ans, is 2.

The elements that would be removed are the first 1 to resolve the duplicate at the start, and any single element from the remaining ones to ensure the array length is even. Thus, the minimum number of elements to remove to make nums beautiful is 2.

Solution Implementation

1class Solution:
2    def minDeletion(self, nums: List[int]) -> int:
3        # Initialize the length of the input list
4        length = len(nums)
5      
6        # Initialize the index and the counter for the number of deletions
7        index = deletions_count = 0
8      
9        # Loop through the list while the current index is less than the index of the last pair
10        while index < length - 1:
11            # If the current element is the same as the next one,
12            # it violates the alternating condition, so we need to delete one of them
13            if nums[index] == nums[index + 1]:
14                # Increment the deletion count
15                deletions_count += 1
16                # Move to the next element
17                index += 1
18            # If the current element is different from the next one,
19            # we can just move to the next pair
20            else:
21                index += 2
22      
23        # If the updated length, after deletions, is still odd, we need to remove one more element
24        if (length - deletions_count) % 2:
25            deletions_count += 1
26      
27        # Return the total number of deletions
28        return deletions_count
29
1class Solution {
2  
3    /**
4     * This method finds the minimum number of deletions required to make the
5     * array beautiful. An array is beautiful if it has an even length and
6     * no two adjacent elements are equal.
7     * 
8     * @param nums Array of integers to be made beautiful.
9     * @return The minimum number of deletions required.
10     */
11    public int minDeletion(int[] nums) {
12        int arrayLength = nums.length; // Total length of the input array.
13        int deletionsNeeded = 0; // Counter for the required deletions.
14
15        // Iterate through the array to find pairs of equal adjacent elements.
16        for (int i = 0; i < arrayLength - 1; ++i) {
17            if (nums[i] == nums[i + 1]) {
18                // Increment the count if a pair of equal adjacent elements is found.
19                ++deletionsNeeded;
20            } else {
21                // Skip the next element if the current and next elements are not equal.
22                ++i;
23            }
24        }
25
26        // Check if the length of the array after deletions is even.
27        // If it's odd, we need an additional deletion to make the length even.
28        if ((arrayLength - deletionsNeeded) % 2 == 1) {
29            ++deletionsNeeded;
30        }
31
32        // Return the total number of deletions needed to make the array beautiful.
33        return deletionsNeeded;
34    }
35}
36
1class Solution {
2public:
3    int minDeletion(vector<int>& nums) {
4        // Initialize the length of the input vector.
5        int length = nums.size();
6      
7        // This variable will store the minimum number of deletions required.
8        int minDeletionsRequired = 0;
9
10        // Iterate over the array elements.
11        for (int i = 0; i < length - 1; ++i) {
12            // If the current element is equal to the next one, we need
13            // to delete one of them.
14            if (nums[i] == nums[i + 1]) {
15                ++minDeletionsRequired;
16            } else {
17                // If they are not equal, skip the next element as it
18                // should form a pair with its subsequent element.
19                ++i;
20            }
21        }
22
23        // After removing pairs, if the array has an odd number of elements,
24        // delete one more element to make the length even.
25        if ((length - minDeletionsRequired) % 2 == 1) {
26            ++minDeletionsRequired;
27        }
28      
29        // Return the total number of deletions required.
30        return minDeletionsRequired;
31    }
32};
33
1function minDeletion(nums: number[]): number {
2    // Initialize the length of the nums array.
3    const length = nums.length;
4  
5    // Initialize the variable to count the number of deletions required.
6    let deletionCount = 0;
7  
8    // Initialize an index counter to iterate through the array.
9    let index = 0;
10  
11    // Loop over the array elements, excluding the last one, 
12    // since we check the current and next element in each iteration.
13    while (index < length - 1) {
14        // If the current and next elements are the same, increment index by 1 
15        // to skip the current element and increment deletionCount.
16        if (nums[index] === nums[index + 1]) {
17            index++;
18            deletionCount++;
19        } else {
20            // If they're different, move forward by 2 as we need pairs of distinct elements.
21            index += 2;
22        }
23    }
24  
25    // Check if the array length after deletions is odd.
26    // If so, more deletions are needed to make the length even.
27    if ((length - deletionCount) % 2 === 1) {
28        deletionCount++;
29    }
30  
31    // Return the final number of deletions required.
32    return deletionCount;
33}
34
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

Time Complexity

The given Python code iterates over the list nums once. During each iteration, it either increments i by one if the current element and the next element are the same, or increments i by two if they are different. In the worst case scenario (no two adjacent elements are the same), i will be incremented by two for each check, except possibly the last element, resulting in n/2 checks.

Despite this, the complexity is not reduced and the algorithm processes each element at most once. Therefore, regardless of the pattern of elements in nums, the time complexity is O(n), where n is the number of elements in nums.

Space Complexity

The space complexity of the algorithm is O(1). It only uses a fixed number of integer variables (n, i, ans) that do not depend on the size of the input list nums. There is no additional space used that grows with the input size. The input list itself is not modified, so the space complexity remains constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫