Remove Duplicates from Sorted Array: Complete Guide

Remove Duplicates from Sorted Array: A Comprehensive Tutorial

Given a sorted array, the goal is to rearrange the array so that all distinct elements appear at the beginning in sorted order. This problem demonstrates efficient in-place array manipulation using the two-pointer technique.

This tutorial provides an in-depth exploration of removing duplicates from a sorted array: the hash set approach (works for unsorted), the optimal in-place approach, practical implementations in C, edge cases, common pitfalls, and best practices.

---

Conceptual Introduction & Fundamentals

What is Removing Duplicates?

Removing duplicates means keeping only one instance of each distinct element in a sorted array, placing them at the beginning of the array.

Example:

text

Input: [1, 2, 2, 3, 4, 4, 4, 5, 5] Output: [1, 2, 3, 4, 5] (first 5 positions)

Why This Problem Matters

• In-place manipulation: Modify array without extra space.
• Two-pointer technique: Foundation for many array problems.
• Algorithm optimization: O(n) time with O(1) space.
• Interview preparation: Common coding question.

Approaches

Approach	Time Complexity	Space Complexity	Works for Unsorted?
Hash Set	O(n)	O(n)	Yes
Two Pointer	O(n)	O(1)	No (requires sorted)

---

Syntax & Core Mechanics

Optimal Approach: Two Pointers (O(n) Time, O(1) Space)

Since the array is sorted, duplicates are consecutive. Use two pointers: idx for the next distinct position and i for iteration.

c

#include <stdio.h> /* Removes duplicates in-place; returns new length */ int removeDuplicates(int arr[], int n) { if (n <= 1) { return n; // No duplicates possible } int idx = 1; // Position for next distinct element for (int i = 1; i < n; i++) { if (arr[i] != arr[i - 1]) { arr[idx++] = arr[i]; // Place distinct element } } return idx; // New length } int main(void) { int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}; int n = sizeof(arr) / sizeof(arr[0]); int newSize = removeDuplicates(arr, n); printf("Array after removing duplicates: "); for (int i = 0; i < newSize; i++) { printf("%d ", arr[i]); } printf("\n"); printf("New length: %d\n", newSize); return 0; }

Expected output:

text

Array after removing duplicates: 1 2 3 4 5 New length: 5

Hash Set Approach (Works for Unsorted)

For unsorted arrays, use a hash set to track seen elements.

c

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> /* Simple hash set for demonstration (limited range) */ #define MAX_VALUE 10000 int removeDuplicatesUnsorted(int arr[], int n) { bool seen[MAX_VALUE] = {false}; int idx = 0; for (int i = 0; i < n; i++) { if (!seen[arr[i]]) { seen[arr[i]] = true; arr[idx++] = arr[i]; } } return idx; } int main(void) { int arr[] = {5, 2, 1, 2, 4, 1, 5, 3}; int n = sizeof(arr) / sizeof(arr[0]); int newSize = removeDuplicatesUnsorted(arr, n); printf("Unsorted array after removing duplicates: "); for (int i = 0; i < newSize; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

---

Full Practical Code Example with Explanation

This program demonstrates removing duplicates with comprehensive examples and edge cases.

Program: Remove Duplicates from Sorted Array

c

/** * remove_duplicates.c * Demonstrates removing duplicates from sorted array. * Includes optimal two-pointer approach and edge cases. */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <stdbool.h> #define MAX_LINE_LEN 100 /* Function prototypes */ int removeDuplicatesSorted(int arr[], int n); int removeDuplicatesUnsorted(int arr[], int n); void demonstrateSortedArray(void); void demonstrateUnsortedArray(void); void demonstrateEdgeCases(void); void demonstratePerformance(void); void printArray(const int arr[], int n); int readInteger(const char *prompt, int *outValue); int main(void) { int choice; char buffer[MAX_LINE_LEN]; printf("=== Remove Duplicates from Array ===\n"); while (1) { printf("\n--- Menu ---\n"); printf("1. Sorted Array (Two Pointers)\n"); printf("2. Unsorted Array (Hash Set)\n"); printf("3. Edge Cases\n"); printf("4. Exit\n"); printf("Enter choice: "); fflush(stdout); if (fgets(buffer, sizeof(buffer), stdin) == NULL) { fprintf(stderr, "Error reading choice.\n"); return EXIT_FAILURE; } choice = atoi(buffer); switch (choice) { case 1: demonstrateSortedArray(); break; case 2: demonstrateUnsortedArray(); break; case 3: demonstrateEdgeCases(); break; case 4: printf("Exiting.\n"); return EXIT_SUCCESS; default: printf("Invalid choice. Please try again.\n"); break; } } return EXIT_SUCCESS; } /* Removes duplicates from sorted array: O(n) time, O(1) space */ int removeDuplicatesSorted(int arr[], int n) { if (n <= 1) { return n; } int idx = 1; for (int i = 1; i < n; i++) { if (arr[i] != arr[i - 1]) { arr[idx++] = arr[i]; } } return idx; } /* Removes duplicates from unsorted array: O(n) time, O(n) space */ int removeDuplicatesUnsorted(int arr[], int n) { bool *seen = calloc(10000, sizeof(bool)); // For values 0-9999 if (seen == NULL) { return n; } int idx = 0; for (int i = 0; i < n; i++) { if (arr[i] >= 0 && arr[i] < 10000 && !seen[arr[i]]) { seen[arr[i]] = true; arr[idx++] = arr[i]; } } free(seen); return idx; } /* Demonstrates sorted array */ void demonstrateSortedArray(void) { printf("\n=== Sorted Array ===\n"); int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original: "); printArray(arr, n); int newSize = removeDuplicatesSorted(arr, n); printf("After removing duplicates: "); printArray(arr, newSize); printf("New length: %d\n", newSize); printf("Time: O(n), Space: O(1)\n"); } /* Demonstrates unsorted array */ void demonstrateUnsortedArray(void) { printf("\n=== Unsorted Array ===\n"); int arr[] = {5, 2, 1, 2, 4, 1, 5, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original: "); printArray(arr, n); int newSize = removeDuplicatesUnsorted(arr, n); printf("After removing duplicates: "); printArray(arr, newSize); printf("Time: O(n), Space: O(n)\n"); } /* Demonstrates edge cases */ void demonstrateEdgeCases(void) { printf("\n=== Edge Cases ===\n"); /* Case 1: Empty array */ int emptyArr[] = {}; int emptyN = 0; printf("Empty array: "); int newSize = removeDuplicatesSorted(emptyArr, emptyN); printf("(length = %d)\n", newSize); /* Case 2: Single element */ int singleArr[] = {42}; int singleN = sizeof(singleArr) / sizeof(singleArr[0]); newSize = removeDuplicatesSorted(singleArr, singleN); printf("Single element: "); printArray(singleArr, newSize); /* Case 3: All duplicates */ int allDupArr[] = {2, 2, 2, 2, 2}; int allDupN = sizeof(allDupArr) / sizeof(allDupArr[0]); newSize = removeDuplicatesSorted(allDupArr, allDupN); printf("All duplicates: "); printArray(allDupArr, newSize); /* Case 4: No duplicates */ int noDupArr[] = {1, 2, 3, 4, 5}; int noDupN = sizeof(noDupArr) / sizeof(noDupArr[0]); newSize = removeDuplicatesSorted(noDupArr, noDupN); printf("No duplicates: "); printArray(noDupArr, newSize); /* Case 5: Two elements */ int twoArr[] = {1, 1}; int twoN = sizeof(twoArr) / sizeof(twoArr[0]); newSize = removeDuplicatesSorted(twoArr, twoN); printf("Two same elements: "); printArray(twoArr, newSize); /* Case 6: Negative numbers */ int negArr[] = {-5, -5, -2, -1, -1, 0, 3, 3}; int negN = sizeof(negArr) / sizeof(negArr[0]); newSize = removeDuplicatesSorted(negArr, negN); printf("Negative numbers: "); printArray(negArr, newSize); } /* Prints array */ void printArray(const int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); }

Explanation of Approaches

1. Sorted array: Two-pointer technique, O(n) time, O(1) space.
2. Unsorted array: Hash set, O(n) time, O(n) space.
3. Edge cases: Empty, single, all duplicates, no duplicates, negative.

Expected Output (partial)

text

=== Remove Duplicates from Array === --- Menu --- 1. Sorted Array (Two Pointers) 2. Unsorted Array (Hash Set) 3. Edge Cases 4. Exit Enter choice: 1 === Sorted Array === Original: 1 2 2 3 4 4 4 5 5 After removing duplicates: 1 2 3 4 5 New length: 5 Time: O(n), Space: O(1) --- Menu --- ... Enter choice: 3 === Edge Cases === Empty array: (length = 0) Single element: 42 All duplicates: 2 No duplicates: 1 2 3 4 5 Two same elements: 1 Negative numbers: -5 -2 -1 0 3

---

Common Pitfalls, Edge Cases & Memory Considerations

1. Not Handling Empty Array

Accessing arr[0] on empty array is undefined.

Solution: Check n <= 1 and return n.

2. Forgetting idx Starts at 1

First element is always distinct.

Solution: Initialize idx = 1 for sorted arrays.

3. Not Using Sorted Property

Using hash set on sorted array wastes space.

Solution: Use two-pointer technique for sorted arrays.

4. Memory Leaks in Hash Set

Forgetting to free hash set memory.

Solution: Always free allocated memory.

5. Hash Set Size Limitations

Fixed-size hash set may not cover all values.

Solution: Use dynamic hash table for arbitrary values.

6. Not Handling Negative Numbers

Hash set with only positive indices fails for negatives.

Solution: Use proper hash function or handle negatives.

7. Modifying Original Array

The function modifies the array in-place.

Solution: Document that the array is modified.

8. Returning Wrong Length

Forgetting to return the new length.

Solution: Return idx as the new size.

9. Not Testing with Edge Cases

Missing tests for empty, single, all duplicates.

Solution: Test thoroughly.

10. Memory Considerations

• Sorted array: O(1) extra space.
• Unsorted array: O(n) for hash set.
• In-place modification: no additional array needed.
• No recursion: no stack space.

---

Summary & Best Practices

Removing duplicates from a sorted array uses the two-pointer technique for O(n) time and O(1) space. For unsorted arrays, a hash set provides O(n) time with O(n) space.

Key Takeaways

• Sorted array: consecutive duplicates.
• Two-pointer technique: idx and i.
• O(n) time, O(1) space for sorted.
• Hash set for unsorted: O(n) time, O(n) space.
• Return the new length.
• Array is modified in-place.

Best Practices

1. Use two-pointer for sorted arrays.
2. Check for empty/single element arrays.
3. Use const where appropriate.
4. Document in-place modification.
5. Free hash set memory.
6. Test with edge cases.
7. Return new length correctly.
8. Handle negative numbers.
9. Consider space-time trade-offs.
10. Profile performance for large arrays.

By mastering this problem, you’ll develop the two-pointer technique essential for many array manipulation tasks.