Leetcode – Remove Duplicates from Sorted Array Solution in Python

The problem ‘Remove Duplicates from Sorted Array’ is a common interview question that you might encounter during a technical interview or a coding challenge. It’s a popular problem on LeetCode which tests your understanding of array manipulation and in-place operations in Python.

In this article, we will go through a detailed explanation of the problem, its solution, and the Python code required to implement this solution.

Understanding the Problem Statement

The problem statement is as follows:

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.

The problem provides an input sorted array and asks to remove the duplicate elements from the array. The key here is to do this “in-place”, meaning we should not create a new array or use extra space to solve this problem. The return value should be the length of the array after removing the duplicates.

This problem is generally asked to test the candidate’s knowledge on array manipulation, particularly in-place operations, which are often more efficient and use less memory.

Approach to the Problem

Given that the array is already sorted, duplicate elements in the array will always be adjacent to each other. So, we can solve this problem using a two-pointer technique.

We start with two pointers, i and j, where i is slow-runner while j is the fast-runner. As long as nums[i] = nums[j], we increment j to skip the duplicate. When we encounter nums[j] ≠ nums[i], the duplicate run has ended so we must copy its value to nums[i + 1]. i is then incremented and we repeat the same process again until j reaches the end of array.

Python Solution for Remove Duplicates from Sorted Array

Now let’s implement this approach in Python:

class Solution:
    def removeDuplicates(self, nums):
        if not nums:
            return 0

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

In this solution, we start by checking if the input list nums is empty. If it is, we return 0 as there are no elements in the array.

Then, we initialize two pointers at the start of the array. We use a for loop to iterate over the array with j. Inside the loop, if the element at index i is not equal to the element at index j, we increment i and set nums[i] equal to nums[j]. This is because we have found a new, non-duplicate element that we want to keep in the array.

After the loop, we return i + 1, which is the length of the array after duplicates have been removed. The + 1 is necessary because array indices start at 0 in Python.

It’s worth mentioning that the array nums is modified in place, which fulfills the requirement set by the problem. The memory usage is O(1), or constant space, and the time complexity is O(n), where n is the number of elements in the array.

In conclusion, the ‘Remove Duplicates from Sorted Array’ problem is an interesting problem that can be solved efficiently using a two-pointer technique. It provides a good opportunity to practice in-place array manipulation and understand the trade-off between time and space complexity. Once you understand the concept of maintaining two pointers, one for iterating over the array and another for keeping track of the non-duplicate elements, this problem becomes straightforward to solve.