Minimum Deletions to Make Array Beautiful

Minimum Deletions to Make Array Beautiful - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,1,2,3,5]

› Output: 1

💡 Note: Delete one element to get [1,2,3] which is not beautiful (odd length), or [1,2] which is beautiful. Minimum deletions: 1 (delete either the second 1 or the last 5).

Example 2 — All Same Elements

$ Input: nums = [1,1,1,1]

› Output: 2

💡 Note: All pairs would be identical. Delete 2 elements to get [1,1] then delete both to get [] (empty array is beautiful), or keep alternating elements. Minimum: 2 deletions.

Example 3 — Already Beautiful

$ Input: nums = [1,2,3,4]

› Output: 0

💡 Note: Array has even length and nums[0] ≠ nums[1], nums[2] ≠ nums[3]. Already beautiful, no deletions needed.

Constraints

0 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [1,1,2,3,5] - length 5 (odd), has identical consecutive elements

Pairing Strategy

Form pairs greedily: (1,2) and (3,?) - need to handle duplicates and odd length

Output

Delete minimum elements to achieve beautiful array

Key Takeaway

🎯 Key Insight: Use greedy pairing strategy - process elements left to right, forming pairs when possible and deleting duplicates

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to greedily form pairs from left to right. When two consecutive elements are the same, we must delete one. The greedy approach achieves optimal solution in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n)	O(1)	Build beautiful array greedily by forming pairs from left to right
Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Try all possible ways to delete elements and check which results in minimum deletions
Stack-Based Approach	O(n)	O(n)	Use a stack to build the beautiful array by tracking valid pairs

Greedy Approach — Algorithm Steps

Iterate through array from left to right
Try to pair current element with previous unpaired element
If they're different, form a pair; if same, delete current element
Count total deletions needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Pairing

Begin from the first element and try to form pairs

Check Adjacent

If two adjacent elements are same, delete one; otherwise form a pair

Continue

Move to next unpaired element and repeat

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    if (n == 0) return 0;
    
    int deletions = 0;
    int i = 0;
    
    while (i < n) {
        // If this is the last element, we need to delete it (array must have even length)
        if (i == n - 1) {
            deletions++;
            break;
        }
        
        // If current and next elements are the same, delete the next one
        if (nums[i] == nums[i + 1]) {
            deletions++;
            i++; // Skip the deleted element
        } else {
            // Form a valid pair, move to next potential pair
            i += 2;
        }
    }
    
    return deletions;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    if (strstr(line, "[]") != NULL) {
        printf("0\n");
        return 0;
    }
    
    // Simple array parsing
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track state

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler