LeetCode Problem 26

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Remove Duplicates from Sorted Array

Problem Understanding

The problem gives us a sorted integer array nums in non-decreasing order. Because the array is already sorted, any duplicate values will always appear next to each other. Our task is to remove duplicate values in-place so that each distinct number appears exactly once at the beginning of the array.

The phrase "in-place" is important. We are not supposed to allocate another array and return it. Instead, we must modify the existing array directly. After modification, the first k elements of nums should contain all unique values in sorted order, where k is the number of distinct elements.

The function should return k, not the modified array itself. The values after index k - 1 do not matter because the judge only checks the first k positions.

For example, if the input is:

[0,0,1,1,1,2,2,3,3,4]

then after processing, the array should begin with:

[0,1,2,3,4]

and the function should return 5.

The constraints tell us several useful things:

• The array length can be as large as 3 * 10^4
• The array is guaranteed to be sorted
• Values range from -100 to 100

The most important guarantee is that the array is sorted. Without sorting, identifying duplicates efficiently would require additional data structures like a hash set. Because duplicates are adjacent, we can solve the problem using two pointers and constant extra space.

Several edge cases are important:

• An array with only one element, such as [5]
• An array where all elements are identical, such as [2,2,2,2]
• An array with no duplicates, such as [1,2,3,4]
• Arrays containing negative numbers
• Arrays where duplicates appear many times consecutively

A naive implementation can easily make indexing mistakes, especially when updating elements in-place.

Approaches

Brute Force Approach

A straightforward solution is to create a separate array that stores only unique values. We iterate through the original array and append a number whenever it differs from the previous number.

After collecting all unique values, we copy them back into the original array and return the count.

This approach is correct because the sorted order guarantees that duplicates are adjacent. By comparing each element with the previous one, we can determine whether it is a new unique value.

The main drawback is the extra memory usage. The problem explicitly asks for an in-place solution, so allocating another array violates the spirit of the requirement.

Optimal Approach

The key observation is that since the array is sorted, duplicates always appear consecutively. That means we only need to keep track of where the next unique value should be written.

We use two pointers:

• A read pointer scans through the array
• A write pointer tracks the position where the next unique element should be placed

Whenever we encounter a new unique value, we write it at the write pointer position and move the write pointer forward.

This works efficiently because every unique element is copied at most once, and duplicates are skipped naturally.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Uses an extra array to store unique values
Optimal	O(n)	O(1)	Uses two pointers and modifies the array in-place

Algorithm Walkthrough

1. Start by handling the simplest case. If the array has only one element, the answer is immediately 1 because there cannot be duplicates.
2. Initialize a write pointer at index 1. The first element is always unique, so we keep it in place.
3. Iterate through the array starting from index 1 using a read pointer.
4. For each element, compare it with the previous element:

• If the current value is different, it is a new unique number.
• Write this value into the position indicated by the write pointer.
• Increment the write pointer.

5. If the current value is the same as the previous value, it is a duplicate, so skip it.
6. After the loop finishes, the write pointer represents the total number of unique elements.
7. Return the write pointer value.

Why it works

The algorithm maintains an important invariant:

• The subarray from index 0 to write_pointer - 1 always contains only unique elements in sorted order.

Because the array is sorted, duplicates appear consecutively. Comparing each element with the previous one is sufficient to determine whether it is unique. Every time we find a new unique value, we place it immediately after the last unique value already stored.

By the end of the traversal, all unique values have been compacted into the front portion of the array.

Python Solution

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1

        write_index = 1

        for read_index in range(1, len(nums)):
            if nums[read_index] != nums[read_index - 1]:
                nums[write_index] = nums[read_index]
                write_index += 1

        return write_index

The implementation begins by checking whether the array contains only one element. In that case, the result is immediately 1.

The variable write_index tracks the position where the next unique value should be written. Since the first element is always unique, it starts at index 1.

The loop uses read_index to scan through the array from left to right. At each step, the current element is compared with the previous element.

If the values differ, we have discovered a new unique number. That value is copied into the position indicated by write_index, and then write_index is incremented.

If the values are equal, the element is a duplicate and is ignored.

Finally, the function returns write_index, which equals the number of unique elements stored at the beginning of the array.

Go Solution

func removeDuplicates(nums []int) int {
    if len(nums) == 1 {
        return 1
    }

    writeIndex := 1

    for readIndex := 1; readIndex < len(nums); readIndex++ {
        if nums[readIndex] != nums[readIndex-1] {
            nums[writeIndex] = nums[readIndex]
            writeIndex++
        }
    }

    return writeIndex
}

The Go implementation follows the same logic as the Python version. Slices in Go are mutable, so modifying nums directly updates the original array.

Unlike some languages, Go does not distinguish between arrays and slices in the same way Python handles lists. The slice is passed by reference-like behavior, so in-place modification works naturally.

There are no integer overflow concerns here because indices remain within the bounds of the array size constraints.

Worked Examples

Example 1

Input:

nums = [1,1,2]

Initial state:

Step	read_index	write_index	nums
Start	-	1	[1,1,2]

Iteration 1:

• nums[1] = 1
• nums[0] = 1
• Duplicate found, skip it

Step	read_index	write_index	nums
After iteration	1	1	[1,1,2]

Iteration 2:

• nums[2] = 2
• nums[1] = 1
• New unique value found
• Write 2 at index 1

Step	read_index	write_index	nums
After iteration	2	2	[1,2,2]

Return value:

2

The first two elements are:

[1,2]

Example 2

Input:

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

Initial state:

Step	read_index	write_index	nums
Start	-	1	[0,0,1,1,1,2,2,3,3,4]

Iteration details:

read_index	Current Value	Action	write_index After	Array State
1	0	Duplicate, skip	1	[0,0,1,1,1,2,2,3,3,4]
2	1	Write at index 1	2	[0,1,1,1,1,2,2,3,3,4]
3	1	Duplicate, skip	2	[0,1,1,1,1,2,2,3,3,4]
4	1	Duplicate, skip	2	[0,1,1,1,1,2,2,3,3,4]
5	2	Write at index 2	3	[0,1,2,1,1,2,2,3,3,4]
6	2	Duplicate, skip	3	[0,1,2,1,1,2,2,3,3,4]
7	3	Write at index 3	4	[0,1,2,3,1,2,2,3,3,4]
8	3	Duplicate, skip	4	[0,1,2,3,1,2,2,3,3,4]
9	4	Write at index 4	5	[0,1,2,3,4,2,2,3,3,4]

Final result:

k = 5

The first five elements are:

[0,1,2,3,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is visited exactly once
Space	O(1)	Only a few pointer variables are used

The algorithm performs a single pass through the array, so the runtime grows linearly with the number of elements.

No extra data structures proportional to the input size are allocated. The array is modified directly in-place, which gives constant auxiliary space usage.

Test Cases

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1

        write_index = 1

        for read_index in range(1, len(nums)):
            if nums[read_index] != nums[read_index - 1]:
                nums[write_index] = nums[read_index]
                write_index += 1

        return write_index

solution = Solution()

nums = [1, 1, 2]
k = solution.removeDuplicates(nums)
assert k == 2  # basic duplicate removal
assert nums[:k] == [1, 2]

nums = [0,0,1,1,1,2,2,3,3,4]
k = solution.removeDuplicates(nums)
assert k == 5  # multiple duplicate groups
assert nums[:k] == [0,1,2,3,4]

nums = [1]
k = solution.removeDuplicates(nums)
assert k == 1  # single element array
assert nums[:k] == [1]

nums = [1,2,3,4]
k = solution.removeDuplicates(nums)
assert k == 4  # no duplicates
assert nums[:k] == [1,2,3,4]

nums = [2,2,2,2]
k = solution.removeDuplicates(nums)
assert k == 1  # all elements identical
assert nums[:k] == [2]

nums = [-3,-3,-2,-1,-1,0]
k = solution.removeDuplicates(nums)
assert k == 4  # negative numbers included
assert nums[:k] == [-3,-2,-1,0]

nums = [1,1,1,2,2,3]
k = solution.removeDuplicates(nums)
assert k == 3  # repeated duplicate blocks
assert nums[:k] == [1,2,3]

Test	Why
[1,1,2]	Verifies basic duplicate removal
[0,0,1,1,1,2,2,3,3,4]	Tests multiple duplicate groups
[1]	Validates single-element edge case
[1,2,3,4]	Confirms behavior when no duplicates exist
[2,2,2,2]	Ensures all-identical arrays are handled correctly
[-3,-3,-2,-1,-1,0]	Verifies negative values work properly
[1,1,1,2,2,3]	Tests long consecutive duplicate sequences

Edge Cases

Single Element Array

An array containing only one element is the smallest valid input. A careless implementation might incorrectly initialize pointers or attempt to access out-of-range indices.

For example:

[5]

The implementation handles this immediately by returning 1 before entering the loop.

All Elements Identical

When every value is the same, the algorithm should keep only one copy.

Example:

[2,2,2,2]

A buggy implementation might continue overwriting values unnecessarily or return the wrong count. The current solution correctly skips every duplicate and returns 1.

No Duplicates

If the array already contains unique values, the algorithm should leave the array unchanged.

Example:

[1,2,3,4]

Every comparison identifies a new unique value, so each element is copied into its own position. The returned value equals the original array length.

Negative Numbers

The problem allows negative integers, so comparisons must work correctly regardless of sign.

Example:

[-5,-5,-2,-1]

Since the algorithm only relies on equality comparison and sorted ordering, negative values are handled naturally without any special logic.