Skip to content

Sum of Two Values

  • Title: Sum of Two Values
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1640
  • Secondary topics: Sort and scan, Original index recovery, Opposite-end pointers
  • Difficulty: medium
  • Subtype: Find two distinct positions whose values sum to a target
  • Status: solved
  • Solution file: sumoftwovalues.cpp

Why Practice This

This is one of the cleanest first examples of the "sorted opposite-end pointers" pattern.

It teaches three useful habits together:

  • sort the data to create monotonicity
  • move only one pointer at a time based on what the sum tells you
  • preserve original indices even after sorting

That makes it a great bridge between simple sorting tasks and full sliding-window reasoning.

Recognition Cue

Reach for opposite-end two pointers when:

  • you need one pair whose sum hits a target
  • values can be sorted
  • moving one endpoint changes the sum monotonically
  • you still need to recover original indices afterward

The strongest smell is:

  • "find two values with sum exactly x"

That is the classic sorted two-pointer pair search.

Problem-Specific Transformation

The statement is rewritten as:

  • pair each value with its original index
  • sort by value
  • search in the sorted order while preserving the answer indices externally

So the problem becomes:

  • one monotone sum scan on sorted values
  • plus one bookkeeping layer for original positions

Core Idea

Store each number together with its original index, then sort by value.

Let:

  • l start at the smallest value
  • r start at the largest value

At every step, check:

values[l] + values[r]

There are only three cases:

  • if the sum is too small, move l right
  • if the sum is too large, move r left
  • if the sum matches the target, output the two original indices

Why is this valid after sorting?

Because increasing l can only increase the sum, and decreasing r can only decrease the sum. That monotone behavior is exactly what makes two pointers work here.

Complexity

  • sorting: O(n log n)
  • two-pointer scan: O(n)
  • total: O(n log n)

Pitfalls / Judge Notes

  • You must output the original positions, not the sorted positions.
  • The two chosen elements must be distinct, so the loop should run while l < r.
  • Use long long for the sum if you want one less thing to worry about when values get large.
  • If no pair works, print IMPOSSIBLE.

Reusable Pattern

Solutions