Remove duplicates from Sorted array – Leetcode 26

Hi everyone, in this article we’ll guide you through the Python program to Remove Duplicates from Soroted Array (in-place) [Problem Link]. We will see both the brute-force and optimal solution and dry run. So let’s begin.

Understand the problem

This problem “Remove Duplicates from Sorted Array” is about modifying a sorted array in place to remove duplicate values while keeping the original order. The goal is to return the number of unique elements.

Simple Question Explanation:

1. You are given a sorted array (non-decreasing order).
2. You need to remove duplicate values so that each unique number appears only once.
3. The remaining unique elements should be placed at the beginning of the array.
4. You cannot use extra space (i.e., no new array), so the changes must be done in place.
5. The function should return the count of unique numbers.

Example:

Input:

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

Output:

nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Explanation: The first 5 elements are the unique values, and the remaining elements are ignored.

Return value: 5 (since there are 5 unique numbers).

Key Constraints:

• The array is already sorted.
• You must modify the array in place (without using extra space).
• The function should return the count of unique elements.

Also read about the Python Program to Rotate an Array by K Places.

1. Brute Force Solution (With Dictionary)

This approach will use dictionary to store unique elements and then use it to put it back into the original array. This might not be the most optimal solution, but we can still get to our answer.

Intuition and Approach

The solution uses a dictionary (my_dict) to track the unique elements of the array. Since dictionary keys in Python are unique, inserting each element of the array as a key in the dictionary automatically removes any duplicates. The approach is straightforward:

• Populate the dictionary with the elements of the array.
• Iterate through the dictionary keys, which are guaranteed to be unique, and copy them back into the original array nums.
• The new length of the array without duplicates is then the count of these unique keys.

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        my_dict = dict()
        for i in nums:
            my_dict[i] = 0

        j = 0
        for n in my_dict:
            nums[j] = n
            j += 1
        return j

Code Explanation

1. Initialization:
   • A dictionary my_dict is initialized to store each unique element of nums.
2. First Loop – Removing Duplicates:
   • Iterates over each element i in nums.
   • Adds i to my_dict as a key. If i is already a key in the dictionary, it does nothing (ignoring duplicates).
3. Second Loop – Reassigning to nums:
   • j is initialized to 0 to act as the index for the next unique element in nums.
   • Iterates through the keys in my_dict (which are the unique elements).
   • Each key n is placed back into nums[j], and j is incremented.
4. Return Statement:
   • Returns j, the number of unique elements placed back into nums.

Dry Run (with images)

Let’s walk through a step-by-step dry run with a sample input:

Edge cases to consider

• Empty Array: If nums is empty (nums = []), our code correctly returns 0 and makes no changes.
• Array with No Duplicates: If the array already contains no duplicates (e.g., nums = [1, 2, 3]), our function will return the original length of the array.
• All Elements Identical: For an array where all elements are identical (e.g., nums = [1, 1, 1]), our function will return 1, with the first element being the unique one.

Time and Space Complexity

• Time Complexity: The time complexity is O(n + n), where n is the length of the array. This is because of one pass to fill the dictionary and another to update the array.
• Space Complexity: The space complexity is O(k), where k is the number of unique elements in nums. In the worst case (all elements are unique), this is O(n).

2. Optimal Solution (With Two Pointers)

To solve this problem we will be using two pointers as i and j. Check out the solution below to understand what are we trying to do and understand through the images via dry run.

Intuition and Approach

Given that the array is sorted, our solution utilizes the two-pointer technique to effectively filter out duplicates in-place. The main idea is to maintain two pointers:

• i points to the last position of the unique elements encountered so far.
• j will loop through the array giving us non duplicates.

If nums[j] is not equal to nums[i], it means nums[j] is a unique element that hasn’t been recorded yet. Therefore, nums[j] is swapped with nums[i+1], effectively growing the list of unique elements by one. The process ensures that all unique elements are shifted to the front of the array in their original order.

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1
        i = 0
        j = i + 1
        while j < len(nums):
            if nums[j] != nums[i]:
                i += 1
                nums[j], nums[i] = nums[i], nums[j]
            j += 1
        return i + 1

Code Explanation

1. Initial Checks:
   • If the array has only one element, it immediately returns 1 since a single element is inherently unique.
2. Initialization:
   • Two pointers, i and j, are initialized where i starts at 0 and j starts at i + 1.
3. While Loop:
   • The loop continues as long as j is less than the length of the array.
   • Inside the loop:
     1. If nums[j] is different from nums[i], this indicates a new unique element.
     2. i is incremented to extend the segment of unique elements.
     3. nums[j] is then swapped with nums[i], positioning it within the unique segment.
     4. j is incremented on every iteration to continue scanning the array.
4. Return Statement:
   • Returns i + 1, which is the count of unique elements since i is the index of the last unique element.

Dry Run (with images)

Let’s walk through a step-by-step dry run with a sample input:

Edge cases to consider

• Empty Array: If nums is empty, our function will handle this and return 0.
• All Elements Identical: For nums = [1, 1, 1], our function should return 1, correctly identifying the single unique element.
• Array with No Duplicates: For an array like nums = [1, 2, 3], our function should return the length of the array, which is 3.

Time and Space Complexity

Time Complexity: The complexity is O(n), where n is the length of the array. Our code iterates through the list once with the j pointer.

Space Complexity: The complexity is O(1) as the solution modifies the array in place and does not use additional space.

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.