Remove Duplicates from Sorted Array in C#

Programming C#
1

Removing duplicates from a sorted array in C# can be efficiently accomplished using a two-pointer technique. Since the array is sorted, duplicates will always be adjacent, making it straightforward to identify and remove them.

Explanation

  1. Two Pointers: Use one pointer to traverse the array (the current pointer) and another pointer to keep track of the position where the next unique element should be placed (the uniqueIndex pointer).

  2. Traverse the Array: As you iterate through the array with the current pointer, whenever you encounter a unique element (i.e., it differs from the last unique element found), you place it at the uniqueIndex position and increment uniqueIndex.

  3. Return the Result: After processing the array, the uniqueIndex will represent the count of unique elements, and the modified portion of the array will contain all unique elements.

Code Implementation

Here’s a sample implementation in C#:

using System;

class Program
{
    static int RemoveDuplicates(int[] nums)
    {
        if (nums.Length == 0) return 0;

        int uniqueIndex = 1; // Start from the second element

        for (int current = 1; current < nums.Length; current++)
        {
            // Check if the current element is different from the previous one
            if (nums[current] != nums[current - 1])
            {
                nums[uniqueIndex] = nums[current]; // Place the unique element
                uniqueIndex++; // Move to the next position for the next unique element
            }
        }

        return uniqueIndex; // The length of the array with unique elements
    }

    static void Main(string[] args)
    {
        int[] arr = { 0, 0, 1, 1, 2, 2, 3, 3, 4 };
        int newLength = RemoveDuplicates(arr);
        
        Console.WriteLine($"Length of array after removing duplicates: {newLength}");
        Console.WriteLine("Modified array: " + string.Join(", ", arr[..newLength])); // Output only unique elements
    }
}

How the Code Works

  1. Check for Empty Array: If the array is empty, return 0 immediately.

  2. Initialize the Unique Index: Set uniqueIndex to 1, as the first element is always considered unique.

  3. Loop Through the Array:

    • Start from the second element (index 1) and compare each element to the one before it.
    • If the current element is different from the previous element, it means it’s a unique element. Place it at the uniqueIndex position and increment uniqueIndex.

  4. Return the Unique Count: After the loop completes, uniqueIndex indicates how many unique elements are in the array.

  5. Output the Results: In the Main method, we print the length of the modified array and display the unique elements.

Complexity

  • Time Complexity: O(n), where n is the number of elements in the array. We only make one pass through the array.
  • Space Complexity: O(1), since we are modifying the array in place and not using any additional data structures.

This method is efficient and straightforward for removing duplicates from a sorted array.