Skip to content

Two pointers

Quote

“Algorithmic complexity for structured programmers: All algorithms are \(\boldsymbol{O(f(n))}\), where \(\boldsymbol{f}\) is someone else's responsibility.” — Peter Cooper

Make use of two pointers to solve problems that require traversing a sequence of elements.

Common problems:

int[] twoSum(int[] nums, int target) {
    for (var i = 0; i < nums.length; i++) {
        for (var j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[]{i, j}
            }
        }
    }
    return []
}

int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (nums.slice(i + 1).includes(complement)) {
      return [i, nums.indexOf(complement, i + 1)];
    }
  }
  return undefined;
}

fun twoSum(nums: IntArray, target: Int): IntArray {
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[j] == target - nums[i]) {
                return intArrayOf(i, j)
            }
        }
    }
    return intArrayOf()
}

def two_sum(self, nums: list[int], target: int) -> list[int] | None:
    for i, num in enumerate(nums):
        complement = target - num
        if complement in nums[i + 1:]:
            return [i, nums.index(complement, i + 1)]
    return None

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (nums.slice(i + 1).includes(complement)) {
      return [i, nums.indexOf(complement, i + 1)];
    }
  }
  return undefined;
}

Sliding window

Restrict the range of the two pointers to a certain window size or condition.

Common problems:

int lengthOfLongestSubstring(String s) {
    HashSet<Character> characters = []
    var start = 0
    var end = 0
    var maxLength = Integer.MIN_VALUE
    while (end < s.length()) {
        if (characters.add(s.charAt(end))) {
            maxLength = Math.max(maxLength, characters.size())
            end++
            continue
        }
        characters.remove(s.charAt(start))
        start++
    }
    return maxLength
}

int lengthOfLongestSubstring(String s) {
    Set<Character> characters = new HashSet<>();
    int start = 0;
    int end = 0;
    int maxLength = Integer.MIN_VALUE;
    while (end < s.length()) {
        if (characters.add(s.charAt(end))) {
            maxLength = Math.max(maxLength, characters.size());
            end++;
            continue;
        }
        characters.remove(s.charAt(start));
        start++;
    }
    return maxLength;
}

function lengthOfLongestSubstring(s) {
    const characters = new Set();
    let start = 0;
    let end = 0;
    let maxLength = Number.MIN_SAFE_INTEGER;
    while (end < s.length) {
      if (!characters.has(s[end])) {
        characters.add(s[end]);
        end++;
        maxLength = Math.max(maxLength, characters.size);
        continue;
      }
      characters.delete(s[start]);
      start++;
    }
    return maxLength;
  }

fun lengthOfLongestSubstring(s: String): Int {
    val characters = hashSetOf<Char>()
    var start = 0
    var end = 0
    var maxLength = Int.MIN_VALUE
    while (end < s.length) {
        if (characters.add(s[end])) {
            maxLength = max(maxLength, characters.size)
            end++
            continue
        }
        characters -= s[start]
        start++
    }
    return maxLength
}

def length_of_longest_substring(self, s: str) -> int:
    characters = set()
    start = 0
    end = 0
    max_length = -maxsize
    while end < len(s):
        if s[end] not in characters:
            characters.add(s[end])
            end += 1
            max_length = max(max_length, len(characters))
            continue
        characters.remove(s[start])
        start += 1

function lengthOfLongestSubstring(s: string): number {
    const characters = new Set<string>();
    let start = 0;
    let end = 0;
    let maxLength = Number.MIN_SAFE_INTEGER;
    while (end < s.length) {
      if (!characters.has(s[end])) {
        characters.add(s[end]);
        end++;
        maxLength = Math.max(maxLength, characters.size);
        continue;
      }
      characters.delete(s[start]);
      start++;
    }
    return maxLength;
  }

Fast-slow pointers

Pointers that move at different speeds to find a cycle or a specific condition.

Common problems:

boolean hasCycle(SinglyListNode head) {
    var slow = head.next
    var fast = head.next.next
    while (fast != null && fast.hasNext() && slow != fast) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow == fast
}

boolean hasCycle(ListNode head) {
    SinglyListNode slow = head.next;
    SinglyListNode fast = head.next.next;
    while (fast != null && fast.hasNext() && slow != fast) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow == fast;
}

function hasCycle(head) {
  let slow = head.next;
  let fast = head.next.next;
  while (fast && fast.hasNext() && slow !== fast) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow === fast;
}

fun hasCycle(head: SinglyListNode?): Boolean {
    if (head?.next == null) {
        return false
    }
    var slow = head.next
    var fast = head.next!!.next
    while (fast != null && fast.hasNext() && slow !== fast) {
        slow = slow!!.next
        fast = fast.next!!.next
    }
    return slow === fast
}

def has_cycle(self, head: ListNode) -> bool:
    slow = head.next
    fast = head.next.next
    while fast and fast.next and slow != fast:
        slow = slow.next
        fast = fast.next.next
    return slow == fast

function hasCycle(head: SinglyListNode | undefined): boolean {
  let slow = head.next;
  let fast = head.next.next;
  while (fast && fast.hasNext() && slow !== fast) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow === fast;
}

Problem characteristics

  • The data structure is linear
  • The task is to find more than one element