Skip to content
Hello Python

Discard Pairs with Two Pointers

Practice ExerciseInterviewEasyOpposite-direction Pointers

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement count_pairs_below(values, limit). values is sorted in nondecreasing order. Return the number of index pairs i < j whose values sum to less than limit, using the monotone effect of moving either endpoint.

Starter code

def count_pairs_below(values, limit):
    pass
Test cases

mixed-pairs

{
  "args": [
    [
      -2,
      0,
      1,
      3
    ],
    2
  ]
}

Expected: 4

none-valid

{
  "args": [
    [
      2,
      3,
      4
    ],
    1
  ]
}

Expected: 0

Wizard outline
  1. Step 1: Seed the pair count

    Return zero when fewer than two indices exist. The i < j contract requires two distinct positions before pointer movement matters.

  2. Step 2: Discard an invalid right endpoint

    Move right leftward while even the smallest available pair is too large. In sorted order, if values[left] + values[right] is invalid, every pair ending at right is invalid.

  3. Step 3: Count a full valid block

    Add every pair from the current left index through right when the endpoint sum is valid. If the largest partner at right works with values[left], every index between left + 1 and right also works.

  4. Step 4: Combine counting and discarding

    Apply the two monotone moves until the pointers meet. Mixed inputs alternate between eliminating an invalid right endpoint and counting a valid left block.

Footguns and prerequisites
  • When values[left] + values[right] is valid, there are right - left valid partners, not just one.
  • Moving left after an invalid sum cannot reduce the sum and may skip all valid smaller-right choices.
  • arrays strings two pointers sliding window
Reviewed references
Prepared Interview Problems
  • Count Subsequences by Minimum and Maximum(opens in a new tab)

    Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing subsequences min max target as a complete Interview Problem.

  • Find K Closest Elements(opens in a new tab)

    Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing find k closest elements as a complete Interview Problem.

  • Maximum Container Area(opens in a new tab)

    Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing container with most water as a complete Interview Problem.

  • Shortest Subarray to Remove for Sorted Order(opens in a new tab)

    Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing shortest subarray remove sorted as a complete Interview Problem.

  • Unique Zero-Sum Triplets(opens in a new tab)

    Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing three sum as a complete Interview Problem.

Recommended approach and implementation

Sorted order lets one successful smallest-plus-largest comparison certify several pairs with the same left endpoint. Every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped.

Why it works: When the endpoint sum is within the limit, pairing left with every index through right is also valid, adding exactly right-left pairs. Otherwise every pair using right is too large, so decrementing right discards no valid pair.

def count_pairs_below(values, limit):
    left, right = 0, len(values) - 1
    count = 0
    while left < right:
        if values[left] + values[right] < limit:
            count += right - left
            left += 1
        else:
            right -= 1
    return count