Algorithm Day112 - Remove Duplicates from Sorted Array (lc-26)

Posted on In , Views:

LC-26 Remove Duplicates from Sorted Array

📌 Problem

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length. Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.

💬 Examples

Example 1

1
2
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

Example 2

1
2
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

💡 Intuition (Two Pointers)

Because the array is sorted, duplicates are adjacent. Use two pointers — slow and fast:

  • slow tracks the position to write the next unique element (starts at 0).
  • fast scans the array from 1 to end.
  • When nums[fast] != nums[slow], increment slow and copy nums[fast] to nums[slow].

After the loop, the new length is slow + 1.

🔢 Java Code (Two Pointers)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int slow = 0;
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

⏱ Complexity Analysis

  • Time: O(n) — single pass through the array.
  • Space: O(1) — in-place, constant extra space.

✍️ Summary

  • Use two pointers on a sorted array to overwrite duplicates.
  • After processing, first k elements are the unique values where k = slow + 1.
  • Very common in interviews — demonstrates in-place array manipulation and two-pointer technique.