Remove Duplicates from Sorted Array ii Solution - Leetcode
Understand Remove Duplicates from sorted array ii (80 Leetcode) with Solution
28
October 2025
This document presents the solution to the problem 80. Remove Duplicates from Sorted Array II - Leetcode.
Known Information
- Array is sorted in non decreasing order i.e, ~ascending order
- An element can appear 1 or multiple times.
- If an element appears 3 times, the last entry will be marked as duplicate.
- Duplicate count per element = Total count per element - 2
Requirements
- Push the duplicate elements to the right so that an element is appears atmost 2 times.
- For example,
[1, 1, 1, 2]becomes[1, 1, 2, 1]- The duplicate
1is moved to the right
- The duplicate
- Return the count of non duplicate elements.
Solution
- States to maintain
current- current element in the loopcurrentCount- the number of times the current element is found consecutivelyduplicateStartIndex&duplicateEndIndex- continuous range inside the array that holds the duplicate element
The solution involes:
- figuring out the duplicate elements, and,
- continuosly partioning the array between duplicate and non-duplicate elements
- with non-duplicate elements being moved from right to left
- while keeping the duplicate elements on the right side of the array
Initial State
- We initialize all the state variables:
current: -1currentCount: -1duplicateStartIndex: -1duplicateEndIndex: -1
1st Iteration:
- We find
idxpointing to value0which is @ index 0.
currentcontains0andcurrentCountbecomes1.duplicateStartIndexandduplicateEndIndexremain uninitialized because no duplicates have been found.
2nd Iteration:
currentremains0and we increment thecurrentCountto2because0has been found twice consecutively.
3rd Iteration:
currentupdates to1withcurrentCountupdating to1. We’ve not found any duplicates until now.
4th Iteration:
currentremains1withcurrentCountupdating to2. We’ve not found any duplicates until now.
5th Iteration:
currentremains1withcurrentCountupdating to3. We’ve found the first duplicate element.duplicateStartIndexandduplicateEndIndexpoint to 4th index of thenumsarray
6th Iteration:
currentremains1withcurrentCountupdating to4. We’ve found the 2nd duplicate element.duplicateEndIndexpoint to 5th index of thenumsarray
7th Iteration:
currentbecomes2withcurrentCountupdating to1.- Since duplicate element range is available and we swap current element with elemnt @
duplicateStartIndex
- After swapping, we increment
duplicateStartIndexandduplicateEndIndexto point the correct range of elements containing the duplicate elements.
8th Iteration:
currentremains2withcurrentCountupdating to2.- The current element is considered a non duplicate element, so we swap just like the previous step
- Since duplicate element range is available and we swap current element with elemnt @
duplicateStartIndex
- And, update the range pointers,
duplicateStartIndexandduplicateEndIndex:
11th Iteration
- Here’s the final snapshot containing the state variables and the array after reaching the end of the array
Exit Conditions
- The loop should exit after the last element has been taken care of.
Please do provide some comments if you find the explanation a bit lacking.
func removeDuplicates(nums []int) int {
current := -1
currentCount := 0
duplicateStartIndex := -1
duplicateEndIndex := -1
for idx, num := range nums {
if num != current {
current = num
currentCount = 1
} else if num == current {
currentCount++
}
if currentCount > 2 {
if duplicateStartIndex == -1 {
duplicateStartIndex = idx
duplicateEndIndex = idx
} else {
duplicateEndIndex = idx
}
} else if currentCount <= 2 && duplicateStartIndex != -1 {
swap(nums, idx, duplicateStartIndex)
duplicateStartIndex++
duplicateEndIndex++
}
if idx == len(nums)-1 {
if duplicateStartIndex != -1 {
return len(nums) - (duplicateEndIndex - duplicateStartIndex + 1)
}
return len(nums)
}
}
return 0
}
func swap(nums []int, i, j int) {
temp := nums[i]
nums[i] = nums[j]
nums[j] = temp
}
Loading Comments...
