Remove Duplicates from Sorted Array

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k. To get accepted, you need to do the following things:

1. Change the array nums such that the first k elements of nums contain the unique elements in the order they were present initially.
2. The remaining elements of nums are not important as well as the size of nums.
3. Return k.

What to notice first

• The array is sorted, which means duplicates are always consecutive.
• You must modify the array in-place without using extra space for a new array.
• Only the first k elements matter; the rest can contain anything.
• You return k, not the modified array.

Examples

Input	Output	Explanation
[1, 1, 2]	2	Array becomes [1, 2, _]. The first 2 elements are unique.
[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]	5	Array becomes [0, 1, 2, 3, 4, _, _, _, _, _]. The first 5 elements are unique.

Constraints

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

Real-World Applications

Where this pattern appears

• Data deduplication — compacting log entries or sensor data while preserving timestamp order.
• Database operations — removing duplicate records in a pre-sorted result set.
• Memory optimization — compacting memory in embedded systems with limited resources.
• Stream processing — deduplicating sorted events from sensors or IoT devices in-place.

Complexity Comparison

Approach	Time	Space	Modifies Array	Best When
Two Pointers In-Place	O(n)	O(1)	Yes	General case — single pass, no extra memory
Simple Pass	O(n)	O(1)	Yes	Clarity over performance — easier to understand

Which approach should you learn first?

• Pick Two Pointers if you want the optimal, interview-ready solution.
• Pick Simple Pass if you prefer clearer variable naming and explicit logic flow.

Best For Speed

Two Pointers In-Place

O(n) time · O(1) space

Clarity

Simple Pass

O(n) time · O(1) space

Approach 1: Two Pointers In-Place

★ Recommended

Use two pointers: one to read unique elements and one to write them back. Since the array is sorted, duplicates are always consecutive. When we encounter a new unique element, write it to the write pointer and advance it.

The key insight is that we only need to check nums[i] != nums[i - 1]. If true, we found a new unique element and should write it to the position k.

⏱ Time O(n) Single pass 💾 Space O(1) No extra space

Step-by-step Example

Input: nums = [1, 1, 2]

Step	i	nums[i]	nums[i-1]	Same?	Action	k	Array State
Start	-	-	-	-	Initialize	1	[1, 1, 2]
1	1	1	1	✓	Skip, duplicate	1	[1, 1, 2]
2	2	2	1	✗	Write nums[2] to nums[k=1], k++	2	[1, 2, 2]

Return k = 2, array first 2 elements: [1, 2] ✓

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

Step	i	nums[i]	Unique?	Action	k	Progress
Start	-	-	-	Initialize	1	0 at k=0 is unique
1	1	0	No	Skip	1	No change
2	2	1	Yes	Write to k=1, k++	2	[0, 1, ...]
3	3	1	No	Skip	2	No change
4	4	1	No	Skip	2	No change
5	5	2	Yes	Write to k=2, k++	3	[0, 1, 2, ...]
6	6	2	No	Skip	3	No change
7	7	3	Yes	Write to k=3, k++	4	[0, 1, 2, 3, ...]
8	8	3	No	Skip	4	No change
9	9	4	Yes	Write to k=4, k++	5	[0, 1, 2, 3, 4, ...]

Return k = 5 ✓

Animated walkthrough

How the two-pointer approach removes duplicates

Watch the write pointer (k) move forward only when a unique element is found. The read pointer (i) scans through the entire array.

Back Autoplay Next Reset

Step 1 of 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function removeDuplicates(nums):
    if nums is empty:
        return 0

    k = 1  // First element is always unique
    for i from 1 to len(nums) - 1:
        if nums[i] != nums[i - 1]:
            nums[k] = nums[i]
            k = k + 1

    return k

Solution Code

Python

remove_duplicates_from_sorted_array_two_pointer.py

from typing import List


def removeDuplicates(nums: List[int]) -> int:
    """
    Two-Pointer In-Place Approach
    Remove duplicates from sorted array in-place and return the length of the new array.

    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not nums:
        return 0

    k = 1  # First element is always unique
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            nums[k] = nums[i]
            k += 1

    return k


# Test cases
print(removeDuplicates([1, 1, 2]))  # 2, nums = [1, 2, _]
print(removeDuplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]))  # 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

C++

remove_duplicates_from_sorted_array_two_pointer.cpp

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    /*
    Two-Pointer In-Place Approach
    Remove duplicates from sorted array in-place and return the length of the new array.

    Time Complexity: O(n)
    Space Complexity: O(1)
    */
    if (nums.empty()) {
        return 0;
    }

    int k = 1;  // First element is always unique
    for (int i = 1; i < (int)nums.size(); i++) {
        if (nums[i] != nums[i - 1]) {
            nums[k] = nums[i];
            k++;
        }
    }

    return k;
}

int main() {
    std::vector<int> nums1 = {1, 1, 2};
    std::cout << removeDuplicates(nums1) << std::endl;  // 2, nums = [1, 2, _]

    std::vector<int> nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    std::cout << removeDuplicates(nums2) << std::endl;  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

    return 0;
}

Java

remove_duplicates_from_sorted_array_two_pointer.java

public class RemoveDuplicatesFromSortedArrayTwoPointer {
    /*
    Two-Pointer In-Place Approach
    Remove duplicates from sorted array in-place and return the length of the new array.

    Time Complexity: O(n)
    Space Complexity: O(1)
    */
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int k = 1;  // First element is always unique
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 1, 2};
        System.out.println(removeDuplicates(nums1));  // 2, nums = [1, 2, _]

        int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(removeDuplicates(nums2));  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
    }
}

JavaScript

remove_duplicates_from_sorted_array_two_pointer.js

/**
 * Two-Pointer In-Place Approach
 * Remove duplicates from sorted array in-place and return the length of the new array.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * @param {number[]} nums
 * @return {number}
 */
function removeDuplicates(nums) {
    if (nums.length === 0) {
        return 0;
    }

    let k = 1;  // First element is always unique
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1]) {
            nums[k] = nums[i];
            k++;
        }
    }

    return k;
}

// Test cases
console.log(removeDuplicates([1, 1, 2]));  // 2, nums = [1, 2, _]
console.log(removeDuplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]));  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Rust

remove_duplicates_from_sorted_array_two_pointer.rs

/*
Two-Pointer In-Place Approach
Remove duplicates from sorted array in-place and return the length of the new array.

Time Complexity: O(n)
Space Complexity: O(1)
*/
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut k = 1;  // First element is always unique
    for i in 1..nums.len() {
        if nums[i] != nums[i - 1] {
            nums[k] = nums[i];
            k += 1;
        }
    }

    k as i32
}

fn main() {
    let mut nums1 = vec![1, 1, 2];
    println!("{}", remove_duplicates(&mut nums1));  // 2, nums = [1, 2, _]

    let mut nums2 = vec![0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
    println!("{}", remove_duplicates(&mut nums2));  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
}

Go

remove_duplicates_from_sorted_array_two_pointer.go

package main

import "fmt"

/*
Two-Pointer In-Place Approach
Remove duplicates from sorted array in-place and return the length of the new array.

Time Complexity: O(n)
Space Complexity: O(1)
*/
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    k := 1  // First element is always unique
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            nums[k] = nums[i]
            k++
        }
    }

    return k
}

func main() {
    nums1 := []int{1, 1, 2}
    fmt.Println(removeDuplicates(nums1))  // 2, nums = [1, 2, _]

    nums2 := []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
    fmt.Println(removeDuplicates(nums2))  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
}

Approach 2: Simple Pass

✓ Simple

Instead of tracking indices i and k, use explicit readIdx and writeIdx pointers with clearer semantics. This approach is functionally identical to the first but with more descriptive variable names.

⏱ Time O(n) Single pass 💾 Space O(1) No extra space

Step-by-step Example

Input: nums = [1, 1, 2]

readIdx	writeIdx	nums[readIdx]	nums[writeIdx]	Action	Result
Start	0	-	1	Initialize pointers	-
1	0	1	1	Equal, skip	No change
2	0	2	1	Different, write nums[2] to nums[1], writeIdx++	[1, 2, _]

Return writeIdx + 1 = 2 ✓

Pseudocode

function removeDuplicates(nums):
    if nums is empty:
        return 0

    writeIdx = 0
    for readIdx from 1 to len(nums) - 1:
        if nums[readIdx] != nums[writeIdx]:
            writeIdx = writeIdx + 1
            nums[writeIdx] = nums[readIdx]

    return writeIdx + 1

Solution Code

Python

remove_duplicates_from_sorted_array_simple.py

from typing import List


def removeDuplicates(nums: List[int]) -> int:
    """
    Simple Pass Approach
    Remove duplicates by iterating and comparing consecutive elements.

    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not nums:
        return 0

    write_idx = 0
    for read_idx in range(1, len(nums)):
        if nums[read_idx] != nums[write_idx]:
            write_idx += 1
            nums[write_idx] = nums[read_idx]

    return write_idx + 1


# Test cases
print(removeDuplicates([1, 1, 2]))  # 2, nums = [1, 2, _]
print(removeDuplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]))  # 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

C++

remove_duplicates_from_sorted_array_simple.cpp

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    /*
    Simple Pass Approach
    Remove duplicates by iterating and comparing consecutive elements.

    Time Complexity: O(n)
    Space Complexity: O(1)
    */
    if (nums.empty()) {
        return 0;
    }

    int write_idx = 0;
    for (int read_idx = 1; read_idx < (int)nums.size(); read_idx++) {
        if (nums[read_idx] != nums[write_idx]) {
            write_idx++;
            nums[write_idx] = nums[read_idx];
        }
    }

    return write_idx + 1;
}

int main() {
    std::vector<int> nums1 = {1, 1, 2};
    std::cout << removeDuplicates(nums1) << std::endl;  // 2, nums = [1, 2, _]

    std::vector<int> nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    std::cout << removeDuplicates(nums2) << std::endl;  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

    return 0;
}

Java

remove_duplicates_from_sorted_array_simple.java

public class RemoveDuplicatesFromSortedArraySimple {
    /*
    Simple Pass Approach
    Remove duplicates by iterating and comparing consecutive elements.

    Time Complexity: O(n)
    Space Complexity: O(1)
    */
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int writeIdx = 0;
        for (int readIdx = 1; readIdx < nums.length; readIdx++) {
            if (nums[readIdx] != nums[writeIdx]) {
                writeIdx++;
                nums[writeIdx] = nums[readIdx];
            }
        }

        return writeIdx + 1;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 1, 2};
        System.out.println(removeDuplicates(nums1));  // 2, nums = [1, 2, _]

        int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(removeDuplicates(nums2));  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
    }
}

JavaScript

remove_duplicates_from_sorted_array_simple.js

/**
 * Simple Pass Approach
 * Remove duplicates by iterating and comparing consecutive elements.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * @param {number[]} nums
 * @return {number}
 */
function removeDuplicates(nums) {
    if (nums.length === 0) {
        return 0;
    }

    let writeIdx = 0;
    for (let readIdx = 1; readIdx < nums.length; readIdx++) {
        if (nums[readIdx] !== nums[writeIdx]) {
            writeIdx++;
            nums[writeIdx] = nums[readIdx];
        }
    }

    return writeIdx + 1;
}

// Test cases
console.log(removeDuplicates([1, 1, 2]));  // 2, nums = [1, 2, _]
console.log(removeDuplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]));  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Rust

remove_duplicates_from_sorted_array_simple.rs

/*
Simple Pass Approach
Remove duplicates by iterating and comparing consecutive elements.

Time Complexity: O(n)
Space Complexity: O(1)
*/
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut write_idx = 0;
    for read_idx in 1..nums.len() {
        if nums[read_idx] != nums[write_idx] {
            write_idx += 1;
            nums[write_idx] = nums[read_idx];
        }
    }

    (write_idx + 1) as i32
}

fn main() {
    let mut nums1 = vec![1, 1, 2];
    println!("{}", remove_duplicates(&mut nums1));  // 2, nums = [1, 2, _]

    let mut nums2 = vec![0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
    println!("{}", remove_duplicates(&mut nums2));  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
}

Go

remove_duplicates_from_sorted_array_simple.go

package main

import "fmt"

/*
Simple Pass Approach
Remove duplicates by iterating and comparing consecutive elements.

Time Complexity: O(n)
Space Complexity: O(1)
*/
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    writeIdx := 0
    for readIdx := 1; readIdx < len(nums); readIdx++ {
        if nums[readIdx] != nums[writeIdx] {
            writeIdx++
            nums[writeIdx] = nums[readIdx]
        }
    }

    return writeIdx + 1
}

func main() {
    nums1 := []int{1, 1, 2}
    fmt.Println(removeDuplicates(nums1))  // 2, nums = [1, 2, _]

    nums2 := []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
    fmt.Println(removeDuplicates(nums2))  // 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
}

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

remove_duplicates_from_sorted_array_optimized.py

"""
Solution for Remove Duplicates from Sorted Array
"""

def solve():
    """Implementation for approach 3 of Remove Duplicates from Sorted Array"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

remove_duplicates_from_sorted_array_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Remove Duplicates from Sorted Array
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

RemoveDuplicatesFromSortedArrayOptimized.java

/**
 * Solution for Remove Duplicates from Sorted Array
 * Approach 3
 */
public class RemoveDuplicatesFromSortedArrayOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

remove_duplicates_from_sorted_array_optimized.js

/**
 * Solution for Remove Duplicates from Sorted Array
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

remove_duplicates_from_sorted_array_optimized.rs

/// Solution for Remove Duplicates from Sorted Array
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

remove_duplicates_from_sorted_array_optimized.go

package main

import "fmt"

// Solution for Remove Duplicates from Sorted Array
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Not realizing the array is sorted. The fact that duplicates are consecutive is critical to this algorithm’s O(1) space complexity.
• Forgetting that only the first k elements matter. Many beginners try to delete or shift elements, which wastes time and space.
• Off-by-one errors. Remember that k starts at 1 (the first element is always unique) and we return k, not k - 1.
• Modifying comparison. Always compare with the previous element (nums[i] != nums[i - 1]), not with writeIdx.

Related Problems

• Remove Element ↗ Easy #27
• Remove Duplicates from Sorted Array II ↗ Medium #80
• Move Zeroes ↗ Easy #283
• Reverse Nodes in k-Group ↗ Hard #25

Interview Tips

Key trade-offs to discuss

• Why two pointers? Because the array is already sorted. If it were unsorted, we would need a hash set (O(n) space) or sorting first (O(n log n) time).
• Why in-place modification? This is explicitly required by the problem. It tests whether you understand memory constraints.
• Edge cases: Single element (return 1), all duplicates (return 1), all unique (return n).
• Follow-ups to expect:
  • “What if duplicates can appear up to k times?” (Problem 80)
  • “What if we need to preserve the original indices?” (Different problem entirely)
  • “Can you do this without modifying the array?” (No, because the problem requires in-place modification)

← Previous
#25 Reverse Nodes in k-Group Next
#27 Remove Element →