Remove Duplicates from a Sorted Array In-Place

• Two pointers – slow marks the end of the unique prefix, fast scans for the next distinct value.
• Sorted precondition – duplicates are adjacent, so a single linear scan can collapse them.
• Compact to front – unique values are compacted into the front of the array.
• Return new length – the unique count is slow + 1; the caller ignores elements beyond that.
• O(n) time, O(1) space – one pass with no extra data structures.

What is the problem?

Given a sorted array, remove duplicate values in place so each value appears exactly once. Return the count of unique values. In a banking context, the notification service at National Bank of India needs each distinct account identifier from a settlement run, so each account receives exactly one notification.

Why does the array need to be sorted?

Because the array is sorted, equal values are guaranteed to be adjacent. This means a single linear scan can detect and collapse all duplicates. If the array were unsorted, you would need a HashSet (O(n) space) or sorting first (O(n log n)).

How does the two-pointer technique work?

Start slow at index 0, treating the first element as already unique. Start fast at index 1. For each fast position, compare its value with the value at slow. If they differ, increment slow and copy the fast value there. If they are the same, skip.

package com.bank.service;

import java.math.BigDecimal;
import java.util.Arrays;

public class DuplicateRemover {

    public static int removeDuplicates(BigDecimal[] ids) {
        if (ids == null || ids.length == 0) {
            return 0;
        }
        int slow = 0;
        for (int fast = 1; fast < ids.length; fast++) {
            if (ids[fast].compareTo(ids[slow]) != 0) {
                slow++;
                ids[slow] = ids[fast];
            }
        }
        return slow + 1;
    }

    public static void main(String[] args) {
        BigDecimal[] accountIds = {
            new BigDecimal("1001"),
            new BigDecimal("1001"),
            new BigDecimal("1002"),
            new BigDecimal("1002"),
            new BigDecimal("1002"),
            new BigDecimal("1003"),
            new BigDecimal("1004")
        };
        int uniqueCount = removeDuplicates(accountIds);
        System.out.println("Unique count: " + uniqueCount);
        System.out.println("Unique prefix: " +
            Arrays.toString(Arrays.copyOf(accountIds, uniqueCount)));
    }
}

Unique count: 4
Unique prefix: [1001, 1002, 1003, 1004]

Why return the new length instead of a new array?

Java arrays are fixed-size and cannot shrink. The method compacts unique values into the front and returns the new logical length. The caller uses only that prefix and ignores the stale tail. This avoids allocating a second array.

Why use compareTo instead of equals for BigDecimal?

BigDecimal's equals checks both value and scale. The identifier 1001 and 1001.00 would be treated as different by equals even though they represent the same account. Using compareTo returning non-zero correctly identifies them as duplicates.

BigDecimal a = new BigDecimal("1001");
BigDecimal b = new BigDecimal("1001.00");
System.out.println(a.equals(b));         // false (scale differs)
System.out.println(a.compareTo(b) == 0); // true (same value)

What is the time and space complexity?

• Time: O(n) because each element is visited once by the fast pointer.
• Space: O(1) because no extra data structures are allocated.

What are common mistakes?

The most common mistake is forgetting to increment slow before the copy, which overwrites the last unique value. Another is using equals instead of compareTo for BigDecimal.

// Wrong: overwriting without incrementing slow
if (ids[fast].compareTo(ids[slow]) != 0) {
    ids[slow] = ids[fast]; // overwrites the value at slow
}

// Correct: increment slow first
if (ids[fast].compareTo(ids[slow]) != 0) {
    slow++;
    ids[slow] = ids[fast];
}

What about unsorted arrays?

For unsorted arrays you cannot use this technique because duplicates are not adjacent. Instead, use a HashSet to track seen values in O(n) time and O(n) space, or sort first in O(n log n) and then apply this technique.

What should a senior engineer know?

A senior engineer documents the method's contract clearly: it mutates the array, returns the new logical length, and the elements beyond that length are stale. The senior also knows that Java's Stream.distinct() does this functionally but allocates intermediate collections. For the settlement pipeline at National Bank of India, the in-place approach is preferred because it processes millions of identifiers without allocating a parallel structure.