Big O Practice: Three Sum

def three_sum(nums):
    nums.sort()
    res = []
    n = len(nums)

    def skip_dups(i, step, bound):
        while i != bound and nums[i] == nums[i + step]:
            i += step
        return i

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
                continue
            if s > 0:
                hi -= 1
                continue
            res.append([nums[i], nums[lo], nums[hi]])
            lo = skip_dups(lo, 1, hi)
            hi = skip_dups(hi, -1, lo)
            lo += 1
            hi -= 1
    return res

Variables

• n - length of the input array nums

Explanation

Sorting is **O(n log n)**, then for each `i` the two-pointer scan is **O(n)** - quadratic dominates, total **O(n²)**. Auxiliary space is **O(1)** if we ignore the output and the in-place sort; some sort implementations use O(log n) stack.

More Big O practice problems · Today's daily problem