Remove Duplicates from Sorted Array Problem and Solution

1. Introduction

A comprehensive guide to solving the "Remove Duplicates from Sorted Array" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "Remove Duplicates from Sorted Array" problem involves modifying an array in place to remove all duplicates, such that each element appears only once. The challenge is to do this with optimal space complexity.

2. Problem

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

3. Solution in C++

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

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

// Example usage
int main() {
    vector<int> nums = {1, 1, 2};
    int newLength = removeDuplicates(nums);
    for (int i = 0; i < newLength; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}

Output:

1 2

Explanation:

1. removeDuplicates in C++ uses two pointers i and j.

2. It iterates through the array with j and only increments i when a new unique element is found.

3. Unique elements are moved to the front of the array.

4. The function returns the length of the array without duplicates.

4. Solution in Java

import java.util.*;

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

    // Example usage
    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        int newLength = removeDuplicates(nums);
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
    }
}

Output:

1 2

Explanation:

1. Java's removeDuplicates method follows the same two-pointer approach as C++.

2. It traverses the array, shifting non-duplicate elements to the front.

3. Returns the length of the modified array, representing the number of unique elements.

5. Solution in Python

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

# Example usage
nums = [1, 1, 2]
new_length = remove_duplicates(nums)
print(nums[:new_length])

Output:

[1, 2]

Explanation:

1. Python's remove_duplicates function uses a two-pointer approach.

2. The i pointer tracks the position of the last unique element, and j iterates through the array.

3. When a new unique element is found, it's moved to the position next to the last unique element (i index).

4. Returns the count of unique elements in the array.