Remove Duplicates From Sorted Array II Leetcode Problem 80 [Python]

Welcome to another exciting coding session!

In this blog post, we'll tackle the Remove Duplicates From Sorted Array II problem from LeetCode.

This problem falls under the category of Two Pointers and is classified as a medium difficulty challenge.

It's a great opportunity to sharpen your problem-solving skills and explore an efficient Python solution.

Let's dive right in and understand the problem statement.

Problem Overview

The problem presents us with an integer array, nums, which is sorted in non-decreasing order (essentially, sorted in ascending order).

Our goal is to remove some duplicates in-place so that each unique element appears at most twice.

Crucially, we must maintain the relative order of the elements.

In other words, if there are 'k' elements after removing the duplicates, the first 'k' elements of nums should contain the final result.

It's important to note that we should not concern ourselves with what lies beyond the first 'k' elements in the array.

The key objective is to modify the input array in-place, using O(1) extra memory.

To illustrate the problem, let's consider an example:

Example 1:

Input: nums = [1, 1, 1, 2, 2, 3]
Output: k = 5, nums = [1, 1, 2, 2, 3, _]

Here, our function should return k = 5, with the first five elements of nums being 1, 1, 2, 2, and 3, respectively.

Anything beyond the returned k value is not relevant, denoted by underscores.

Example 2:

Input: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
Output: k = 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

In this case, the function should return k = 7, and the first seven elements of nums should be 0, 0, 1, 1, 2, 3, and 3, respectively.

Anything beyond the returned k value is irrelevant, marked by underscores.

Constraints:

1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums is sorted in non-decreasing order.

Now that we have a clear understanding of the problem statement, including the constraints, let's explore how we can efficiently tackle this challenge.

Understanding Constraints

Before delving into the solution, it's crucial to grasp the constraints of the problem.

Understanding these constraints will help us choose the most appropriate approach and optimize our code.

The key constraints to keep in mind are as follows:

The input array, nums, can have a maximum length of 30,000. This suggests that our solution needs to be efficient, preferably linear time complexity.
The values in nums can range from -10,000 to 10,000. This range isn't overly large, which means we can use straightforward comparisons and manipulation of values.
The input array is sorted in non-decreasing order, which simplifies our task.

All duplicates will be adjacent, making them easier to identify and handle.

With these constraints in mind, we can proceed to develop a solution that meets the efficiency and memory requirements.

Remove Duplicates From Sorted Array II LeetCode Problem Solution

Now, let's get into the heart of the solution.

We'll approach this problem step by step, and I'll provide you with both the efficient Python code solution and a clear understanding of its logic.

1. Bruteforce Approach

Before we dive into the more efficient approach, let's briefly discuss a less efficient method for solving this problem.

This approach involves using two pointers and counting the duplicates.

def removeDuplicatesBruteforce(nums):
    # Initialize left and right pointers
    left = 0
    right = 1

    while right < len(nums):
        count = 1

        # Count duplicates
        while right + 1 < len(nums) and nums[right] == nums[right + 1]:
            right += 1
            count += 1

        # Keep at most two duplicates
        for i in range(min(2, count)):
            nums[left] = nums[right]
            left += 1

        right += 1

    return left

This bruteforce approach essentially follows the same logic we discussed earlier, but it does not optimize the process as much as the efficient approach we'll cover next.

2. An Efficient Approach with Explanation

To achieve an efficient solution, we'll iterate through the array while maintaining two pointers, left and right.

We'll also keep track of the count of duplicates.

The efficient approach follows this logic:

Initialize the left and right pointers at the beginning of the array.
While iterating through the array with the right pointer, we'll count the number of duplicates in the current streak of the same values.
If we encounter more than two duplicates, we'll skip the extra duplicates and move the right pointer to the next unique value.
If we encounter two or fewer duplicates, we'll copy these duplicates to the left pointer's position and increment the left pointer accordingly.
After processing all duplicates in a streak, the left pointer will be at the appropriate position.
Continue this process until we reach the end of the array.

Let's dive into the efficient Python code solution that follows this logic:

def removeDuplicates(nums):
    left = 0
    right = 0

    while right < len(nums):
        count = 1

        # Count duplicates
        while right + 1 < len(nums) and nums[right] == nums[right + 1]:
            right += 1
            count += 1

        # Keep at most two duplicates
        for i in range(min(2, count)):
            nums[left] = nums[right]
            left += 1

        right += 1

    return left

This efficient solution provides a faster and more optimized way to remove duplicates from the sorted array while ensuring that we follow the constraints of the problem.

Python Code Solution

Now that we've discussed the efficient approach, let's provide the Python code solution for the problem:

View on GitHub ➹

def removeDuplicates(nums):
    left = 0
    right = 0

    while right &lt; len(nums):
        count = 1

        # Count duplicates
        while right + 1 &lt; len(nums) and nums[right] == nums[right + 1]:
            right += 1
            count += 1

        # Keep at most two duplicates
        for i in range(min(2, count)):
            nums[left] = nums[right]
            left += 1

        right += 1

    return left

You can use this Python function to remove duplicates from a sorted array as described in the problem statement.

It efficiently processes the

array and returns the length of the resulting array.

Time and Space Complexity

Now, let's analyze the time and space complexity of our solution.

Time Complexity: Our solution has a time complexity of O(n), where n is the length of the input array nums.

The reason for this linear time complexity is that we iterate through the array only once, ensuring that each element is processed efficiently.

Space Complexity: Our solution has a space complexity of O(1), indicating that it uses a constant amount of extra memory.

We don't rely on additional data structures that grow with the input size.

Reasoning Behind Our Approach

Our approach is based on the principle of efficiently handling duplicates while iterating through the array in a single pass.

By using two pointers, left and right, we're able to keep track of both the current position and the position where we should place unique values.

We count duplicates, ensuring that we process at most two duplicates of each value.

If we encounter more than two duplicates, we skip the extras.

By following this approach, we eliminate the need for additional data structures and achieve the desired result in linear time.

Conclusion

In this blog post, we explored the Remove Duplicates From Sorted Array II problem from LeetCode.

We provided an efficient Python solution that follows the constraints of the problem and ensures that duplicates are removed while maintaining the relative order of elements.

By using a two-pointer approach and counting duplicates, we achieved a time complexity of O(n) and a space complexity of O(1).

This solution is well-optimized for large input arrays and adheres to the constraints provided in the problem statement.

We encourage you to test the code, experiment with different inputs, and deepen your understanding of this efficient approach.

Coding challenges like these are excellent opportunities to enhance your problem-solving skills and become a more proficient programmer.

If you found this guide helpful or have any questions, please feel free to comment, ask questions, make suggestions, or share the content with others.

We value your engagement and aim to provide valuable resources for both beginners and experienced programmers.

For the full problem description and to try the problem on LeetCode, visit the following link:
Remove Duplicates From Sorted Array II on LeetCode

Thank you for joining us on this coding journey, and we look forward to sharing more coding insights with you in the future!

Happy coding!