In-Place Slow–Fast Scan Pattern: Remove Duplicates from a Sorted Array

The in-place Slow–Fast Scan pattern is designed for problems where data must be processed or cleaned without allocating extra memory. By separating reading and writing responsibilities between two forward-moving pointers, this pattern enables efficient in-place transformations. We’ll explore it through a sorted-array example.

Pattern Definition

The in-place Slow–Fast Scan pattern is used when you want to filter or clean data directly inside an array, without using extra memory.

The idea is simple:

Both pointers move forward, but they serve different purposes.

This separation of responsibility lets us modify the array in place, efficiently.

Problem

You are given a sorted array of integers.

Your task is to remove duplicate elements in place so that each unique element appears only once.

You must return the new length of the array that contains only unique values.

Only the first k elements (where k is the returned length) are considered valid.

Input

nums = [1, 1, 2, 2, 3, 3, 4, 4, 5]

Output

Updated array (first part): [1, 2, 3, 4, 5]
New length: 5

Why the Slow–Fast Scan Works Here

The array is sorted, which means:

The slow pointer always points to the last confirmed unique value,

while the fast pointer checks the next values and decides whether they’re new or duplicates.

Step-by-Step Intuition

Before we walk through the array, let’s be clear about the roles:

Now let’s look at the input:

[1, 1, 2, 2, 3, 3, 4, 4, 5]

By the time the fast pointer reaches the end:

Kotlin Implementation

fun removeDuplicates(nums: IntArray): Int {
    if (nums.size < 2) return nums.size

    var slow = 0

    for (fast in 1 until nums.size) {
        if (nums[slow] != nums[fast]) {
            slow++
            nums[slow] = nums[fast]
        }
    }
    return slow + 1
}

fun main() {
    val nums = intArrayOf(1, 1, 2, 2, 3, 3, 4, 4, 5)
    val newLength = removeDuplicates(nums)
    val result = nums.sliceArray(0 until newLength)
    println(result.joinToString())
}

Flow (Step-by-Step)

Start
  |
  v
If array size < 2:
  return size
  |
  v
Initialize slow = 0
  |
  v
Move fast from index 1 to end:
  |
  v
If nums[fast] != nums[slow]:
  slow++
  nums[slow] = nums[fast]
  |
  v
Continue until fast reaches end
  |
  v
Return slow + 1

Real-Time Analogy

Imagine cleaning a sorted attendance list:

You read names one by one:

You don’t rewrite the whole list.

You simply compress it, keeping only the first occurrence of each name.

That’s exactly what the slow–fast scan does.

Real-World Use Cases

This pattern appears frequently in real systems:

Time & Space Complexity

Time Complexity: O(n)

The array is scanned exactly once. The fast pointer moves through every element, while the slow pointer advances only when a new unique value is found. Since both pointers move forward and never step back, the total work is linear.

Space Complexity: O(1)

The algorithm modifies the array in place and does not allocate any additional data structures. Apart from the two pointers, no extra memory is used, making it space-efficient.

Conclusion

The Remove Duplicates from Sorted Array problem is one of the cleanest examples of the in-place Slow–Fast Scan pattern. It shows how separating reading and writing responsibilities between two pointers allows us to clean data efficiently without using extra memory.

Once this idea clicks, many similar problems start to look familiar — only the condition for what counts as a “valid” element changes.