SimuVedaAlgorithms Lab Open in the lab

Patterns / Beginner

Two Pointers (Opposite Ends) Visualizer

Start at both ends. If the sum is too small, move the left pointer right. If too big, move the right pointer left.

Start the Two Pointers (Opposite Ends) 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(1)
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. The values are sorted. Put one pointer at each end. Target is 17. [1, 3, 4, 6, 8, 11, 13, 15]
  2. 1 + 15 = 16.
  3. 16 < 17. Need a bigger sum, so move l right.
  4. 3 + 15 = 18.
  5. 18 > 17. Need a smaller sum, so move r left.
  6. 3 + 13 = 16.
  7. 16 < 17. Need a bigger sum, so move l right.
  8. 4 + 13 = 17.
  9. That equals 17. Answer: indexes 2 and 6.

Try it with your own input →

Two pointers (opposite ends) in Java, Python, C++, C and JavaScript

int[] twoSum(int[] a, int target) {
  int l = 0, r = a.length - 1;
  while (l < r) {
    int sum = a[l] + a[r];
    if (sum == target) return new int[]{l, r};
    if (sum < target) l++;
    else r--;
  }
  return new int[]{-1, -1};
}
def two_sum(a, target):
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return [l, r]
        if s < target:
            l += 1
        else:
            r -= 1
    return [-1, -1]
vector<int> twoSum(const vector<int>& a, int target) {
  int l = 0, r = (int)a.size() - 1;
  while (l < r) {
    int sum = a[l] + a[r];
    if (sum == target) return {l, r};
    if (sum < target) l++;
    else r--;
  }
  return {-1, -1};
}
void twoSum(int a[], int n, int target, int out[2]) {
  int l = 0, r = n - 1;
  while (l < r) {
    int sum = a[l] + a[r];
    if (sum == target) { out[0] = l; out[1] = r; return; }
    if (sum < target) l++;
    else r--;
  }
  out[0] = out[1] = -1;
}
function twoSum(a, target) {
  let l = 0, r = a.length - 1;
  while (l < r) {
    const sum = a[l] + a[r];
    if (sum === target) return [l, r];
    if (sum < target) l++;
    else r--;
  }
  return [-1, -1];
}

In an interview

LeetCode 167, Two Sum II: in a sorted array, find two values that add up to the target.

Because the array is sorted, every move safely rules out a whole row of pairs. That is why it is O(n) instead of O(n²).

More patterns