LeetCode 26: Remove Duplicates from Sorted Array

 

Remove Duplicates from Sorted Array - LeetCode Solution (C++)

Removing duplicates from a sorted array is a fundamental problem that tests understanding of array manipulation and in-place modifications.

---

Problem Statement

LeetCode 26: Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Return the number of unique elements and modify nums in-place.

Example 1:

Input:

nums = [1,1,2]

Output:

[1,2,_] (returning length = 2)

Example 2:

Input:

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

Output:

[0,1,2,3,4,_] (returning length = 5)

---

Optimal Approach - Two Pointers

Key Idea

1. Use two pointers: One (i) iterates through the array, while the other (j) keeps track of unique elements.
2. Move only when a new unique value is found.
3. Modify nums in-place.

Time Complexity:

• O(N) where N is the number of elements.

Space Complexity:

• O(1) as we modify the array in-place.

---

C++ Solution (LeetCode Compatible)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int j = 0; // Points to the last unique element
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[j]) { // New unique element found
                j++;
                nums[j] = nums[i]; // Move it next to the last unique element
            }
        }
        return j + 1; // Length of unique array
    }
};

---

Step-by-Step Code Explanation

1. Initialize j = 0. This keeps track of the position of the last unique element.
2. Iterate through the array (i = 1 to N-1).
   • If nums[i] != nums[j], increment j and assign nums[j] = nums[i].
3. Return j + 1, which gives the count of unique elements.

---

Dry Run / Execution Steps

Input:

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

Pointer Updates & Modifications

Step	i	j	nums[] (after modification)
1	1	0	[0,,,,,,,,,_]
2	2	1	[0,1,,,,,,,,]
3	5	2	[0,1,2,,,,,,,_]
4	7	3	[0,1,2,3,,,,,,]
5	9	4	[0,1,2,3,4,,,,,_]

Final Output:

[0,1,2,3,4,_] (length = 5)

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Notes
Using Set	O(N log N)	O(N)	❌ Uses extra memory
Brute Force (Shifting Elements)	O(N^2)	O(1)	❌ Too slow for large inputs
Two Pointers (Best Approach) ✅	O(N)	O(1)	✅ Efficient, modifies in-place

Why Two Pointers is Best?

✔ Efficient (O(N) time, O(1) space).
✔ In-place modification without extra storage.
✔ Handles edge cases like empty arrays naturally.

---

Conclusion

• Best approach: Two Pointers
• Why? O(N) time, O(1) space, and in-place modification.
• Alternative: Using Set (extra memory, unnecessary complexity).
• Practice More:
  • Remove Element
  • Move Zeroes

Would you like more LeetCode solutions like this? Let me know! 🚀