Remove Duplicates from Sorted Array

🎯

Remove Duplicates from Sorted Array

easyTWO_POINTERAmazonFacebookMicrosoft

Imagine you have a sorted list of customer IDs and want to keep only unique IDs to avoid duplicate processing.

💡 This problem teaches how to efficiently remove duplicates from a sorted array in-place. Beginners often struggle with in-place modifications and understanding how two pointers can help traverse and modify arrays simultaneously.

📋

Problem Statement

Given a sorted integer array nums, remove the duplicates in-place such that each element appears only once and returns 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.

1 ≤ nums.length ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4nums is sorted in non-decreasing order

💡

Example

Input"[1,1,2]"

Output2

After removing duplicates, the first two elements are [1,2]. The function returns length 2.

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

Output5

After removing duplicates, the first five elements are [0,1,2,3,4]. The function returns length 5.

• Array with all unique elements → length remains same
• Array with all identical elements → length is 1
• Array with two elements both duplicates → length is 1
• Array with single element → length is 1

⚠️

Common Mistakes

Not handling empty array input

Code throws index out of range error

✅ Add early return if array length is zero

Incrementing slow pointer incorrectly

Overwrites unique elements or skips duplicates

✅ Only increment slow pointer when a new unique element is found

Using extra space like another array

Fails in-place constraint, may be rejected in interviews

✅ Modify input array in-place using two pointers

Not returning correct length

Leads to incorrect output or partial results

✅ Return slow pointer index + 1 as the new length

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by explicitly checking each element against all others, showing why naive methods are inefficient.

Intuition

For each element, scan the rest of the array to check if it is a duplicate and remove it by shifting elements left.

Algorithm

1. Start from the first element and compare it with every other element to the right.
2. If a duplicate is found, shift all subsequent elements one position to the left.
3. Reduce the array length by one after each removal.
4. Repeat until all duplicates are removed.

💡 This algorithm is straightforward but inefficient because it repeatedly shifts elements, which is costly.

</>

Code

def remove_duplicates(nums):
    n = len(nums)
    i = 0
    while i < n:
        j = i + 1
        while j < n:
            if nums[j] == nums[i]:
                for k in range(j, n - 1):
                    nums[k] = nums[k + 1]
                n -= 1
            else:
                j += 1
        i += 1
    return n

# Driver code
if __name__ == '__main__':
    arr = [0,0,1,1,1,2,2,3,3,4]
    length = remove_duplicates(arr)
    print(length)  # Expected: 5
    print(arr[:length])  # Expected: [0,1,2,3,4]

Line Notes

n = len(nums)Store original length to track array size as we remove duplicates

while i < n:Outer loop picks each element to compare against others

if nums[j] == nums[i]:Check if current element is a duplicate

for k in range(j, n - 1):Shift elements left to overwrite duplicate

n -= 1Reduce effective array size after removal

else: j += 1Only advance j if no removal to avoid skipping elements

return nReturn new length after all duplicates removed

public class Solution {
    public static int removeDuplicates(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n) {
                if (nums[j] == nums[i]) {
                    for (int k = j; k < n - 1; k++) {
                        nums[k] = nums[k + 1];
                    }
                    n--;
                } else {
                    j++;
                }
            }
            i++;
        }
        return n;
    }

    public static void main(String[] args) {
        int[] arr = {0,0,1,1,1,2,2,3,3,4};
        int length = removeDuplicates(arr);
        System.out.println(length); // Expected: 5
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Line Notes

int n = nums.length;Keep track of current array length as duplicates are removed

while (i < n) {Outer loop selects each element for comparison

if (nums[j] == nums[i]) {Detect duplicate element

for (int k = j; k < n - 1; k++) {Shift elements left to overwrite duplicate

n--;Decrease array size after removal

else { j++; }Advance j only if no removal to avoid skipping elements

return n;Return new length after processing

#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int j = i + 1;
        while (j < n) {
            if (nums[j] == nums[i]) {
                for (int k = j; k < n - 1; k++) {
                    nums[k] = nums[k + 1];
                }
                n--;
            } else {
                j++;
            }
        }
        i++;
    }
    return n;
}

int main() {
    vector<int> arr = {0,0,1,1,1,2,2,3,3,4};
    int length = removeDuplicates(arr);
    cout << length << endl; // Expected: 5
    for (int i = 0; i < length; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

int n = nums.size();Track current size of array as duplicates are removed

while (i < n) {Outer loop picks each element to compare

if (nums[j] == nums[i]) {Check for duplicate element

for (int k = j; k < n - 1; k++) {Shift elements left to overwrite duplicate

n--;Reduce array size after removal

else { j++; }Advance j only if no removal to avoid skipping elements

return n;Return new length after all duplicates removed

function removeDuplicates(nums) {
    let n = nums.length;
    let i = 0;
    while (i < n) {
        let j = i + 1;
        while (j < n) {
            if (nums[j] === nums[i]) {
                for (let k = j; k < n - 1; k++) {
                    nums[k] = nums[k + 1];
                }
                n--;
            } else {
                j++;
            }
        }
        i++;
    }
    return n;
}

// Driver code
const arr = [0,0,1,1,1,2,2,3,3,4];
const length = removeDuplicates(arr);
console.log(length); // Expected: 5
console.log(arr.slice(0, length)); // Expected: [0,1,2,3,4]

Line Notes

let n = nums.length;Store current array length to track removals

while (i < n) {Outer loop selects each element for duplicate check

if (nums[j] === nums[i]) {Detect duplicate element

for (let k = j; k < n - 1; k++) {Shift elements left to overwrite duplicate

n--;Decrease array length after removal

else { j++; }Advance j only if no removal to avoid skipping elements

return n;Return new length after duplicates removed

⏱

Complexity

TimeO(n^2)

SpaceO(1)

For each element, we scan the rest of the array and shift elements on duplicates, leading to quadratic time.

💡 For n=20, this means roughly 400 operations, which is inefficient for large arrays.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Two Pointers - Basic

💡 This approach introduces the two-pointer technique to efficiently remove duplicates by overwriting duplicates in-place.

Intuition

Use one pointer to track the position of the last unique element and another to scan through the array, copying unique elements forward.

Algorithm

1. Initialize two pointers: slow at 0 and fast at 1.
2. Iterate fast through the array.
3. If nums[fast] != nums[slow], increment slow and copy nums[fast] to nums[slow].
4. Return slow + 1 as the new length.

💡 This algorithm efficiently overwrites duplicates by only moving unique elements forward.

</>

Code

def remove_duplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# Driver code
if __name__ == '__main__':
    arr = [0,0,1,1,1,2,2,3,3,4]
    length = remove_duplicates(arr)
    print(length)  # Expected: 5
    print(arr[:length])  # Expected: [0,1,2,3,4]

Line Notes

if not nums:Handle empty array edge case immediately

slow = 0Initialize slow pointer to track last unique element

for fast in range(1, len(nums))Fast pointer scans through array

if nums[fast] != nums[slow]:Detect new unique element

slow += 1Move slow pointer forward to next unique position

nums[slow] = nums[fast]Overwrite duplicate with unique element

return slow + 1Return count of unique elements

public class Solution {
    public static int removeDuplicates(int[] nums) {
        if (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;
    }

    public static void main(String[] args) {
        int[] arr = {0,0,1,1,1,2,2,3,3,4};
        int length = removeDuplicates(arr);
        System.out.println(length); // Expected: 5
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Line Notes

if (nums.length == 0) return 0;Handle empty array edge case

int slow = 0;Slow pointer tracks last unique element index

for (int fast = 1; fast < nums.length; fast++) {Fast pointer scans array

if (nums[fast] != nums[slow]) {Check for new unique element

slow++;Advance slow pointer to next unique position

nums[slow] = nums[fast];Overwrite duplicate with unique element

return slow + 1;Return count of unique elements

#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.size(); fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

int main() {
    vector<int> arr = {0,0,1,1,1,2,2,3,3,4};
    int length = removeDuplicates(arr);
    cout << length << endl; // Expected: 5
    for (int i = 0; i < length; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

if (nums.empty()) return 0;Handle empty input edge case

int slow = 0;Slow pointer tracks last unique element

for (int fast = 1; fast < nums.size(); fast++) {Fast pointer scans array

if (nums[fast] != nums[slow]) {Detect new unique element

slow++;Move slow pointer forward

nums[slow] = nums[fast];Overwrite duplicate with unique element

return slow + 1;Return count of unique elements

function removeDuplicates(nums) {
    if (nums.length === 0) return 0;
    let slow = 0;
    for (let fast = 1; fast < nums.length; fast++) {
        if (nums[fast] !== nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

// Driver code
const arr = [0,0,1,1,1,2,2,3,3,4];
const length = removeDuplicates(arr);
console.log(length); // Expected: 5
console.log(arr.slice(0, length)); // Expected: [0,1,2,3,4]

Line Notes

if (nums.length === 0) return 0;Handle empty array edge case

let slow = 0;Slow pointer tracks last unique element

for (let fast = 1; fast < nums.length; fast++) {Fast pointer scans array

if (nums[fast] !== nums[slow]) {Detect new unique element

slow++;Advance slow pointer

nums[slow] = nums[fast];Overwrite duplicate with unique element

return slow + 1;Return count of unique elements

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with two pointers, no extra space used.

💡 For n=20, this means about 20 operations, which is efficient even for large inputs.

Interview Verdict: Accepted

This is the standard efficient solution for this problem and is expected in interviews.

🧠

Two Pointers - Optimized with Early Return

💡 This approach is a slight refinement of the basic two-pointer method, adding early return for empty arrays and clearer variable naming.

Intuition

Same as basic two pointers but with explicit handling of empty input and more readable code.

Algorithm

1. Check if array is empty; if yes, return 0 immediately.
2. Initialize uniqueIndex to 0 to track last unique element.
3. Iterate through array with currentIndex from 1 to end.
4. If current element differs from element at uniqueIndex, increment uniqueIndex and copy current element there.
5. Return uniqueIndex + 1 as the count of unique elements.

💡 This approach is easier to read and less error-prone, important in interviews.

</>

Code

def remove_duplicates(nums):
    if len(nums) == 0:
        return 0
    uniqueIndex = 0
    for currentIndex in range(1, len(nums)):
        if nums[currentIndex] != nums[uniqueIndex]:
            uniqueIndex += 1
            nums[uniqueIndex] = nums[currentIndex]
    return uniqueIndex + 1

# Driver code
if __name__ == '__main__':
    arr = [1,1,2]
    length = remove_duplicates(arr)
    print(length)  # Expected: 2
    print(arr[:length])  # Expected: [1,2]

Line Notes

if len(nums) == 0:Early return for empty input to avoid errors

uniqueIndex = 0Tracks position of last unique element

for currentIndex in range(1, len(nums))Iterate through array starting from second element

if nums[currentIndex] != nums[uniqueIndex]:Detect new unique element

uniqueIndex += 1Move uniqueIndex forward

nums[uniqueIndex] = nums[currentIndex]Overwrite duplicate with unique element

return uniqueIndex + 1Return count of unique elements

public class Solution {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int uniqueIndex = 0;
        for (int currentIndex = 1; currentIndex < nums.length; currentIndex++) {
            if (nums[currentIndex] != nums[uniqueIndex]) {
                uniqueIndex++;
                nums[uniqueIndex] = nums[currentIndex];
            }
        }
        return uniqueIndex + 1;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,2};
        int length = removeDuplicates(arr);
        System.out.println(length); // Expected: 2
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Line Notes

if (nums.length == 0) return 0;Early return for empty input

int uniqueIndex = 0;Tracks last unique element index

for (int currentIndex = 1; currentIndex < nums.length; currentIndex++) {Iterate through array

if (nums[currentIndex] != nums[uniqueIndex]) {Detect new unique element

uniqueIndex++;Advance uniqueIndex

nums[uniqueIndex] = nums[currentIndex];Overwrite duplicate

return uniqueIndex + 1;Return count of unique elements

#include <iostream>
#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int uniqueIndex = 0;
    for (int currentIndex = 1; currentIndex < nums.size(); currentIndex++) {
        if (nums[currentIndex] != nums[uniqueIndex]) {
            uniqueIndex++;
            nums[uniqueIndex] = nums[currentIndex];
        }
    }
    return uniqueIndex + 1;
}

int main() {
    vector<int> arr = {1,1,2};
    int length = removeDuplicates(arr);
    cout << length << endl; // Expected: 2
    for (int i = 0; i < length; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Line Notes

if (nums.empty()) return 0;Early return for empty input

int uniqueIndex = 0;Tracks last unique element

for (int currentIndex = 1; currentIndex < nums.size(); currentIndex++) {Iterate through array

if (nums[currentIndex] != nums[uniqueIndex]) {Detect new unique element

uniqueIndex++;Advance uniqueIndex

nums[uniqueIndex] = nums[currentIndex];Overwrite duplicate

return uniqueIndex + 1;Return count of unique elements

function removeDuplicates(nums) {
    if (nums.length === 0) return 0;
    let uniqueIndex = 0;
    for (let currentIndex = 1; currentIndex < nums.length; currentIndex++) {
        if (nums[currentIndex] !== nums[uniqueIndex]) {
            uniqueIndex++;
            nums[uniqueIndex] = nums[currentIndex];
        }
    }
    return uniqueIndex + 1;
}

// Driver code
const arr = [1,1,2];
const length = removeDuplicates(arr);
console.log(length); // Expected: 2
console.log(arr.slice(0, length)); // Expected: [1,2]

Line Notes

if (nums.length === 0) return 0;Early return for empty input

let uniqueIndex = 0;Tracks last unique element

for (let currentIndex = 1; currentIndex < nums.length; currentIndex++) {Iterate through array

if (nums[currentIndex] !== nums[uniqueIndex]) {Detect new unique element

uniqueIndex++;Advance uniqueIndex

nums[uniqueIndex] = nums[currentIndex];Overwrite duplicate

return uniqueIndex + 1;Return count of unique elements

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass with two pointers, no extra space.

💡 This approach is optimal and clean, suitable for production code.

Interview Verdict: Accepted

This is the recommended approach to implement in interviews for clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer approach (Approach 2 or 3) is what you should code in 95% of interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Two Pointers - Basic	O(n)	O(1)	No	N/A	Code this for optimal solution
3. Two Pointers - Optimized with Early Return	O(n)	O(1)	No	N/A	Code this for clean production-ready solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the two-pointer technique as an optimization.Step 4: Code the optimal two-pointer solution cleanly.Step 5: Test your code with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize, code correctness, and communication skills.

Common Follow-ups

• What if the array is not sorted? → Use a hash set or sort first.
• Can you do this without extra space? → Yes, the two-pointer approach is in-place.

💡 These follow-ups test your ability to adapt solutions to variations and constraints.

🔍

Pattern Recognition

When to Use

1) Input is sorted array, 2) Need to remove duplicates or partition, 3) In-place modification required, 4) Optimize for O(n) time

Signature Phrases

remove duplicatessorted arrayin-place modification

NOT This Pattern When

Unsorted arrays with duplicates removal requiring hashing or sorting first

Similar Problems

Remove Element - similar in-place removal using two pointersMerge Sorted Array - merging sorted arrays with pointers

Practice

1. You are given an unsorted array and a number k. The task is to find a subset of k elements such that the difference between the maximum and minimum elements in this subset is minimized. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Use a greedy approach by always picking the smallest element and then the next closest elements without sorting.

B. Sort the array and use a sliding window of size k to find the minimum difference between the first and last elements in each window.

C. Use dynamic programming to store minimum differences for all subsets of size k.

D. Use brute force to generate all subsets of size k and compute their differences.

Solution

1. Step 1: Understand the problem constraints

   Finding a subset of k elements with minimum max-min difference requires contiguous elements after sorting.

2. Step 2: Identify the optimal approach

   Sorting the array places elements in ascending order, so the minimum difference subset must be a contiguous window of size k. Sliding window efficiently checks all such windows.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + sliding window is classic for minimum range in subsets [OK]

Hint: Sort then slide window to find minimal range [OK]

Common Mistakes:

• Trying greedy without sorting misses optimal subsets
• Using DP unnecessarily complicates the problem
• Brute force is correct but impractical

2. What is the time complexity of the optimal 3Sum solution that sorts the array and uses a hash set for the two-sum complement search for each fixed element?

medium

A. O(n^3) because of nested loops and hash set operations

B. O(n^2) because for each element, we scan the rest with a hash set lookup in O(1)

C. O(n log n) due to sorting and linear two-pointer scans

D. O(n^2 log n) because sorting and hash set insertions dominate

Solution

1. Step 1: Identify sorting cost

   Sorting takes O(n log n), which is dominated by later steps.

2. Step 2: Analyze nested loops and hash set usage

   Outer loop runs n times; inner loop runs up to n times; hash set operations inside inner loop are O(1) each, but overall complexity is O(n^2).

3. Step 3: Clarify complexity of hash set approach

   The hash set approach inside the inner loop leads to O(n^2) complexity, not O(n^3).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Hash set lookups are O(1), so total is O(n^2) [OK]

Hint: Sorting O(n log n) < O(n²) nested loops dominate [OK]

Common Mistakes:

• Confusing hash set insertions as O(n)
• Thinking sorting dominates
• Assuming triple nested loops remain

3. What is the time complexity of the optimal 4Sum solution that uses a hash map to store all pairs of sums and then finds complementary pairs to form quadruplets?

medium

A. O(n^2 + k^2), where k is the average number of pairs per sum stored in the hash map.

B. O(n^4) because all quadruplets are checked explicitly.

C. O(n^3) due to nested loops over pairs and quadruplets.

D. O(n^2 log n) because sorting dominates the complexity.

Solution

1. Step 1: Analyze pair sum generation

   Generating all pairs sums takes O(n^2) time and space.

2. Step 2: Analyze combining pairs to quadruplets

   For each sum, combining pairs from two lists takes O(k^2) where k is average pairs per sum.

3. Step 3: Consider worst case

   In worst case, k can be O(n), so combining pairs can be O(n^2) per sum, leading to O(n^4) overall.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Worst-case complexity is O(n^4), not O(n^2 + k^2) [OK]

Hint: Worst-case complexity can be O(n^4) due to pair combinations [OK]

Common Mistakes:

• Assuming average case complexity applies to worst case
• Ignoring worst-case pair combination cost

4. What is the time and space complexity of the optimal two-pointer overwrite approach for moving zeroes to the end of an array of length n?

medium

A. Time: O(n), Space: O(1) because it scans array twice but no extra space

B. Time: O(n^2), Space: O(1) due to nested loops

C. Time: O(n), Space: O(n) because it uses an auxiliary array implicitly

D. Time: O(n log n), Space: O(1) due to sorting involved

Solution

1. Step 1: Identify loops and operations

   The algorithm scans the array twice sequentially: once to overwrite non-zero elements, once to fill zeroes.

2. Step 2: Analyze time and space

   Each loop is O(n), total O(n). No extra arrays or recursion used, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear passes, constant extra space [OK]

Hint: Two linear scans, no nested loops or extra arrays [OK]

Common Mistakes:

• Mistaking two loops as nested (O(n^2))
• Assuming extra space due to overwriting
• Confusing with sorting complexity

5. The following code attempts to reverse a list of characters in-place using recursion. Identify the line that contains a subtle bug that could cause incorrect behavior or runtime error.

def reverseString(s):
    def helper(left, right):
        if left > right:
            return
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)

if __name__ == "__main__":
    s = ['r','a','c','e','c','a','r']
    reverseString(s)
    print(s)

medium

A. Line 7: The initial call to helper is missing and should be added.

B. Line 4: The swap operation overwrites characters incorrectly without a temporary variable.

C. Line 5: The recursive call should increment both pointers by 1 instead of incrementing left and decrementing right.

D. Line 3: The base case condition should be 'left >= right' instead of 'left > right'.

Solution

1. Step 1: Examine base case condition

   The base case uses 'if left > right', but when left == right (middle element), swap should stop to avoid redundant swap or index errors.

2. Step 2: Correct base case

   Changing condition to 'left >= right' ensures recursion stops correctly when pointers meet or cross.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case off-by-one causes incorrect or extra swaps [OK]

Hint: Base case must include equality to avoid extra swaps [OK]

Common Mistakes:

• Off-by-one in base case
• Assuming swap needs temp variable in Python
• Incorrect pointer increments