Minimum Deletions To Make Array Beautiful
01 · Problem
An array arr is called beautiful when:
- its length is even, and
arr[i] != arr[i + 1]for every even indexi(so each consecutive pair (arr[0], arr[1]), (arr[2], arr[3]), ... has two different values).
The empty array is beautiful. You are given an integer array nums. You may delete any elements; the remaining elements close up and keep their original relative order.
Return the minimum number of deletions needed to make nums beautiful.
02 · Examples
nums = [7,7,7,3]
2
Delete two of the 7s to get [7,3], one pair of different values with even length.
nums = [2,5,5,5,8]
1
Delete one of the 5s to get [2,5,5,8]: pairs (2,5) and (5,8) both differ. The original length is odd, so at least one deletion is needed.
nums = [4]
1
A single element can never form a pair, so it must be deleted to leave the empty (beautiful) array.
03 · Constraints
- 011 <= nums.length <= 105
- 020 <= nums[i] <= 105
- 03The empty array counts as beautiful
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.