Is Minimum Deletions to Make Array Sharp easy or hard?

It is an easy problem. The difficulty comes from realizing that deletions only need to target duplicates inside each run of equal values, which reduces the task to a single comparison per adjacent pair.

Minimum Deletions to Make Array Sharp Python solution?

In Python, iterate with range(len(nums) - 1) and add 1 to a counter when nums[i] == nums[i + 1], then return the counter. The solution is a few lines and runs in O(n) time with O(1) extra space.

How to solve Minimum Deletions to Make Array Sharp in O(n)?

Loop from index 0 to n-2 and increment a counter whenever nums[i] equals nums[i+1]. Return the counter. A run of equal values only needs one survivor, so each equal adjacent pair corresponds to exactly one required deletion.

What is the best approach for Minimum Deletions to Make Array Sharp?

The best approach is to count the adjacent pairs where nums[i] equals nums[i+1] in a single pass. Each run of k equal values needs k-1 deletions, so the total equals the number of equal adjacent pairs. This runs in O(n) time with O(1) extra space.

What data structure is used in Minimum Deletions to Make Array Sharp?

The optimal solution uses no data structure beyond a single integer counter. A stack is an alternative that rebuilds the valid array, and it is useful for understanding the problem but is not required for the final answer.

What is the time complexity of Minimum Deletions to Make Array Sharp?

The optimal solution runs in O(n) time because it scans the array once. The stack-based alternative also runs in O(n) time but uses O(n) extra space to store the rebuilt array.

Is Minimum Deletions to Make Array Sharp asked at Google, Amazon, or Meta?

This problem is tagged General on FleetCode and is classified as Easy with a 67.5% acceptance rate. Company-specific frequency data is not listed for it, so check recent interview reports on company tag pages before assuming it appears at a given firm.

Description Hints 2 Solution Video 0:48

4083. Minimum Deletions to Make Array Sharp

Easy67.5% acceptance

You are given an integer array nums.

You may delete any number of elements from nums. The remaining elements keep their original order.

The resulting array a is sharp if the bitwise XOR of every pair of adjacent elements is non-zero. That is, a[i] XOR a[i + 1] != 0 for every index i such that 0 <= i < a.length - 1. An array with at most one element is sharp.

Return the minimum number of deletions needed to make nums sharp.

Bitwise XOR compares the corresponding bits of two integers. A bit in the result is 1 if the corresponding bits differ, and 0 otherwise.

Example 1:

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

Output: 3

Explanation:

The pairs at indices (0, 1), (2, 3), and (3, 4) each have an XOR of 0.
Deleting one 1 and two 2s leaves [1, 2, 3], where 1 XOR 2 == 3 and 2 XOR 3 == 1 are both non-zero. Therefore, the answer is 3.

Example 2:

Input: nums = [4,4,9,4]

Output: 1

Explanation:

The pair at indices (0, 1) has an XOR of 0.
Deleting either of these two 4s leaves [4, 9, 4], where 4 XOR 9 == 13 and 9 XOR 4 == 13 are both non-zero.

Constraints:

2 <= nums.length <= 100
1 <= nums[i] <= 100

Hints open one at a time

Hint 1

The XOR of two integers is zero exactly when they are equal. Therefore, adjacent retained elements must have different values.

Hint 2

Keep exactly one element from each maximal run of equal values. The number of deletions equals the number of adjacent equal pairs in the original array.

0:48

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minDeletions(self, nums: list[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,1,2,2,2,3]

Input

[4,4,9,4]

Your code is saved on this device.Solution