Remove Duplicates from Sorted Array - Practice Coding Problems

Remove Duplicates from Sorted Array - Problem

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.

Consider the number of unique elements in nums to be k. After removing duplicates, return the number of unique elements k. The first k elements of nums should contain the unique numbers in sorted order. The remaining elements beyond index k-1 can be ignored.

Custom Judge: The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,1,2]

› Output: 2

💡 Note: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k.

Example 2 — Multiple Duplicates

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

› Output: 5

💡 Note: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.

Example 3 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Single element array has no duplicates, return 1.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-100 ≤ nums[i] ≤ 100
nums is sorted in non-decreasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array with duplicate elements

Process

Use two pointers to compact unique elements in-place

Output

Return count of unique elements

Key Takeaway

🎯 Key Insight: Since the array is sorted, duplicates are adjacent - use two pointers to compact unique elements in-place!

Asked in

G Google 42 a Amazon 38 M Microsoft 35 f Facebook 28

The key insight is that since the array is sorted, all duplicate elements are adjacent to each other. The optimal approach uses two pointers - one to scan through the array and another to track where to place the next unique element. This achieves O(n) time and O(1) space complexity while modifying the array in-place.

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Optimal In-Place	O(n)	O(1)	Use two pointers to track unique position and current element
Brute Force - Check All Pairs	O(n²)	O(n)	For each element, check if it appears earlier in the array

Two Pointers - Optimal In-Place — Algorithm Steps

Step 1: Start with slow pointer at position 1
Step 2: Move fast pointer through array
Step 3: When elements differ, copy to slow position
Step 4: Increment slow pointer and continue

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Slow at 1, fast scans from 1

Compare

Check if current differs from previous

Write Unique

Copy unique elements to slow position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    if (numsSize <= 1) return numsSize;
    
    // slow pointer tracks position for next unique element
    int slow = 1;
    
    // fast pointer scans through array
    for (int fast = 1; fast < numsSize; fast++) {
        // If current element is different from previous
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    return slow;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    if (strcmp(line, "[]\n") == 0) {
        printf("0\n");
        return 0;
    }
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array with two pointers

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables, no extra arrays

✓ Linear Space

67.2K Views

High Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Optimal In-Place — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler