Two pointers: time and space complexity

High interview relevanceRoadmap: Beginner

Time	O(n)
Space	O(1)

Why it costs this much

Each pointer only moves in one direction, so together they make at most n moves.

Code

def pair_sum(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo < hi:                  # lo and hi only move inward: at most n steps
        s = sorted_nums[lo] + sorted_nums[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

Common pitfalls

It needs sorted or otherwise ordered input, and sorting first adds O(n log n). Be able to explain why moving a pointer cannot skip the answer.