[Array] Remove Duplicates from Sorted Array - Easy

Removing duplicates from a sorted array is a common task in programming. We see this in languages like Java, Python, and C++. The main goal is to get rid of duplicate entries but keep the unique ones in order. We can use different ways like the two-pointer method or changing the array in place. This helps us do it quickly and use less space.

In this article, we will look at different ways to remove duplicates from a sorted array in various programming languages. We will see how to do it in Java, Python, and C++. We will also talk about methods like the two-pointer approach and in-place changes. Plus, we will answer common questions about this topic. This will help us understand how to remove duplicates from sorted arrays better.

  • Remove Duplicates from Sorted Array in Java
  • Remove Duplicates from Sorted Array in Python
  • Remove Duplicates from Sorted Array in C++
  • Two Pointer Approach in Java
  • Two Pointer Approach in Python
  • Two Pointer Approach in C++
  • In Place Modification in Java
  • In Place Modification in Python
  • In Place Modification in C++
  • Frequently Asked Questions

For more reading on related array problems, check out articles on Array Two Sum, Array Contains Duplicate, and Array Maximum Subarray.

Remove Duplicates from Sorted Array in Python

We can remove duplicates from a sorted array in Python easily. We can use a simple method with two pointers or change the array in place. Since the array is sorted, duplicates are next to each other. This makes it easier to manage them.

Two Pointer Approach

This method uses two pointers. One pointer goes through the array. The other pointer keeps track of where we put unique elements.

def remove_duplicates(nums):
    if not nums:
        return 0
    
    unique_index = 1  # Start from the second element
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:  # Compare with the previous element
            nums[unique_index] = nums[i]
            unique_index += 1
            
    return unique_index  # Length of unique elements

In Place Modification

We can also change the original array without using extra space. The unique elements will be at the start of the array.

def remove_duplicates_in_place(nums):
    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  # Number of unique elements

Example Usage

nums = [0, 0, 1, 1, 2, 2, 3, 4]
length = remove_duplicates(nums)
print(nums[:length])  # Output: [0, 1, 2, 3, 4]

For more reading, we can find helpful info in the article on Array Contains Duplicate. This article looks at how to handle duplicates in arrays.

Remove Duplicates from Sorted Array in C++

To remove duplicates from a sorted array in C++, we can use a two-pointer technique. This method changes the array directly and keeps its sorted order.

Code Example

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int uniqueIndex = 0; // Pointer for unique elements
    
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[uniqueIndex]) {
            uniqueIndex++;
            nums[uniqueIndex] = nums[i]; // Update unique position
        }
    }
    
    return uniqueIndex + 1; // Return count of unique elements
}

int main() {
    std::vector<int> nums = {1, 1, 2, 2, 3, 4};
    int newSize = removeDuplicates(nums);
    
    std::cout << "The new size is: " << newSize << std::endl;
    std::cout << "Array after removing duplicates: ";
    for (int i = 0; i < newSize; i++) {
        std::cout << nums[i] << " ";
    }
    return 0;
}

Explanation

  • The function removeDuplicates takes a vector of integers.
  • It checks if the vector is empty. If so, it returns 0.
  • We start a pointer uniqueIndex at 0 to track unique elements.
  • Then, we loop through the array. We compare each element with the last unique element.
  • When we find a new unique element, we put it at uniqueIndex. Then we increase uniqueIndex.

This way, we change the original array directly. It gives us a time complexity of O(n) and a space complexity of O(1).

For more insights on arrays, check our articles on Array Contains Duplicate and Array Rotate Array.

Two Pointer Approach in Java

We can use the Two Pointer Approach to remove duplicates from a sorted array in Java. This is a simple and effective technique. It uses two pointers to go through the array. This helps us place each unique element at the front.

Implementation

Here is a simple way to use the Two Pointer Approach to remove duplicates:

public class RemoveDuplicates {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int uniqueIndex = 1; // Start from the second element
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[uniqueIndex] = nums[i]; // Place unique element
                uniqueIndex++;
            }
        }
        
        return uniqueIndex; // Number of unique elements
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 3};
        int uniqueCount = removeDuplicates(nums);
        
        System.out.println("Number of unique elements: " + uniqueCount);
        for (int i = 0; i < uniqueCount; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

Explanation

  • Initialization: We start with a pointer for unique elements called uniqueIndex, and we set it to 1.
  • Traversal: We go through the array starting from the second element.
  • Comparison: If the current element is different from the one before it, we put it in the position at uniqueIndex, then we move uniqueIndex up by one.
  • Return Value: The method gives back the count of unique elements, which helps us to find the new length of the array.

This way is quick. It has a time complexity of O(n) and a space complexity of O(1). This makes it a good choice for this problem. If we want to learn more about handling arrays, we can check Remove Duplicates in a Sorted Array.

Two Pointer Approach in Python

The Two Pointer Approach is a simple way to remove duplicates from a sorted array in Python. We use two pointers to go through the array. This helps us keep a unique set of elements.

Implementation

def remove_duplicates(nums):
    if not nums:
        return 0

    # Pointer for the position of unique elements
    unique_index = 1

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

    return unique_index

# Example usage
arr = [1, 1, 2, 2, 3, 4]
length = remove_duplicates(arr)
print(arr[:length])  # Output: [1, 2, 3, 4]

Explanation

  • Initialization: We start with unique_index at 1 because the first element is always unique.
  • Traversal: We loop through the array starting from the second element.
    • If the current element is different from the one before it, we put it in the unique_index position and increase unique_index.
  • Return: We return the length of the array without duplicates.

This method runs in O(n) time and O(1) space. It is a good choice for this problem. For more algorithms like this, check Array Contains Duplicate.

Two Pointer Approach in C++

The Two Pointer approach is a good way to remove duplicates from a sorted array in C++. This method uses two pointers to look through the array and handle duplicates well.

Implementation

In this method, one pointer (i) goes through the array. The other pointer (j) keeps track of where the unique elements are. Here are the main steps:

  1. Start with the first pointer i at 1 (the second element) and the second pointer j at 0 (the first element).
  2. Compare the element at i with the element at j.
  3. If they are different, we move j forward and set the element at j to the element at i.
  4. Keep going until we reach the end of the array.

Example Code

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) return 0;

    int j = 0; // Pointer for the unique elements

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[j]) {
            j++; // Move to the next position
            nums[j] = nums[i]; // Update the unique position
        }
    }
    return j + 1; // Return the count of unique elements
}

int main() {
    std::vector<int> nums = {1, 1, 2, 2, 3};
    int newLength = removeDuplicates(nums);

    std::cout << "Number of unique elements: " << newLength << std::endl;
    std::cout << "Unique elements: ";
    for (int i = 0; i < newLength; i++) {
        std::cout << nums[i] << " ";
    }
    return 0;
}

Key Properties

  • Time Complexity: O(n), where n is the length of the array.
  • Space Complexity: O(1), because we don’t use extra space for storing elements.

This method works well and is good for large datasets. It makes sure that only unique elements stay in the original array. For more reading on similar problems, you can check Array Contains Duplicate or see how to deal with different array manipulations in other articles.

In Place Modification in Java

To remove duplicates from a sorted array in Java, we can use a simple way to go through the array. We will keep a pointer to track where the unique elements go as we look at each element.

Implementation

public class RemoveDuplicates {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int uniqueIndex = 1; // Start from the second element
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) { // Found a new unique element
                nums[uniqueIndex] = nums[i];
                uniqueIndex++;
            }
        }
        
        return uniqueIndex; // Length of array with unique elements
    }

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

Explanation

  • Time Complexity: O(n), where n is how many elements in the array.
  • Space Complexity: O(1), since we not using extra data structures.
  • The function changes the input array to keep only unique elements and gives back the new length of the changed array.

This way is good for removing duplicates from a sorted array. It keeps the order of elements. For more topics, you can check Contains Duplicate or look at other array problems like Two Sum.

In Place Modification in Python

We can remove duplicates from a sorted array in Python by using in-place modification. We will use the two-pointer technique. This way, we do not need extra space for another array. It helps save memory.

Code Example

def remove_duplicates(nums):
    if not nums:
        return 0

    # Pointer for the position of the next unique element
    write_index = 1

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

    return write_index

Explanation

  • Initialization: We start with write_index set to 1. The first element is always unique.
  • Iteration: We loop through the array starting from the second element.
  • Comparison: If the current element is different from the one before, we write it at write_index and increase write_index.
  • Return Value: The function gives back the length of the array with unique elements.

Example Usage

nums = [0, 0, 1, 1, 2, 2, 3, 3, 4]
length = remove_duplicates(nums)
print(length)  # Output: 5
print(nums[:length])  # Output: [0, 1, 2, 3, 4]

The code above changes the original array in place. It leaves only the unique elements at the start of the array.

For more related topics, we can find useful insights in articles like Array Contains Duplicate and Array Rotate Array.

In Place Modification in C++

To remove duplicates from a sorted array in C++, we can use a method called in-place modification. This method changes the original array. We do not need extra space for another array. This makes it good for time and space use.

Algorithm

  1. We start with a pointer i to keep track of unique elements. It begins at index 0.
  2. We will use another pointer j to go through the array. This starts from index 1.
  3. For each element at j, if it is different from the element at i, we increase i and set array[i] to array[j].
  4. We repeat this until we reach the end of the array.
  5. We can find the number of unique elements by using i + 1.

C++ Code Example

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int i = 0; // Pointer for unique elements
    
    for (int j = 1; j < nums.size(); j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j]; // Put the unique element in the next place
        }
    }
    
    return i + 1; // Length of unique elements
}

int main() {
    std::vector<int> nums = {1, 1, 2, 3, 3, 4};
    int length = removeDuplicates(nums);
    
    std::cout << "Length of unique elements: " << length << std::endl;
    std::cout << "Modified array: ";
    for (int k = 0; k < length; k++) {
        std::cout << nums[k] << " ";
    }
    
    return 0;
}

Key Properties

  • Time Complexity: O(n), where n is how many elements are in the array.
  • Space Complexity: O(1) because we do not use extra space for another array.
  • Modification: The original array is changed to have unique elements at the start. The other elements are not defined.

For more tips on array changes, see Remove Duplicates from Sorted Array in Python.

Frequently Asked Questions

1. How do we remove duplicates from a sorted array in Java?

To remove duplicates from a sorted array in Java, we can use a simple loop. We will use a counter to keep track of unique elements. We will go through the array and compare each element with the one before it. If they are different, we will move the unique element to the front. Here is a sample code snippet:

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int uniqueIndex = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] != nums[i - 1]) {
            nums[uniqueIndex++] = nums[i];
        }
    }
    return uniqueIndex;
}

2. What is the two-pointer approach for removing duplicates in Python?

The two-pointer approach in Python helps us remove duplicates from a sorted array quickly. One pointer checks the current element. The other pointer moves through the array. If the two elements are different, we write the unique element to where the first pointer is. This method is good since it has a time complexity of O(n). You can see a detailed example here.

3. Can we modify the array in place when removing duplicates in C++?

Yes, we can change the array in place while removing duplicates in C++. We can use a single loop and a variable to keep track of unique elements. This way, we can directly overwrite duplicates in the original array. Below is an example code snippet:

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

4. What are the benefits of using the two-pointer technique for this problem?

The two-pointer technique works well for removing duplicates from a sorted array. It helps us avoid nested loops. Nested loops can slow down the process. With two pointers, we go through the array in one pass. This gives us O(n) time complexity, which is the best for this kind of problem. We can also use this technique in many other array tasks, which can help us improve our coding skills.

5. Are there common mistakes to avoid when removing duplicates from an array?

Yes, there are common mistakes when we remove duplicates from an array. One mistake is not handling edge cases. For example, we should check for empty arrays or arrays with only one element. Another mistake is forgetting to check if the array is sorted. This can lead to wrong results. We should always understand the problem rules before we start coding. For more on array problems, check out articles like Best Time to Buy and Sell Stock.