Remove Duplicates From Sorted Array Leetcode Problem 26 [Python Solution]

Welcome to another Python coding session! Today, we go head on with the problem of removing duplicates from a sorted array, Remove Duplicates From Sorted Array.

This problem is known as Remove Duplicates From Sorted Array and is categorized as an easy-level problem on LeetCode.

If you are looking for an efficient Python solution for this problem, you’ve come to the right place.

Problem Overview

Let’s start by understanding the problem statement.

You are given an integer array nums that is sorted in non-decreasing order.

Your task is to remove the duplicates in-place, which means modifying the array in such a way that each unique element appears only once.

The relative order of the elements should be kept the same.

After removing the duplicates, you need to return the number of unique elements in the modified array.

Here’s a step-by-step breakdown of what you need to do to get your solution accepted:

1. Change the array nums so that the first k elements of nums contain the unique elements in the order they were present in nums initially.

The remaining elements of nums are not important, and their values are not specified.

2. Return k, which represents the number of unique elements in nums.

In essence, your solution should transform the input array into a new array without duplicates while maintaining the original order of elements.

It’s essential to note that this transformation should be done in-place, without using any extra memory.

Understanding Constraints

Before we dive into the solution, let’s take a closer look at the constraints provided for this problem.

Understanding these constraints will help us design an efficient solution.

• The length of the array nums is within the range 1 <= nums.length <= 3 * 10^4.
• The elements of nums are integers, and they are sorted in non-decreasing order, meaning they form an ascending sequence.
• The integers in nums are within the range -100 <= nums[i] <= 100.

Now that we have a clear understanding of the problem and its constraints, let’s proceed with the solution.

Remove Duplicates From Sorted Array LeetCode Problem Solution

1. Bruteforce Approach

To solve this problem efficiently, we will use a two-pointer approach.

We will initialize two pointers, a left pointer and a right pointer.

The left pointer will help us keep track of where the next unique element should be placed in the modified array.

The right pointer will traverse the original array to identify unique elements.

Let’s go through the code step by step:

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

    left = 1  # Initialize left pointer
    for right in range(1, len(nums)):
        if nums[right] != nums[right - 1]:
            # This is a new unique element
            # Place it at the left pointer's position
            nums[left] = nums[right]
            left += 1

    return left

The removeDuplicates function takes an input array nums.

We start by handling a special case where the array is empty.

If the array is empty, there are no unique elements, so we return 0. Next, we initialize the left pointer to 1. Why 1?

Because the first element (at index 0) is always a unique element, and we will not modify it.

The right pointer starts from 1 and iterates through the array.

In each iteration, we compare the value at the right pointer with the value at the previous index (right - 1).

If they are not the same, it means we have encountered a new unique element.

We place this new unique element at the position pointed to by the left pointer and then increment the left pointer.

This process effectively removes duplicates while maintaining the original order.

Finally, we return the value of left, which represents the count of unique elements in the modified array.

This approach is efficient as both pointers traverse the array only once, resulting in a time complexity of O(n), where n is the length of the input array nums.

2. Efficient Approach: The Two-Pointer Technique

The efficient approach we discussed above uses a two-pointer technique to remove duplicates from the sorted array in-place.

This approach is highly efficient in terms of both time and space complexity.

Now, let’s take a deeper look into this technique and understand how it works.

Two-Pointer Technique

The key idea behind the two-pointer technique is to use two pointers: one for iterating through the array (right pointer) and another to keep track of where the next unique element should be placed (left pointer).

This technique is especially useful when dealing with sorted arrays, as it allows us to identify and remove duplicates efficiently.

Here’s how it works:

1. Initialize both left and right pointers. left starts at the position where the first unique element should be placed (usually 1), and right starts from the second element (index 1) to compare it with the previous element.
2. Iterate through the array with the right pointer.

Compare the element at the right pointer with the element at right - 1 (the previous element).

If they are the same, it’s a duplicate, and we continue to the next element.

3. When the right pointer encounters a new unique element (an element different from the previous one), we place it at the position pointed to by the left pointer and increment the left pointer.
4. Continue this process until the right pointer reaches the end of the array.

The left pointer will now point to the next available position for unique elements.

5. The left pointer’s final position indicates the count of unique elements in the modified array.

In this efficient approach, the two pointers traverse the array only once, resulting in a linear time complexity of O(n).

Now, let’s discuss the Python code for this approach, which we’ve already seen in the previous section.

Python Code Solution

def removeDuplicates(self, nums: List[int]) -> int:
    if not nums:
        return 0

    left = 1  # Initialize left pointer
    for right in range(1, len(nums)):
        if nums[right] != nums[right - 1]:
            # This is a new unique element
            # Place it at the left pointer's position
            nums[left] = nums[right]
            left += 1

    return left

This Python function effectively implements the two-pointer technique to remove duplicates from a sorted array.

It ensures that the modified array contains unique elements in the original order, and it returns the count of unique elements.

Time and Space Complexity

Before we conclude, let’s summarize the time and space complexity of our solution.

• Time Complexity: The time complexity of this solution is O(n), where n is the length of the input array nums.

This is because both the left and right pointers traverse the array only once, making it a linear-time solution.

• Space Complexity: The space complexity of this solution is O(1).

We are not using any additional data structures that grow with the input size.

The modification is done in-place, which keeps the space

complexity constant.

Reasoning Behind Our Approach

The reasoning behind our approach lies in the efficiency of the two-pointer technique when applied to this specific problem.

Given the sorted nature of the input array, we can use two pointers to identify and remove duplicates efficiently while maintaining the original order of elements.

By comparing adjacent elements and placing new unique elements at the appropriate positions in the modified array, we achieve the desired result without the need for additional memory.

This approach minimizes both time and space complexity, making it an optimal solution for the Remove Duplicates From Sorted Array problem.

Related Interview Questions By Company:

• Maximum Depth Of Binary Tree LeetCode
• Remove Duplicates From Sorted Array LeetCode
• Reverse Bits LeetCode

Related Interview Questions By Difficulty:

• Reverse String LeetCode
• Valid Palindrome II LeetCode
• Rotate Array LeetCode

Related Interview Questions By Category:

• Maximum Length Of A Concatenated String With Unique Characters
• IPO LeetCode
• Middle Of The Linked List LeetCode

Conclusion

In this blog post, we’ve explored an efficient Python solution to the LeetCode problem Remove Duplicates From Sorted Array We’ve discussed the problem statement, constraints, and the reasoning behind our approach.

We used the two-pointer technique to remove duplicates from a sorted array in-place, while also maintaining the original order of elements.

The resulting code is concise, easy to understand, and has a time complexity of O(n) and a space complexity of O(1).

I hope this solution helps you in your coding journey.

If you found this blog post useful, please like and engage to support our our platform.

Feel free to ask questions, make suggestions, and share this content with others.

You can access the original problem and try the solution on LeetCode here: Remove Duplicates From Sorted Array.

Happy coding, and stay tuned for more coding adventures!