We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Deletions to Make Array Beautiful

Number: 1355

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given an array of integers, the goal is to delete the minimum number of elements so that the resulting array is "beautiful." An array is considered beautiful if its length is even and for every even index i (0-indexed), the element at nums[i] is not equal to its immediate next element nums[i+1]. Note that an empty array is also considered beautiful.

Key Insights

  • Use a greedy approach to simulate the construction of a beautiful array.
  • Iterate through the array while forming valid pairs.
  • If adding an element would cause a pair violation (i.e., both elements in a pair are the same), skip that element (count it as a deletion).
  • After processing, if the length of the constructed array is odd, remove the last element to satisfy the even-length condition.

Space and Time Complexity

Time Complexity: O(n) - We traverse the input array once. Space Complexity: O(n) - In the worst-case scenario, we may store nearly all elements in our simulation (this can be optimized to O(1) by just tracking counts).

Solution

We can solve this problem by simulating the construction of a "beautiful" array. Initialize an empty result list and a deletion counter. Loop through the input array; add the current element if it does not cause an even-index pair to have identical elements. If it would, consider it deleted (increment deletion counter). Finally, if the resulting list has an odd number of elements, remove the last element and increase the deletion counter by one to ensure an even count.

Code Solutions

# Python implementation for Minimum Deletions to Make Array Beautiful

def minDeletion(nums):
    # List to simulate construction of the beautiful array
    beautiful = []
    # Counter for the number of deletions required
    deletions = 0
    
    # Process each number in the input array
    for num in nums:
        # If the current beautiful list size is odd, we pair it with the previous element
        if len(beautiful) % 2 == 1:
            # If the last added element equals the current value, skip it and count a deletion
            if beautiful[-1] == num:
                deletions += 1
                continue
        # Otherwise, add the number to the beautiful array
        beautiful.append(num)
    
    # Ensure that the beautiful array has an even length
    if len(beautiful) % 2 == 1:
        deletions += 1  # Remove the last extra element
    
    return deletions

# Example usage:
# nums = [1,1,2,3,5]
# print(minDeletion(nums))  # Expected output: 1
← Back to All Questions