Remove Duplicates

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Remove duplicate elements from sorted array in-place.

Algorithm

1Two pointers: write pointer w=0. For each element arr[i]: if arr[i] != arr[w]: arr[++w] = arr[i]. Return w+1.

Common Pitfalls

•Same as LC 26. O(n) O(1). Works only on sorted arrays. For unsorted: use hashset.

Remove Duplicates.java

Java

// Approach: Linked list: traverse keeping previous; skip duplicate consecutive nodes.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    String removeDups(String str) {
        HashSet<Character> set = new HashSet<>();

        StringBuilder ans = new StringBuilder();

        for (char c : str.toCharArray()) {
            if (!set.contains(c))
                ans.append(c);
            set.add(c);
        }

        return ans.toString();
    }
}

Was this solution helpful?