Mastering 'Remove Duplicates from Sorted Array': The Ultimate Multi-Language Masterclass

In technical interviews, particularly at tier-one tech firms like Apple, Google, and Meta, array manipulation questions are highly favored. Among these, LeetCode 26: Remove Duplicates from Sorted Array is a foundational classic. It tests a developer's ability to reason about memory efficiency, space constraints, and in-place array transformations.

At first glance, removing duplicates seems trivial if you can allocate extra memory. However, when constrained to an in-place modification with O(1) auxiliary space, the problem demands a rigorous structural understanding of array indexing. In this comprehensive guide, we will analyze the underlying architecture of this problem, design an optimal algorithm using the Two-Pointer pattern, and write robust, production-ready solutions in every major programming language supported by LeetCode.

Understanding the Problem and Its Strict Constraints

The problem description states: 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 must be kept the same. Then return the number of unique elements in nums.

To do this, you must modify the array such that the first k elements of nums contain the unique elements in the order they were initially present in nums. The remaining elements of nums do not matter, nor does the size of the final array.

The Concept of "In-Place" Array Modification

In-place computation means changing the input data structure directly without dedicating a new copy. Many developers are tempted to construct a temporary Set or a secondary array to filter duplicates. While this yields an intuitive $O(N)$ time solution, it violates the $O(1)$ space constraint by allocating $O(N)$ extra memory on the heap. In production-grade software, avoiding extra heap allocations is critical for minimizing garbage collection pauses and maximizing CPU cache locality.

Key Invariant: Since the input array is already sorted, all duplicate values are guaranteed to be contiguous. This single physical property allows us to solve the problem without tracking visited elements in a hash map.

---

The Architecture of the Two-Pointer Algorithm

The optimal approach to this problem utilizes a linear-scan technique known as the Two-Pointer Strategy. We maintain two pointers moving through the array at different speeds:

• Write Pointer (writeIndex): Tracks the position where the next unique element should be written. Since the first element (at index 0) is always unique relative to itself, we initialize this pointer to index 1.

• Read Pointer (readIndex): Iterates through the array starting from index 1 to inspect every element.

Visualizing the Execution Trace

Consider the input array: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4].

Initial State:
[ 0,  0,  1,  1,  1,  2,  2,  3,  3,  4 ]
  |   |
  |   +-- readIndex = 1
  +------ writeIndex = 1

- nums[readIndex] (0) == nums[readIndex-1] (0): Duplicate detected! Move readIndex forward.

[ 0,  0,  1,  1,  1,  2,  2,  3,  3,  4 ]
  |       |
  |       +-- readIndex = 2
  +---------- writeIndex = 1

- nums[readIndex] (1) != nums[readIndex-1] (0): Unique element found!
  Copy nums[readIndex] to nums[writeIndex].
  Increment writeIndex.

[ 0,  1,  1,  1,  1,  2,  2,  3,  3,  4 ]
      |   |
      |   +-- readIndex = 3
      +------ writeIndex = 2

This scanning pattern guarantees that the prefix nums[0...writeIndex-1] is always sorted and contains strictly unique values.

---

Production-Grade Implementations in All LeetCode Languages

We present clean, optimized, and idiomatic implementations for the key programming languages supported by LeetCode. Each codebase follows strict static-typing rules (where applicable) and idiomatic syntax.

1. Python 3

Python's slicing mechanisms are highly expressive, but to modify the array in place, we iterate through indices directly to maintain optimal memory boundaries.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        if not nums:
            return 0
        
        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

2. Java

Java relies on primitive array manipulations. We avoid boxing-unboxing and any virtual method dispatches to guarantee low latency.

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int writeIndex = 1;
        for (int readIndex = 1; readIndex < nums.length; readIndex++) {
            if (nums[readIndex] != nums[readIndex - 1]) {
                nums[writeIndex] = nums[readIndex];
                writeIndex++;
            }
        }
        return writeIndex;
    }
}

3. C++

In C++, we accept a reference to a std::vector. We use size_t for indexing to prevent signs-mismatch warnings during loop iterations.

#include <vector>

class Solution {
public:
    int removeDuplicates(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        size_t writeIndex = 1;
        for (size_t readIndex = 1; readIndex < nums.size(); ++readIndex) {
            if (nums[readIndex] != nums[readIndex - 1]) {
                nums[writeIndex] = nums[readIndex];
                writeIndex++;
            }
        }
        return static_cast<int>(writeIndex); 
    }
};

4. JavaScript (ES6+)

JavaScript arrays are dynamic, but we manipulate them using raw indices to optimize V8's internal optimization loops, preventing the array from degrading to dictionary mode.

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;
    
    let writeIndex = 1;
    for (let readIndex = 1; readIndex < nums.length; readIndex++) {
        if (nums[readIndex] !== nums[readIndex - 1]) {
            nums[writeIndex] = nums[readIndex];
            writeIndex++;
        }
    }
    return writeIndex;
};

5. TypeScript

TypeScript ensures type safety. We leverage clean type annotations while matching JavaScript's runtime efficiency.

function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0;
    
    let writeIndex: number = 1;
    for (let readIndex: number = 1; readIndex < nums.length; readIndex++) {
        if (nums[readIndex] !== nums[readIndex - 1]) {
            nums[writeIndex] = nums[readIndex];
            writeIndex++;
        }
    }
    return writeIndex;
}

6. Go

Go emphasizes simplicity and performance. Slices behave as windows into underlying arrays; modifying slice elements modifies the storage array directly.

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

7. Rust

Rust enforces strict memory-safety rules. We access the mutable vector index directly inside safe boundaries.

impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }
        
        let mut write_index = 1;
        for read_index in 1..nums.len() {
            if nums[read_index] != nums[read_index - 1] { 
                nums[write_index] = nums[read_index];
                write_index += 1;
            }
        }
        write_index as i32
    } 
}

8. C#

In C#, arrays are objects on the managed heap. We write a clean procedural loop targeting .NET runtime optimization.

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if (nums == null || nums.Length == 0) return 0;
        
        int writeIndex = 1;
        for (int readIndex = 1; readIndex < nums.Length; readIndex++) {
            if (nums[readIndex] != nums[readIndex - 1]) {
                nums[writeIndex] = nums[readIndex];
                writeIndex++;
            }
        }
        return writeIndex;
    }
}

9. Swift

Swift arrays require inout parameters to allow mutations in-place when passed to functions.

class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        if nums.isEmpty { return 0 }
        
        var writeIndex = 1
        for readIndex in 1..<nums.count {
            if nums[readIndex] != nums[readIndex - 1] {
                nums[writeIndex] = nums[readIndex]
                writeIndex += 1
            }
        }
        return writeIndex
    }
}

10. Kotlin

Kotlin leverages standard library structures. For performance, we run explicit integer loops directly over index ranges.

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

---

Complexity Analysis

Understanding computational complexity is crucial to getting through system-level and low-level algorithmic interviews. Let's analyze the performance profile of our Two-Pointer solution:

Time Complexity: $O(N)$

We make exactly one pass through the input array of size $N$. Inside the loop, every operation—including element comparison, value copying, and index pointer increment—is an $O(1)$ constant-time instruction. Hence, the overall time grows linearly with the size of the array.

Space Complexity: $O(1)$

No auxiliary space is allocated on the heap or stack that scales with the size of the input array. We only track state using simple primitive variables (the loop counters and write pointers), ensuring constant space complexity.

Spatial Locality and Cache Efficiency

The Two-Pointer approach reads and writes memory in a purely sequential manner. Modern CPU microarchitectures utilize prefetching engines that load sequential blocks of memory into high-speed Level 1 (L1) and Level 2 (L2) caches. Because we do not perform random memory accesses (unlike node-based structures like lists or trees), our solution exhibits exceptionally high cache hit rates, maximizing hardware efficiency.

---

Edge Cases and Pitfalls to Avoid

When implementing solutions under high-pressure interview conditions, watch out for the following critical edge cases:

• Empty Input Array: Ensure you have guard clauses returning 0 immediately if the array is empty. Accessing index 0 without checking can trigger array boundary exceptions (e.g., ArrayIndexOutOfBoundsException in Java or undefined behavior in C++).

• Single Element Arrays: When nums.length == 1, our algorithm must bypass the loop and return 1 smoothly without processing errors.

• No Duplicates Present: For arrays containing strictly unique elements (e.g., [1, 2, 3, 4]), the algorithm performs unnecessary self-assignments (copying values onto themselves). While this keeps the algorithm simple, it operates correctly.

---

Summary & Takeaways

The Two-Pointer Technique is a vital strategy for optimizing sequence-traversal algorithms. By utilizing the sorted state of the data, we decoupled reading from writing and executed the deduplication filter in a single linear sweep.

When tackling in-place challenges in the future, remember to verify data constraints, prioritize CPU-cache-friendly continuous memory transformations, and establish strict index boundary safeguards.