Optimizing Storage: How to Remove Duplicates in Place (Python code)

Filtering Uniqueness: Visualizing the Deduplication of a Sorted Array

Welcome back to our series on essential computer algorithms where we tackle both fundamental and advanced coding challenges. Today, we delve into the “Remove Duplicates from Sorted Array” problem, an exercise that challenges us to optimize space usage while maintaining array order. In previous posts, we explored “Two Sum”و “Reverse Integer”, “Palindrome Number”, “Roman to Integer”, “Longest Common Prefix”, “Valid Parentheses” and “Merge Two Sorted Lists”, which focused on number manipulations and efficient data processing. This series aims to broaden our understanding of algorithmic solutions and their applications in real-world software development.

Problem: Remove Duplicates from Sorted Array

The problem is designed to test one’s ability to manipulate arrays efficiently. Given a sorted array of integers, the objective is to remove duplicates in-place, ensuring that each element appears only once and the original order is maintained. The solution must also return the number of unique elements, which determines the length of the modified array containing only the unique elements.

Example 1:

• Input: nums = [1,1,2]
• Output: 2, nums = [1,2,_]
• Explanation: The array should be modified to contain only 1 and 2 at the start, with the length returned as 2.

Example 2:

• Input: nums = [0,0,1,1,1,2,2,3,3,4]
• Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
• Explanation: The first five elements of the array are the unique numbers 0, 1, 2, 3, and 4, with the function returning 5.

This problem emphasizes the importance of space optimization, as the removal of duplicates must be done without allocating extra space for another array.

Solutions to the Problem

Simplest Solution: Two-pointer Technique

In the simplest solution for merging two sorted linked lists, we employ the two-pointer method, an efficient and intuitive approach that leverages the inherent order of the lists to perform a merge operation. This technique utilizes two pointers to traverse the two lists simultaneously. Each pointer tracks the current position in its respective list. At each step, the pointers compare the values of the nodes they point to, and the node with the smaller value is appended to the merged list. This process continues iteratively, effectively "zipping" the two lists together into a single sorted sequence.

def removeDuplicates(nums):
    if not nums:
        return 0
    # Initialize the first pointer
    i = 0
    # Second pointer goes through each element in the array
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

Visualizing the Two-Pointer Method: Efficiently Merging Sorted Lists

The two-pointer method is particularly well-suited for this task because it ensures that each list is only traversed once, thereby maintaining a linear time complexity relative to the combined size of the lists. This approach guarantees that the merged list retains the sorted order without requiring additional space for a separate data structure, as the nodes are merely re-linked rather than copied. This method is a staple in algorithm design for problems involving sequences or linked structures, where maintaining order and efficiency is paramount.

Optimized Solution: Same as Simplest, with detailed explanation

Given the nature of the problem, the simplest two-pointer technique is also the most optimized in terms of space and time for this specific task.

Complexity Analysis

Time Complexity: The implementation run in O(n), where n is the number of elements in the array. Each element is checked once.

Space Complexity: O(1) — The space complexity is constant because the array is modified in place without using extra space for another data structure.

Conclusion

The “Remove Duplicates from Sorted Array” problem showcases an essential technique in array manipulation — using the two-pointer method to modify the array in place efficiently. This approach is not only optimal for space but also maintains the non-decreasing order of the array, demonstrating a fundamental strategy in algorithm design. Through such challenges, programmers can sharpen their skills in handling array transformations efficiently, which is crucial for data-intensive applications.

Relevant blog in Farsi (Persian):

با زبان برنامه نویسی پایتون و کاربردهای آن آشنا شوید! | کافه‌تدریس