Remove Duplicates from Sorted Array II - C Solution

1. Introduction

This blog post addresses a common problem in array manipulation: removing duplicates from a sorted array in such a way that each unique element appears no more than twice. This task is particularly challenging because it requires modifying the array in-place with constant extra space. It is a useful exercise for understanding array manipulation and in-place algorithms.

Problem

Given an integer array nums sorted in non-decreasing order, the goal is to remove some duplicates in-place such that each unique element appears at most twice. The result should be placed in the first part of the array nums. The function should return the new length k of the array after duplicates have been removed.

2. Solution Steps

1. Check if the array length is less than or equal to 2. If yes, return the length of the array.

2. Initialize two pointers: one for iterating through the array (i) and another for tracking the position of the modified array (j).

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

4. If the current element is different from the element two positions back, update the array at the jth position.

5. Increment both i and j as needed while iterating.

6. After the loop, return j as the new length of the modified array.

3. Code Program

#include <stdio.h>

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

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

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

    int k = removeDuplicates(nums, numsSize);

    printf("Array after removing duplicates: ");
    for (int i = 0; i < k; i++) {
        printf("%d ", nums[i]);
    }
    printf("\nNew Length: %d\n", k);

    return 0;
}

Output:

Array after removing duplicates: 1 1 2 2 3
New Length: 5

Explanation:

1. if (numsSize <= 2) return numsSize; - If the array size is 2 or less, no duplicates removal is needed.

2. int j = 2; - Start from the third element as the first two elements can always stay.

3. for (int i = 2; i < numsSize; i++) - Iterate through the array starting from the third element.

4. if (nums[i] != nums[j - 2]) - Check if the current element is different from the element two positions before in the modified array.

5. nums[j++] = nums[i]; - If the condition is met, update the array at jth position and increment j.

6. return j; - The final value of j is the new length of the array after duplicates have been removed.

7. In main, removeDuplicates function is called and the modified array and its new length are printed.