Remove Duplicate From Sorted Array – 26. LeetCode

The Remove Duplicates from Sorted Array problem asks us to take a sorted array of integers and remove duplicate values in-place so that each unique value appears only once. The result must use the initial part of the array to store unique elements, and the rest of the array beyond the “result length” doesn’t matter. The function should return the count of unique elements in the modified array. This problem is about leveraging the fact that the input array is sorted, making it easier to identify and eliminate duplicates.

Brute Force Approach

public int RemoveDuplicatesBruteForce(int[] nums) {
    if (nums.Length == 0) return 0; // Handle empty array edge case.

    int index = 0; // Keeps track of the next position for a unique element.

    for (int i = 0; i < nums.Length; i++) { // Outer loop to iterate through the array.
        bool isUnique = true; // Flag to check if the current element is unique.

        for (int j = 0; j < index; j++) { // Inner loop to check for duplicates.
            if (nums[i] == nums[j]) { // If duplicate is found.
                isUnique = false; 
                break; // Exit inner loop early.
            }
        }

        if (isUnique) { // If the element is unique, place it in the unique section.
            nums[index] = nums[i];
            index++; // Increment the index for unique elements.
        }
    }

    return index; // Return the count of unique elements.
}

This code iterates through the array and checks if each element is already present in the portion of the array considered “unique”. If it’s unique, the element is placed in the “result” section of the array, and the count of unique elements (index) is incremented.

• Outer loop: Goes through each element in the array
• Inner loop: Checks if the current element is a duplicate by comparing it to all elements in the unique section.
• In-place modification: If the element is unique, it’s moved to the unique section.

Optimal Approach: Two Pointers Technique

Algorithmic and Data Structure Pattern

The optimal solution leverages the Two Pointers technique, which is ideal for processing elements in-place in arrays. This approach works because the array is sorted, so duplicates will always appear consecutively.

Intuition Behind the Algorithm

The algorithm uses two pointers:

1. A slow pointer (i) to track the position where the next unique element should be placed.

2. A fast pointer (j) to scan through the array for unique elements.

By comparing the current element (nums[j]) to the last placed unique element (nums[i-1]), we can determine if a duplicate exists. When a new unique element is found, it’s placed at the next position in the array.

Steps

1. Check if the array is empty; return 0 if true.

2. Initialize a pointer uniqueIndex to track where the next unique element should go.

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

4. Compare each element with its previous one.

5. If unique, place the element at the position indicated by uniqueIndex and increment uniqueIndex.

6. Return uniqueIndex, which represents the count of unique elements.

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

        int uniqueIndex = 1;
        for (int i = 1; i < nums.Length; i++)
        {
            if (nums[i] != nums[i - 1])
            {
                nums[uniqueIndex] = nums[i];
                uniqueIndex++;
            }
        }
        return uniqueIndex;
    }
}

Line-By-Line Code Explanation

Step 1: Handle Edge Case

if (nums.Length == 0) return 0;

• Check if the input array (nums) is empty. If it is, the function immediately returns 0 because there are no elements to process or count as unique.

Step 2: Initialize Index

int uniqueIndex = 1;

• Initializes a pointer, uniqueIndex to 1. This pointer tracks the position where the next unique element should be placed in the array.
• It uses in-place modification to save memorty, which is both efficient and adheres to the problem’s requirments.

Step 3: iterate Through the Array

for (int i = 1; i < nums.Length; i++) {

• Starts a loop from the second element and iterates through the entire array.
• Avoids unnecessary comparisons with elements before i – 1, improving efficiency.

Step 4: Check for a Unique Element

if (nums[i] != nums[i - 1]) {

• Compares the current element (nums[i]) with the previous element (nums[i – 1]). If they are not equal, the current element is unique.
• This condition ensures that duplicates are skipped, and only unique elements are processed.

Step 5: Place the Unique Element

nums[uniqueIndex] = nums[i];
uniqueIndex++;

• Assigns the unique element (nums[i]) to the position indicated by uniqueIndex.

• Increments uniqueIndex to point to the next position for a future unique element.

• In-place modification eliminates the need for extra space, meeting the problem’s constraints for space efficiency.

Step 6: Return

return uniqueIndex;

• Returns the value of uniqueIndex, which now holds the count of unique elements.

Why This Code Works

Why This Code Was Written This Way

1. In-place modification: Saves memory by not using extra space.

2. Early return: Simplifies handling of edge cases.

3. Efficient traversal: Ensures that each element is processed exactly once.

4. Pointer logic: Tracks unique elements efficiently, maintaining the array’s order.

5. Simplicity: Clear and concise code improves readability and adheres to LeetCode’s best practices for solutions.