Question 26

Delete the Repeating Item in a Sorted Array

We need to achieve this within Space Complexity O(1).

Approach: Double Pointer Technique

To solve the problem of deleting repeating items in a sorted array, we can use a two-pointer technique. Since the array is sorted, duplicates will appear consecutively, allowing us to easily remove them by using two pointers: one for tracking the unique elements and another for iterating through the array.

Steps:

1. Initialize two pointers:

   • The slow pointer will mark the position where the next unique element should be placed.
   • The fast pointer will iterate through the array.

2. Scan the array:

   • For each element in the array:
     • If the element at the fast pointer is different from the element at the slow pointer, increment the slow pointer and update arr[slow] with arr[fast].

3. After the loop:

   • The unique elements will be placed at the beginning of the array, and the length of the unique array will be slow + 1.

Time and Space Complexity:

• Time Complexity: (O(n)), where (n) is the length of the array. We make a single pass through the array.
• Space Complexity: (O(1)), as we modify the array in place and use a constant amount of extra space for the pointers.

Java Code Implementation

public class RemoveDuplicates {
    public static int removeDuplicates(int[] arr) {
        // Edge case: if the array is empty or has only one element
        if (arr.length == 0) {
            return 0;
        }

        int slow = 0;  // Pointer for placing unique elements

        // Iterate with the fast pointer
        for (int fast = 1; fast < arr.length; fast++) {
            // If we encounter a new unique element
            if (arr[fast] != arr[slow]) {
                slow++;  // Increment the slow pointer
                arr[slow] = arr[fast];  // Place the unique element at the slow pointer
            }
        }

        // The number of unique elements is slow + 1
        return slow + 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 4, 4, 5};
        int newLength = removeDuplicates(arr);
        System.out.println("New array with unique elements: ");
        for (int i = 0; i < newLength; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("\nNew length of the array: " + newLength);
    }
}