Problem Statement
Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length.
Sample Test Case
Input
- Array: [1, 1, 2, 2, 3, 4, 4]
Output
- New length: 4
- Modified array: [1, 2, 3, 4]
Approaches
Brute Force Approach
Idea
Create a new array and insert unique elements from the original array, one by one, while keeping track of which elements have already been added.
Steps
- Initialize an empty array.
- Iterate through the original array.
- Add an element to the new array only if it hasn't been added already.
- Return the new length of the new array.
Time Complexity
- O(n), where n is the number of elements in the array.
Space Complexity
- O(n), as we use an additional array to store unique elements.
Example Code (JavaScript)
Dry Run
- Input: arr = [1, 1, 2, 2, 3, 4, 4]
- uniqueArr starts as an empty array.
- As we iterate, we add 1, 2, 3, and 4 to uniqueArr, ignoring the duplicates.
- The new length is 4.
Efficient Approach (Two Pointer Technique)
Idea
Since the array is sorted, use two pointers: one for iterating through the array and another for tracking the position of unique elements.
Steps
- Initialize a pointer
i at the start of the array.
- Use another pointer
j to iterate through the array.
- Whenever a unique element is found (i.e.,
arr[j] != arr[i]), move i forward and set arr[i] to arr[j].
- Return
i + 1 as the new length, which indicates the number of unique elements.
Time Complexity
- O(n), where n is the number of elements in the array.
Space Complexity
- O(1), since no additional data structures are used.
Example Code (JavaScript)
Dry Run
- Input:
arr = [1, 1, 2, 2, 3, 4, 4]
i starts at index 0, j starts at index 1.- As
j moves through the array, i only advances when a new unique element is found.
- The modified array becomes
[1, 2, 3, 4, 3, 4, 4], and the new length is 4.
Example Test Cases
Test Case 1
- Input:
arr = [1, 1, 2]
- Output: New length = 2, Modified array = [1, 2]
Test Case 2
- Input:
arr = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
- Output: New length = 5, Modified array = [0, 1, 2, 3, 4]
Test Case 3
- Input:
arr = [1, 1, 1, 1]
- Output: New length = 1, Modified array = [1]
Complexity Analysis
Brute Force Approach
- Time Complexity: O(n)
- Space Complexity: O(n)
Efficient Approach
- Time Complexity: O(n)
- Space Complexity: O(1)
Conclusion
The brute force approach is simple but requires extra space, with time complexity O(n). The two-pointer technique is a more efficient solution, achieving O(n) time complexity and O(1) space complexity, making it ideal for large datasets.