Definition
- Remove Duplicates – given a sorted array or linked list, remove duplicate elements in place so each value appears only once.
- Slow-fast pointers – slow marks the end of the unique prefix, fast scans ahead; when fast finds a new value, copy it to slow + 1.
- Array version – returns the new logical length; elements beyond slow are ignored.
- Linked list version – unlinks duplicate nodes by adjusting next pointers.
- Complexity – O(n) time, O(1) extra space.
Imagine Rajesh has a sorted ledger of account numbers where the same account appears several times in a row because of repeated entries. He keeps one finger on the last unique account and reads forward with another finger. Whenever the reading finger sees an account different from the last unique one, he writes it right after his confirmed section and moves his confirming finger forward.
Understanding the Concepts
What is the Remove Duplicates problem?
Given a sorted array or sorted linked list, remove duplicate elements in place so each element appears only once, and return the new length (array) or the de-duplicated list. No extra structure may be allocated. Because the data is sorted, every group of equal values is contiguous, so duplicates are always neighbours.
package com.bank.service;
public class DuplicateRemover {
// Returns the count of unique elements
public int removeDuplicates(int[] sorted) {
// implementation below
return 0;
}
}
How does the slow-fast pointer approach work for arrays?
Keep a slow index at position 0, pointing to the last unique element. Scan with a fast index from 1 to the end. If arr[fast] differs from arr[slow], increment slow and copy arr[fast] into arr[slow]. If they are equal, skip. After the scan, positions 0 through slow hold the unique values, and the unique count is slow + 1.
package com.bank.service;
public class AccountDeduplicator {
public static int removeDuplicates(int[] accounts) {
if (accounts.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < accounts.length; fast++) {
if (accounts[fast] != accounts[slow]) {
slow++;
accounts[slow] = accounts[fast];
}
}
return slow + 1;
}
public static void main(String[] args) {
int[] accounts = {101, 101, 102, 103, 103, 103, 104};
int uniqueCount = removeDuplicates(accounts);
System.out.print("Unique accounts: ");
for (int i = 0; i < uniqueCount; i++) {
System.out.print(accounts[i] + " ");
}
System.out.println("(count: " + uniqueCount + ")");
}
}
Unique accounts: 101 102 103 104 (count: 4)
How does the linked list version work?
Walk a current pointer through the sorted list. While current.next exists and has the same value as current, bypass the duplicate by setting current.next = current.next.next. Otherwise advance current. This removes all consecutive duplicates in one pass.
package com.bank.service;
public class SortedListDeduplicator {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public static ListNode removeDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next; // unlink duplicate
} else {
current = current.next;
}
}
return head;
}
public static void main(String[] args) {
ListNode head = new ListNode(101);
head.next = new ListNode(101);
head.next.next = new ListNode(102);
head.next.next.next = new ListNode(103);
head.next.next.next.next = new ListNode(103);
ListNode result = removeDuplicates(head);
while (result != null) {
System.out.print(result.val + " ");
result = result.next;
}
}
}
101 102 103
What is the "allow at most two" variant?
A common variant allows each element to appear at most twice. For the array version, compare arr[fast] against arr[slow - 1] instead of arr[slow]. If they differ, the value has appeared fewer than twice, so copy it.
package com.bank.service;
public class AllowTwoDuplicates {
public static int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
int slow = 1;
for (int fast = 2; fast < nums.length; fast++) {
if (nums[fast] != nums[slow - 1]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
public static void main(String[] args) {
int[] nums = {101, 101, 101, 102, 102, 103};
int len = removeDuplicates(nums);
for (int i = 0; i < len; i++) System.out.print(nums[i] + " ");
}
}
101 101 102 102 103
What about the harder linked list variant?
The harder variant removes all nodes that ever had a duplicate. A dummy head is needed because even the original head might be removed. Walk with a prev pointer; when prev.next and prev.next.next have the same value, skip the entire run of that value.
package com.bank.service;
public class RemoveAllDuplicates {
static class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public static ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
if (prev.next.val == prev.next.next.val) {
int dupVal = prev.next.val;
while (prev.next != null && prev.next.val == dupVal) {
prev.next = prev.next.next;
}
} else {
prev = prev.next;
}
}
return dummy.next;
}
}
What are edge cases?
Edge cases include an empty array (return 0), a single element (return 1), and an array where all elements are the same (return 1). For the linked list, an empty list returns null and a single-node list returns the node unchanged.
removeDuplicates(new int[]{}); // 0
removeDuplicates(new int[]{42}); // 1
removeDuplicates(new int[]{5, 5, 5}); // 1
What are common mistakes?
The most common mistake is returning slow instead of slow + 1 for the array version, which undercounts by one. Another is advancing current inside the if-branch of the linked list version, which skips the comparison of the new next node.
// Wrong: advance current after unlinking
if (current.val == current.next.val) {
current.next = current.next.next;
current = current.next; // BUG: skips comparison
}
// Correct: only advance in the else branch
if (current.val == current.next.val) {
current.next = current.next.next; // stay at current
} else {
current = current.next;
}
What should a senior engineer know?
A senior engineer knows the three variants (unique only, allow two, remove all duplicated nodes), which comparison to use for each, and when a dummy head is needed. They know the array method cannot physically shrink the array in Java, so the logical length is returned and the tail is ignored. They handle the comparison correctly for both primitive and object types.
Visual Overview
Array: [101, 101, 102, 103, 103, 103, 104]
slow
fast
Step 1: fast=1, arr[1]=101 == arr[slow]=101 --> skip
Step 2: fast=2, arr[2]=102 != arr[slow]=101 --> slow++, copy
[101, 102, 102, 103, 103, 103, 104]
slow
Step 3: fast=3, arr[3]=103 != arr[slow]=102 --> slow++, copy
[101, 102, 103, 103, 103, 103, 104]
slow
Step 4: fast=4, arr[4]=103 == arr[slow]=103 --> skip
Step 5: fast=5, arr[5]=103 == arr[slow]=103 --> skip
Step 6: fast=6, arr[6]=104 != arr[slow]=103 --> slow++, copy
[101, 102, 103, 104, 103, 103, 104]
slow
Unique prefix: [101, 102, 103, 104]
Count: slow + 1 = 4
Linked List:
101 -> 101 -> 102 -> 103 -> 103 -> null
^curr
101 == 101 --> unlink: 101 -> 102 -> 103 -> 103
^curr
101 != 102 --> advance
^curr
102 != 103 --> advance
^curr
103 == 103 --> unlink: 101 -> 102 -> 103 -> null
Key Takeaway
Removing duplicates from a sorted structure in place relies on one key fact: because the data is sorted, every group of equal values sits together, so I only need to compare each element to the previous kept element. That lets me solve it in a single O(n) pass with O(1) extra space using a slow-fast two-pointer scheme.
For the array version I keep a slow pointer at the last unique element and scan forward with a fast pointer. Whenever the fast element differs from the slow element, I advance slow and copy the fast element in, building the unique prefix in place. The unique count is slow + 1, and everything beyond that is leftover garbage. For the sorted linked list I walk a single pointer and unlink nodes whose value equals the current node's value.
The senior-level point is knowing the variants. If the requirement allows each element at most twice, I compare fast against slow - 1 instead of slow. For the harder linked-list variant that removes every node that ever had a duplicate, I use a dummy head so I have a stable handle before a run of duplicates.
In my banking project at the National Bank of India, I used this to clean a sorted feed of account numbers from a partner, where overlapping export windows produced repeats. The feed was large, so allocating a second array was not acceptable, and the in-place slow-fast sweep collapsed the repeats cheaply before reconciliation ran.
Remember one sentence: in sorted data, keep a slow pointer at the last unique element and advance it only when the fast pointer finds a new value, giving O(n) in-place deduplication.
---