SimuVedaAlgorithms Lab Open in the lab

Patterns / Beginner

Fast and Slow Pointers Visualizer

fast reads every value. slow marks where the next kept value should go.

Start the Fast and Slow Pointers simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Sorted, so duplicates sit next to each other. Everything up to slow is unique. [1, 1, 2, 3, 3, 3, 4, 5, 5, 6]
  2. Is a[fast] = 1 different from a[slow] = 1?
  3. No, it is a duplicate. Skip it.
  4. Is a[fast] = 2 different from a[slow] = 1?
  5. Yes. Move slow up and copy 2 to index 1. [1, 2, 1, 3, 3, 3, 4, 5, 5, 6]
  6. Is a[fast] = 3 different from a[slow] = 2?
  7. Yes. Move slow up and copy 3 to index 2. [1, 2, 3, 1, 3, 3, 4, 5, 5, 6]
  8. Is a[fast] = 3 different from a[slow] = 3?
  9. No, it is a duplicate. Skip it.
  10. Is a[fast] = 3 different from a[slow] = 3?
  11. No, it is a duplicate. Skip it.
  12. Is a[fast] = 4 different from a[slow] = 3?
  13. Yes. Move slow up and copy 4 to index 3. [1, 2, 3, 4, 3, 3, 1, 5, 5, 6]
  14. Is a[fast] = 5 different from a[slow] = 4?
  15. Yes. Move slow up and copy 5 to index 4. [1, 2, 3, 4, 5, 3, 1, 3, 5, 6]
  16. Is a[fast] = 5 different from a[slow] = 5?
  17. No, it is a duplicate. Skip it.
  18. Is a[fast] = 6 different from a[slow] = 5?
  19. Yes. Move slow up and copy 6 to index 5. [1, 2, 3, 4, 5, 6, 1, 3, 5, 3]
  20. Done. The first 6 values are unique. Return 6.

Try it with your own input →

Fast and slow pointers in Java, Python, C++, C and JavaScript

int removeDuplicates(int[] a) {
  int slow = 0;
  for (int fast = 1; fast < a.length; fast++) {
    if (a[fast] != a[slow]) {
      slow++;
      a[slow] = a[fast];
    }
  }
  return slow + 1;
}
def remove_duplicates(a):
    slow = 0
    for fast in range(1, len(a)):
        if a[fast] != a[slow]:
            slow += 1
            a[slow] = a[fast]
    return slow + 1
int removeDuplicates(vector<int>& a) {
  int slow = 0;
  for (int fast = 1; fast < (int)a.size(); fast++) {
    if (a[fast] != a[slow]) {
      slow++;
      a[slow] = a[fast];
    }
  }
  return slow + 1;
}
int removeDuplicates(int a[], int n) {
  int slow = 0;
  for (int fast = 1; fast < n; fast++) {
    if (a[fast] != a[slow]) {
      slow++;
      a[slow] = a[fast];
    }
  }
  return slow + 1;
}
function removeDuplicates(a) {
  let slow = 0;
  for (let fast = 1; fast < a.length; fast++) {
    if (a[fast] !== a[slow]) {
      slow++;
      a[slow] = a[fast];
    }
  }
  return slow + 1;
}

In an interview

LeetCode 26, Remove Duplicates from Sorted Array, in place.

Mention the linked-list version too: fast moves 2 steps and slow 1, and they meet if there is a cycle (Floyd’s algorithm).

More patterns