Minimum Deletions to Make Array Sharp solution and explanation
4 more videos on this problem
LeetCode Weekly Contest #524 Q1. Minimum Deletions to Make Array SharpADevOpsEngineer · 0:48 · 87 views
Minimum Deletions to Make Array Sharp | Leetcode 4083 | Weekly Contest 524 | Detailed ExplanationVijay Algorithms · 6:06 · 72 views
Minimum Deletions to make Array Sharp | Leetcode Problem number 4083 | Weekly contest 524.Prince Gupta Study · 9:18 · 21 views
LeetCode 4083: Minimum Deletions to Make Array Sharp | Java Solution | EasyCakot Coding · 5:28 · 17 views
LeetCode 4083 Minimum Deletions to Make Array Sharp — the XOR disguise, explainedPrateek Goel · 12:56 · 4 views
The problem
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], where1 XOR 2 == 3and2 XOR 3 == 1are 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], where4 XOR 9 == 13and9 XOR 4 == 13are both non-zero.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 100
Approach overview
Problem Overview: You are given an array and must delete the fewest elements so that no two adjacent values in the result are equal. Deletions shift the remaining elements, so you need to track what ends up next to what.
Approach 1: Greedy Stack Rebuild (O(n) time, O(n) space)
Build a new list by scanning left to right. Push an element only if it differs from the top of the stack, otherwise count it as a deletion. The stack always holds the current valid prefix, so the top is the only neighbor you need to compare. This is easy to reason about and works without any counting trick, but it allocates an extra array. Use it when you want to verify the logic or when you need the actual resulting array, not just the count.
Approach 2: Count Adjacent Equals (O(n) time, O(1) space)
Scan the array once and count every index i where nums[i] == nums[i+1]. The key insight is that a run of k equal values needs exactly k-1 deletions to collapse into one value, and deleting duplicates inside a run never creates a new equal adjacency because the surviving value's neighbors are already different from it. The total deletions equal the sum of (k-1) over all runs, which is the same as the number of equal adjacent pairs. You only need one pass and a single integer counter, so there is no extra memory. Prefer this approach in every real submission.
Recommended for interviews: Start by describing the stack approach to show you understand that deletions reshape the neighbors. Then move to counting adjacent equal pairs and explain why the run-length argument holds. The stack solution shows understanding, but the single-pass counter shows you can reduce the problem to its core invariant. Interviewers look for that reduction. For more practice on related patterns, see array and stack problems on FleetCode.
Solution
Thinking
nis at most100, so comparing adjacent elements is cheap, but enumerating every deletion subset is exponential. Adjacent XOR is0exactly when the two values are equal, so searching subsets is unnecessary.The bottleneck is a contiguous run of equal values. Relative order is fixed, so a run can keep only one element. Runs of different values are already separated by an unequal boundary, and deleting the extras inside a run does not make those runs interfere.
A run of length
kcostsk-1deletions, and it contains exactlyk-1adjacent equal pairs. One left-to-right scan that counts positions wherenums[i]=nums[i-1]is the minimum number of deletions.
Two integers have bitwise XOR 0 if and only if they are equal. The task is therefore to delete as few elements as possible, without changing the relative order, so that every pair of adjacent remaining elements is different.
Scan the array from left to right. If nums[i]=nums[i-1], those two positions cannot both stay. Treat each contiguous run of equal values as one group. A group of length k must lose k-1 elements, and that group contains exactly k-1 adjacent equal pairs. Elements on either side of a group boundary are already different, so keeping one element from each group still leaves unequal neighbors. The minimum number of deletions is the number of adjacent equal pairs.
The time complexity is O(n) and the space complexity is O(1), where n is the length of the array.
class Solution:
def minDeletions(self, nums: list[int]) -> int:
return sum(x == y for x, y in pairwise(nums))class Solution {
public int minDeletions(int[] nums) {
int ans = 0;
for (int i = 1; i < nums.length; ++i) {
if (nums[i] == nums[i - 1]) {
++ans;
}
}
return ans;
}
}class Solution {
public:
int minDeletions(vector<int>& nums) {
int ans = 0;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] == nums[i - 1]) {
++ans;
}
}
return ans;
}
};function minDeletions(nums: number[]): number {
let ans: number = 0;
for (let i = 1; i < nums.length; ++i) {
if (nums[i] === nums[i - 1]) {
++ans;
}
}
return ans;
}func minDeletions(nums []int) (ans int) {
for i := 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
ans++
}
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Stack Rebuild | O(n) | O(n) | When you need the resulting array, not only the count |
| Count Adjacent Equals | O(n) | O(1) | General case and interviews, when only the deletion count is required |
Frequently asked questions
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.