ProgramGuru.org

ProgramGuru.org

Remove Duplicates from Sorted Array - Optimal Solution

Remove Duplicates from Sorted Array - Optimal Solution

Visualization

Algorithm Steps

  1. Given a sorted array arr.
  2. Use two pointers: i to track unique elements and j to iterate through the array.
  3. Start with i = 0 and j = 1.
  4. If arr[j] != arr[i], increment i and update arr[i] = arr[j].
  5. Continue this until j reaches the end of the array.
  6. The first i + 1 elements are the array with duplicates removed.

Remove Duplicates using Two-Pointer Technique Code

Python
JavaScript
Java
C++
C
def remove_duplicates(arr):
    if not arr:
        return 0
    i = 0
    for j in range(1, len(arr)):
        if arr[j] != arr[i]:
            i += 1
            arr[i] = arr[j]
    return i + 1

# Sample Input
arr = [1, 1, 2, 2, 3, 4, 4]
k = remove_duplicates(arr)
print("After removing duplicates:", arr[:k])

Detailed Step by Step Example

Let's remove duplicates from the sorted array using the two-pointer technique.

{ "array": [1,1,2,2,3,4,4], "showIndices": true }

Initialize pointer i = 0 to track the last unique element. Start loop from j = 1.

Check index 1

Compare arr[1] = 1 with arr[0] = 1.

Duplicate found. Do nothing.

{ "array": [1,1,2,2,3,4,4], "showIndices": true, "highlightIndices": [0, 1], "labels": { "0": "i", "1": "j" } }

Check index 2

Compare arr[2] = 2 with arr[0] = 1.

Values are different. Increment i to 1 and set arr[1] = 2.

{ "array": [1,2,2,2,3,4,4], "showIndices": true, "highlightIndices": [1, 2], "labels": { "1": "i", "2": "j" } }

Check index 3

Compare arr[3] = 2 with arr[1] = 2.

Duplicate found. Do nothing.

{ "array": [1,2,2,2,3,4,4], "showIndices": true, "highlightIndices": [1, 3], "labels": { "1": "i", "3": "j" } }

Check index 4

Compare arr[4] = 3 with arr[1] = 2.

Values are different. Increment i to 2 and set arr[2] = 3.

{ "array": [1,2,3,2,3,4,4], "showIndices": true, "highlightIndices": [2, 4], "labels": { "2": "i", "4": "j" } }

Check index 5

Compare arr[5] = 4 with arr[2] = 3.

Values are different. Increment i to 3 and set arr[3] = 4.

{ "array": [1,2,3,4,3,4,4], "showIndices": true, "highlightIndices": [3, 5], "labels": { "3": "i", "5": "j" } }

Check index 6

Compare arr[6] = 4 with arr[3] = 4.

Duplicate found. Do nothing.

{ "array": [1,2,3,4,3,4,4], "showIndices": true, "highlightIndices": [3, 6], "labels": { "3": "i", "6": "j" } }

Final Result:

Array without duplicates (first 4 elements): [1,2,3,4]