Count weight triples that stay under a limit

Two pointers Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
w, limit = [1, 2, 3, 4], 8
count = 0
for i in range(len(w)):
    for j in range(i + 1, len(w)):
        for k in range(j + 1, len(w)):
            if w[i] + w[j] + w[k] < limit:
                count += 1
print(count)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2

Right: 1+2+3 = 6 and 1+2+4 = 7 are under 8; 1+3+4 and 2+3+4 are not.

The brute force agrees with the two-pointer count; checking against it on small inputs is how this page's solution is tested.

Why not the others?
  • B 3. 1 + 3 + 4 is exactly 8, which is not strictly less.
  • C 4. Only two of the four triples fit.

30-second answer

Sort the weights. Fix the smallest parcel i, then run two pointers lo = i + 1 and hi = end. If w[i] + w[lo] + w[hi] is under the limit, every parcel between lo and hi also works with i and lo, so add hi - lo and move lo up; otherwise move hi down. O(n²) time after an O(n log n) sort, versus O(n³) for all triples. The sorted copy takes O(n) space.

Practise saying it · 60 s. No recording, just a timer

Explain the sort-and-two-pointers count for triples.

Say your answer out loud, then check which of these points you covered:

  • Sort first
  • Fix one, sweep two
  • Count hi - lo at once; O(n²)

Deep dive

Counting hi - lo at once is the key step: sortedness means all those middle choices are even lighter than hi.

Sorting changes positions, but the question counts sets of parcels, so the count is the same.

O(n²) is the expected answer for triple-sum style questions; better bounds need much heavier machinery.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def count_triples(weights: list[int], limit: int) -> int:
    w = sorted(weights)
    total = 0
    for i in range(len(w) - 2):
        j, k = i + 1, len(w) - 1
        while j < k:
            if w[i] + w[j] + w[k] < limit:
                total += k - j  # every third pick in (j, k] fits
                j += 1
            else:
                k -= 1
    return total

Common mistakes

  • Adding 1 instead of hi - lo when the sum fits, which undercounts.
  • Using <= when the limit is strict.

Senior take & follow-ups

Explain the 'count a whole block at once' step with a tiny example. It is where most candidates go wrong.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if you need triples that equal the target exactly?

    Show hint

    Same skeleton; on a match, skip runs of equal values to avoid counting duplicates if values must be distinct.

  2. What about pairs?

    Show hint

    Drop the outer loop: one two-pointer sweep, O(n log n) with the sort.

What each operation costs: Arrays · Array Operations

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.