Remove Duplicates from Sorted Array - C Solution

1. Introduction

This blog post addresses a classic problem in array manipulation: removing duplicates from a sorted array in such a way that each unique element appears only once. This is a fundamental challenge in computer programming that tests one's understanding of array operations, particularly in-place modifications. The task is to modify the array so that the first part contains all the unique elements in their original order, and then return the count of these unique elements.

Problem

Given an integer array nums sorted in non-decreasing order, the objective is to remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be preserved. The function should return the number of unique elements in nums.

2. Solution Steps

1. Handle the edge case where the array is empty.

2. Initialize a pointer j to track the position of the non-duplicate element in the array.

3. Iterate through the array starting from the second element.

4. If the current element is different from its predecessor, update the array at the position tracked by j.

5. Increment j accordingly while iterating.

6. After completing the iteration, return j as the count of unique elements.

3. Code Program

#include <stdio.h>

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int j = 1;
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] != nums[i - 1]) {
            nums[j++] = nums[i];
        }
    }
    return j;
}

int main() {
    int nums[] = {1, 1, 2, 2, 3, 4, 4, 5};
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    int k = removeDuplicates(nums, numsSize);

    printf("Unique elements: ");
    for (int i = 0; i < k; i++) {
        printf("%d ", nums[i]);
    }
    printf("\nCount of unique elements: %d\n", k);

    return 0;
}

Output:

Unique elements: 1 2 3 4 5
Count of unique elements: 5

Explanation:

1. if (numsSize == 0) return 0; - Handle the case where the array is empty.

2. int j = 1; - Initialize the index for the unique elements.

3. for (int i = 1; i < numsSize; i++) - Iterate through the array.

4. if (nums[i] != nums[i - 1]) - Check if the current element is different from its predecessor.

5. nums[j++] = nums[i]; - Update the array at the jth position if a unique element is found and increment j.

6. return j; - Return the total count of unique elements.

7. In main, the removeDuplicates function is called, and the resulting array of unique elements and their count is printed.