Remove Duplicates from Sorted Array - Java Solution

1. Introduction

In this blog post, we will address a common problem in array manipulation - removing duplicates from a sorted array. The challenge is to do this in place with O(1) extra memory, modifying the original array to store the result.

Problem

Given a sorted array, remove all the duplicates such that each element appears only once, and return the new length. Do not allocate extra space for another array.

Example:

Given array [1, 1, 1, 3, 5, 5, 7]

The output should be 4, with the first four elements of the array being [1, 3, 5, 7]

2. Solution Steps

1. Initialize a pointer (index) to track the position of the non-duplicate elements.

2. Iterate through the array, starting from the second element.

3. Compare the current element with the previous one.

4. If they are different, increment index and update the array at index with the current element.

5. Continue this process until the end of the array.

6. Return index + 1, which is the new length of the array without duplicates.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 3, 5, 5, 7};
        int newLength = removeDuplicates(nums);
        System.out.println("New length: " + newLength);
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    // Method to remove duplicates from a sorted array
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[index]) {
                index++;
                nums[index] = nums[i]; // Update the array with the non-duplicate element
            }
        }
        return index + 1; // New length of the array
    }
}

Output:

New length: 4
1 3 5 7

Explanation:

In the given array [1, 1, 1, 3, 5, 5, 7], the removeDuplicates method iterates through the array and identifies unique elements. It places these unique elements at the start of the array, effectively removing duplicates. The method returns 4, indicating the new length of the array, and the first four elements are the non-duplicate values [1, 3, 5, 7].