3Sum Smaller

func threeSumSmaller(nums []int, target int) int {

}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0

    // Fix an anchor, then scan the rest for pairs that keep the total under target.
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0

    // Fix an anchor, then scan the rest for pairs that keep the total under target.
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
        }
    }
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0

    // Fix an anchor, then scan the rest for pairs that keep the total under target.
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            // Key insight: the array is sorted, so if the WIDEST pair
            // (left, right) is already under target, then pairing left with
            // every index between left+1 and right is under target too.
            // That's (right - left) valid pairs — count them all at once.
        }
    }
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0

    // Fix an anchor, then scan the rest for pairs that keep the total under target.
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            // Key insight: the array is sorted, so if the WIDEST pair
            // (left, right) is already under target, then pairing left with
            // every index between left+1 and right is under target too.
            // That's (right - left) valid pairs — count them all at once.
            if nums[i]+nums[left]+nums[right] < target {
                count += right - left
                left++
            }
        }
    }
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0

    // Fix an anchor, then scan the rest for pairs that keep the total under target.
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            // Key insight: the array is sorted, so if the WIDEST pair
            // (left, right) is already under target, then pairing left with
            // every index between left+1 and right is under target too.
            // That's (right - left) valid pairs — count them all at once.
            if nums[i]+nums[left]+nums[right] < target {
                count += right - left
                left++
                // Otherwise the sum is too big; the only way to shrink it is to
                // pull the right pointer inward to a smaller value.
            }
        }
    }
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0

    // Fix an anchor, then scan the rest for pairs that keep the total under target.
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            // Key insight: the array is sorted, so if the WIDEST pair
            // (left, right) is already under target, then pairing left with
            // every index between left+1 and right is under target too.
            // That's (right - left) valid pairs — count them all at once.
            if nums[i]+nums[left]+nums[right] < target {
                count += right - left
                left++
            } else {
                // Otherwise the sum is too big; the only way to shrink it is to
                // pull the right pointer inward to a smaller value.
                right--
            }
        }
    }
}

func threeSumSmaller(nums []int, target int) int {
    // Sort so the converging scan works — and so we can count many valid pairs
    // in a single step instead of one at a time.
    sort.Ints(nums)
    count := 0

    // Fix an anchor, then scan the rest for pairs that keep the total under target.
    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1
        for left < right {
            // Key insight: the array is sorted, so if the WIDEST pair
            // (left, right) is already under target, then pairing left with
            // every index between left+1 and right is under target too.
            // That's (right - left) valid pairs — count them all at once.
            if nums[i]+nums[left]+nums[right] < target {
                count += right - left
                left++
            } else {
                // Otherwise the sum is too big; the only way to shrink it is to
                // pull the right pointer inward to a smaller value.
                right--
            }
        }
    }

    return count // O(n^2)
}