Remove Duplicates from Sorted Array
Understanding Removing Duplicates
This page offers a detailed guide on removing duplicates from sorted array, exploring different methodologies, analyzing their complexities, and providing illustrative code snippets. In this homepage “Remove Duplicates from Sorted array”, we will explore the approach like Brute Force and Optimal Approach.
Statement : Removing Duplicates
Given an integer array sorted in non-decreasing order, perform an in-place removal of duplicates to ensure that each distinct element appears exactly once, while preserving the original relative order of the elements.
Example 1:
Input : A[ ] = [9, 9, 9, 9, 9]
Output : A[ ] = [9]
Explanation : All the elements present in the input array A[ ] are 9, then it will return output as one element i.e. A[ ] = [9]
Example 2:
Input : A[ ] = [11, 11, 13, 13, 13]
Output : A[ ] = [11, 13]
Explanation : All the elements present in the input array A[ ] are 11 and 13, then it will return output as two element i.e. A[ ] = [11, 13]
Approach for Removing Duplicates from Sorted Array
There are mainly two approached to solve this problem of Removing Duplicates from sorted array :
- Brute Force/Naive Approach
- Optimized Approach
Brute Force Approach
- The simplest approach involves iterating through the array and comparing each element with its adjacent one. If a duplicate is found, remove it.
- While this method works, it has a time complexity of O(n^2), making it inefficient for large arrays.
PseudoCode :
- Initialize a HashSet. Iterate through the array using a for loop.
- Add each element of the array to the HashSet.
- Record the size of the HashSet in a variable, say K.
- Transfer all elements from the HashSet back to the array, starting from the beginning.
- Return the value of K.
Code :
from typing import List
def remove_duplicates_and_update(arr: List[int]) -> int:
unique_elements_set = set()
# Create a set to store unique elements
for element in arr:
unique_elements_set.add(element)
# Update the original array with unique elements
index = 0
for unique_element in unique_elements_set:
arr[index] = unique_element
index += 1
return len(unique_elements_set)
if __name__ == "__main__":
input_array = [1, 1, 2, 2, 2, 3, 3]
unique_count = remove_duplicates_and_update(input_array)
print("The array after removing duplicate elements is:")
for i in range(unique_count):
print(input_array[i], end=" ")
Output :
The array after removing duplicate elements is: 1 2 3
Optimized Approach
- A more efficient approach takes advantage of the fact that the array is already sorted.
- By using two pointers, you can iterate through the array while maintaining the uniqueness of elements.
- This results in a time complexity of O(n) and is the preferred method for larger datasets.
PseudoCode :
- Initialize a variable i to 0. Utilize a for loop with a variable j ranging from 1 to the length of the array.
- Within the loop, check if arr[j] is not equal to arr[i]. If true, increment i and update arr[i] to be equal to arr[j].
- Upon completion of the loop, return i + 1, indicating the size of the array containing unique elements.
Code :
from typing import List
def remove_duplicates_and_update(arr: List[int]) -> int:
i = 0
for j in range(1, len(arr)):
if arr[i] != arr[j]:
i += 1
arr[i] = arr[j]
return i + 1
if __name__ == "__main__":
input_array = [1, 1, 2, 2, 2, 3, 3]
unique_count = remove_duplicates_and_update(input_array)
print("The array after removing duplicate elements is:")
for i in range(unique_count):
print(input_array[i], end=" ")
Output :
The array after removing duplicate elements is: 1 2 3
Complexity Analysis
- Time Complexity: O(N)
- Space Complexity: O(1)
To wrap it up:
In conclusion, This page explored two primary approaches—the Brute Force method and the Optimized Two-Pointer method. The Brute Force approach, involving nested loops and set operations, is straightforward but has a time complexity of O(n^2), making it less suitable for large datasets. On the other hand, the Optimized Two-Pointer approach leverages the sorted nature of the array, achieving a time complexity of O(n) by efficiently updating the array in-place.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment