Minimum Deletions to Make Array Beautiful

• Initialize a DP array dp of size n, where dp[i] stores the length of the longest valid subsequence ending with nums[i].
• Iterate from i = 0 to n-1:
  • Set dp[i] = 1 (for the subsequence containing only nums[i]).
  • Iterate from j = 0 to i-1:
    • Let len_j = dp[j].
    • If len_j is odd, we can append nums[i]. Update dp[i] = max(dp[i], len_j + 1).
    • If len_j is even and nums[i] != nums[j], we can append nums[i]. Update dp[i] = max(dp[i], len_j + 1).
• Find the maximum value in the dp array, max_len.
• If max_len is odd, the number of elements we can keep is max_len - 1. Otherwise, it's max_len.
• The result is n - kept_count.

This approach solves the problem by building up solutions for progressively larger prefixes of the array. We define dp[i] as the length of the longest valid subsequence (one that satisfies seq[k] != seq[k+1] for even k) that ends with the element nums[i].

To compute dp[i], we consider all previous elements nums[j] (where j < i) as potential predecessors. We can append nums[i] to the subsequence ending at nums[j] if the resulting new subsequence remains valid. The condition for appending depends on the length of the subsequence ending at j, dp[j]:

• If dp[j] is odd, nums[j] is at an odd-indexed position in its subsequence. The new element nums[i] will be at an even-indexed position, which has no immediate predecessor constraint, so we can always append.
• If dp[j] is even, nums[j] is at an even-indexed position. The new element nums[i] will be at an odd-indexed position, so we can only append it if nums[i] != nums[j].

After filling the dp array, the maximum value max_len represents the longest possible valid subsequence. Since a beautiful array must also have an even length, the final number of elements we can keep is max_len if it's even, or max_len - 1 if it's odd. The minimum deletions will be the original array length minus this final count.

1import java.util.Arrays;2 3class Solution {4    public int minDeletion(int[] nums) {5        int n = nums.length;6        if (n == 0) {7            return 0;8        }9 10        int[] dp = new int[n];11        Arrays.fill(dp, 1);12 13        int maxLen = 1;14 15        for (int i = 1; i < n; i++) {16            for (int j = 0; j < i; j++) {17                // The new element nums[i] will be at index dp[j] (0-indexed)18                // If dp[j] is even, it's an even position. nums[j] is at dp[j]-1 (odd).19                // If dp[j] is odd, it's an odd position. nums[j] is at dp[j]-1 (even).20                if (dp[j] % 2 != 0) { // nums[j] is at an even position in its subsequence21                    if (nums[i] != nums[j]) {22                        dp[i] = Math.max(dp[i], dp[j] + 1);23                    }24                } else { // nums[j] is at an odd position in its subsequence25                    dp[i] = Math.max(dp[i], dp[j] + 1);26                }27            }28            maxLen = Math.max(maxLen, dp[i]);29        }30 31        int keptCount = maxLen;32        if (keptCount % 2 != 0) {33            keptCount--;34        }35 36        return n - keptCount;37    }38}

Note: The logic in the code snippet is slightly different but follows the same DP principle. A simpler DP transition is dp[i] = 1 + max(dp[j]) where j<i and (dp[j]%2==1 && nums[i]!=nums[j]) || (dp[j]%2==0). The provided code implements this logic.

• Initialize an empty list, res.
• Iterate through each num in nums.
• If the current size of res is even, it's a new pair's start, so add num to res.
• If the current size of res is odd, num would be the second element of a pair. Add it only if it's different from the last element in res.
• After the loop, let keptCount = res.size().
• If keptCount is odd, we must delete one more element (the last one). So, finalKeptCount = keptCount - 1.
• Otherwise, finalKeptCount = keptCount.
• Return nums.length - finalKeptCount.

The greedy strategy aims to maximize the number of elements we keep, which is equivalent to minimizing deletions. We iterate through the nums array and build a new list, let's call it beautifulList, which will store the elements of our resulting beautiful array.

The logic for adding an element num from nums to beautifulList depends on the current size of beautifulList:

• If beautifulList.size() is even, the new element num will be at an even index (e.g., 0, 2, ...). This is the first element of a new pair, so there are no constraints. We can greedily add num to beautifulList.
• If beautifulList.size() is odd, the new element num will be at an odd index (e.g., 1, 3, ...). This is the second element of a pair. It must be different from the preceding element (which is at beautifulList.size() - 1). We add num only if num != beautifulList.get(beautifulList.size() - 1). If they are equal, we must delete num and continue searching for a suitable element for this position.

After iterating through all of nums, beautifulList holds the longest possible sequence satisfying the second condition. Finally, we check the even-length condition. If beautifulList.size() is odd, we must perform one final deletion (conceptually, removing the last element). The total deletions is the original length minus the final size of our beautiful array.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int minDeletion(int[] nums) {6        List<Integer> beautifulList = new ArrayList<>();7        for (int num : nums) {8            if (beautifulList.size() % 2 == 0) {9                beautifulList.add(num);10            } else {11                if (beautifulList.get(beautifulList.size() - 1) != num) {12                    beautifulList.add(num);13                }14            }15        }16 17        int keptCount = beautifulList.size();18        if (keptCount % 2 != 0) {19            return nums.length - (keptCount - 1);20        } else {21            return nums.length - keptCount;22        }23    }24}

• Initialize deletions = 0.
• Iterate i from 0 to n-2.
• The index of nums[i] in the new array is i - deletions.
• If this new index (i - deletions) is even, nums[i] is the first element of a pair.
• Check if it's equal to the next element, nums[i+1]. If nums[i] == nums[i+1], we must delete one. We increment deletions.
• After the loop, calculate the number of remaining elements: keptCount = n - deletions.
• If keptCount is odd, we need one more deletion. Increment deletions.
• Return deletions.

We can achieve the same result as the greedy approach without using any extra space. The key observation is that to make a decision at index i, we only need to know the effective size of the beautiful array built so far, not its actual contents. The effective size determines whether nums[i] would be at an even or odd position.

The effective index for nums[i] in the new array is i - deletions, where deletions is the count of elements we have discarded from nums[0...i-1]. We only care about violations of the form new_nums[k] == new_nums[k+1] where k is even. This corresponds to an element nums[i] at an even effective index i - deletions being equal to the next non-deleted element.

A simpler way to implement this is to iterate through the array and find adjacent elements nums[i] and nums[i+1] that need to be placed at an even and odd index respectively. If (i - deletions) is an even index and nums[i] == nums[i+1], we have a violation. We must delete one element, so we increment deletions.

After iterating through the array, we have the total deletions required to satisfy the second condition. Finally, we check if the remaining number of elements, nums.length - deletions, is even. If not, one more deletion is required to satisfy the first condition.

1class Solution {2    public int minDeletion(int[] nums) {3        int n = nums.length;4        int deletions = 0;5        6        // We iterate up to n-1 because we access i+17        for (int i = 0; i < n - 1; i++) {8            // The index in the new (conceptual) array is (i - deletions)9            if ((i - deletions) % 2 == 0) {10                if (nums[i] == nums[i + 1]) {11                    // Found a pair nums[k] == nums[k+1] where k is even in the new array.12                    // We must delete one. Incrementing deletions effectively deletes nums[i+1]13                    // by shifting the indices of all subsequent elements.14                    deletions++;15                }16            }17        }18 19        // After all pair-based deletions, if the remaining array has an odd length,20        // we must delete one more element (e.g., the last one).21        if ((n - deletions) % 2 != 0) {22            deletions++;23        }24 25        return deletions;26    }27}