Minimum Deletions to Make Array Beautiful

Medium

Asked by:

18 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed integer array nums. The array nums is beautiful if:

nums.length is even.
nums[i] != nums[i + 1] for all i % 2 == 0.

Note that an empty array is considered beautiful.

You can delete any number of elements from nums. When you delete an element, all the elements to the right of the deleted element will be shifted one unit to the left to fill the gap created and all the elements to the left of the deleted element will remain unchanged.

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

Example 1:

Input: nums = [1,1,2,3,5]
Output: 1
Explanation: You can delete either nums[0] or nums[1] to make nums = [1,2,3,5] which is beautiful. It can be proven you need at least 1 deletion to make nums beautiful.

Example 2:

Input: nums = [1,1,2,2,3,3]
Output: 2
Explanation: You can delete nums[0] and nums[5] to make nums = [1,2,2,3] which is beautiful. It can be proven you need at least 2 deletions to make nums beautiful.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array, `nums`?
Can the elements in `nums` be negative, zero, or non-integer values?
If multiple beautiful arrays can be formed with the same minimum number of deletions, is any one of them acceptable?
What should I return if the input array is null or empty?
Is there a limit on the range of values in `nums`?

Brute Force Solution

Approach

The brute force approach to making an array beautiful is to try every single possible combination of deletions. We will check each of these combinations to find the one that requires the fewest deletions and also makes the array beautiful.

Here's how the algorithm would work step-by-step:

Consider all possible ways to remove items from the list.
For each of those ways, check if the remaining items form a 'beautiful' list.
A 'beautiful' list has a special property: at every even position (starting from the first item), the item must be different than the item right after it.
If the remaining items do form a 'beautiful' list, count how many items we removed to get there.
Do this for every single possible way to remove items.
Once we've tried every possible way, find the way that removed the fewest items while still resulting in a 'beautiful' list.
The number of items removed in that best way is the answer.

Code Implementation

def min_deletions_brute_force(numbers):
    min_deletions = float('inf')
    array_length = len(numbers)

    for i in range(2**array_length):
        subset = []
        deletions = 0

        for j in range(array_length):
            if (i >> j) & 1:
                subset.append(numbers[j])
            else:
                deletions += 1

        is_beautiful = True
        subset_length = len(subset)

        # Check if the subset is beautiful
        for k in range(0, subset_length - 1, 2):
            if subset[k] == subset[k+1]:
                is_beautiful = False
                break

        #If the subset has an odd number of elements, it can still be beautiful
        if subset_length % 2 != 0:
            pass
        elif is_beautiful:
            min_deletions = min(min_deletions, deletions)

    return min_deletions

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach involves considering all possible subsets of the input array. For an array of size n, there are 2^n possible subsets (each element can either be included or excluded). For each subset, we iterate through the remaining elements to check if it is beautiful, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2^n). However, since the 2^n term dominates, we can simplify this to O(2^n).

Space Complexity

O(N) – The brute force approach considers all possible subsets of the input array to find a beautiful array. In the worst case, the recursion depth could be N, where N is the length of the input array, num. At each level of recursion, a copy of the array or indices may be created. Thus, the space complexity arises from the recursive call stack, which can grow up to a depth of N in the worst case, leading to O(N) space. This space is used to store the intermediate states of the recursion.

Optimal Solution

Approach

The goal is to make the arrangement 'beautiful' by strategically removing as few items as possible. We look at the items one by one and decide whether to keep it or discard it to maintain an alternating pattern where neighboring items are different.

Here's how the algorithm would work step-by-step:

Start by looking at the items one at a time, from left to right.
Keep track of how many items we've kept so far. If we've kept an even number of items, we need to make sure the next item we keep is different from the last kept item. If we've kept an odd number of items, we can keep the next one regardless of its value.
If keeping the current item would mess up the 'beautiful' pattern (because it's the same as the previous kept item and we've kept an even number of items already), then we skip it and count it as a deletion.
If keeping the current item doesn't break the pattern, or if we've kept an odd number of items already, then we keep it.
Continue this process until we've looked at all the items.
The total number of items skipped is the minimum number of deletions needed to make the arrangement 'beautiful'.

Code Implementation

def min_deletion(numbers):
    deletion_count = 0
    items_kept_count = 0
    last_kept_number = -1

    for number in numbers:
        # When even items are kept, current item must differ.
        if items_kept_count % 2 == 0:

            if number == last_kept_number:
                deletion_count += 1

            # Keep the current number and update last_kept_number.
            else:
                items_kept_count += 1
                last_kept_number = number

        # If an odd number of items are kept, we keep the number.
        else:
            items_kept_count += 1
            last_kept_number = number

    # If the final length is odd, we need to delete one more.
    if items_kept_count % 2 != 0:
        deletion_count += 1

    return deletion_count

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array nums of size n exactly once. Inside the loop, it performs constant-time operations such as comparing elements and incrementing counters. Since the number of operations scales linearly with the input size n, the time complexity is O(n).

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it only uses a few integer variables to keep track of the number of kept items and potentially an index or counter for iteration. No additional data structures like arrays, lists, or hash maps are created that scale with the input array's size N. The space used remains constant irrespective of the number of elements in the input array.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 since an empty array is considered beautiful by default.
Array with a single element	Return 1, as the array must have an even length to be beautiful, so we delete the single element.
Array with two identical elements	Return 1, as deleting either element makes the array beautiful.
Array with an odd number of elements where the last two elements are equal after deletions.	Account for the final element if, after deletions, the effective length is still odd; delete the last element to satisfy the even length constraint.
Array with all identical elements	The number of deletions will be the smallest number to make the array beautiful.
Large input array size	Ensure the solution has linear time complexity, such as iterating through the array once.
Array with a long sequence of identical elements at the end	The algorithm should correctly handle the sequence of identical elements and make necessary deletions to maintain the beautiful property.
Integer overflow if calculating array size or index	Use appropriate data types (e.g., long in Java or C++) to prevent integer overflow issues when dealing with large array sizes or indices.

Null or empty input array

How to Handle:

Return 0 since an empty array is considered beautiful by default.

Array with a single element

How to Handle:

Return 1, as the array must have an even length to be beautiful, so we delete the single element.

Array with two identical elements

How to Handle:

Return 1, as deleting either element makes the array beautiful.

Array with an odd number of elements where the last two elements are equal after deletions.

How to Handle:

Account for the final element if, after deletions, the effective length is still odd; delete the last element to satisfy the even length constraint.

Array with all identical elements

How to Handle:

The number of deletions will be the smallest number to make the array beautiful.

Large input array size

How to Handle:

Ensure the solution has linear time complexity, such as iterating through the array once.

Array with a long sequence of identical elements at the end

How to Handle:

The algorithm should correctly handle the sequence of identical elements and make necessary deletions to maintain the beautiful property.

Integer overflow if calculating array size or index

How to Handle:

Use appropriate data types (e.g., long in Java or C++) to prevent integer overflow issues when dealing with large array sizes or indices.