26 Remove Duplicates from Sorted Array

Description

You are given a list of integers that is already sorted in ascending order. Your task is to remove the duplicate values in-place, so that each number appears only once and the order of the elements remains the same.

The operation should be done without allocating another array. After removing duplicates, return the number of unique elements. The first k elements of the array should contain these unique values.

Any leftover elements beyond the k-th position don’t matter — they can be left as-is or ignored.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

---

Example 1

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

---

Example 2

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k.

---

Constraints

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

---

Initialize a pointer idx to track where the next unique element should go. Start at 1 because the first element is always unique. Start looping from the second element, if the current element is different from the previous one, it's a new unique number. Place this unique number at idx, overwriting duplicates, and move idx forward.

Java

class Solution {
    public int removeDuplicates(int[] nums) {
        var idx = 1;
        for(var i = 1; i < nums.length; i++) {
            if(nums[i] != nums[i-1]) {
                nums[idx++] = nums[i];
            }  
        }
        return idx;
    }
}

Kotlin

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        var idx = 1
        for(i in 1 until nums.size) {
            if(nums[i] != nums[i-1]) {
                nums[idx++] = nums[i]
            }
        }
        return idx++
    }
}

Scala

object Solution {
    def removeDuplicates(nums: Array[Int]): Int = {
        var idx = 1
        for(i <- 1 until nums.length) {
            if(nums(i) != nums(i-1)) {
                nums(idx) = nums(i)
                idx += 1
            }
        }
        return idx
    }
}

Time Complexity: O(n)
Space Complexity: O(1)