Two Pointers

Two pointers use a proven ordering property to move indices without revisiting all pairs. One common version approaches from opposite ends of a sorted array to find a target-sum pair. Another reads a sorted sequence while writing a duplicate-free prefix. Both are linear because each pointer moves in only one direction. The trick is not the number of variables, but proving that every discarded candidate is unnecessary.

Prerequisites: Sorted arrays; loops; correctness of comparisons.

Build the idea

1. 1. Start from extreme candidates

   For a nondecreasing array, let left=0 and right=n−1. Their sum uses the smallest and largest remaining values. If it equals the target, the two distinct positions form a valid pair. The loop condition left<right prevents using one position twice. Equal values at different indices remain legal.

2. 2. Justify eliminating one endpoint

   If a[left]+a[right]<target, pairing that left value with any smaller remaining right value cannot help, so discard left. If the sum is too large, pairing that right value with any larger remaining left value also cannot help, so discard right. Sorted order, not nonnegativity, proves these eliminations; signed sorted arrays work too.

3. 3. Trace a target pair

   For [1,1,2,3,5] and target 4, extremes give 1+5=6, so right moves from 4 to 3. Now 1+3=4, returning indices 0 and 3. If the input were unsorted, moving right based on one large value would not prove anything about the rest. Sorting would enable the search but change original indices unless each value retained its original position.

4. 4. Compact duplicates with read/write pointers

   After the search, scan read from zero upward. write is the length of the unique prefix. Copy a[read] when write==0 or it differs from the last kept value a[write−1]. Because input is sorted, every duplicate value is consecutive. For the example, keep 1 once, then 2,3,5, and resize to length 4. The read pointer never falls behind written data needed for comparison.

5. 5. Separate a witness from counting

   This pair procedure returns one pair, not the number of all index pairs. Counting would need multiplicity handling, especially with duplicate values. Similarly, deduplication intentionally discards repeated values, which is appropriate only if the requested result is unique values. For unsorted deduplication use sorting or a membership structure with an explicit order requirement.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
int main(){
    int n;
    long long target;
    std::cin>>n>>target;
    std::vector<long long>a(n);
    for(long long&x:a){
        std::cin>>x;
    }
    int left=0,right=n-1,answerL=-1,answerR=-1;
    while(left<right){
        long long sum=a[left]+a[right];
        if(sum==target){
            answerL=left;
            answerR=right;
            break;
        }
        if(sum<target){
            ++left;
        }
        else{
            --right;
        }
    }
    if(answerL==-1){
        std::cout<<"NONE\n";
    }
    else{
        std::cout<<answerL<<' '<<answerR<<'\n';
    }
    int write=0;
    for(int read=0;read<n;++read){
        if(write==0||a[read]!=a[write-1]){
            a[write++]=a[read];
        }
    }
    a.resize(write); // Only the unique prefix is retained.
    for(int i=0;i<write;++i){
        std::cout<<a[i]<<(i+1==write?'\n':' ');
    }
    if(write==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n) time for pair search plus duplicate compaction, O(n) input storage and O(1) auxiliary memory. Each endpoint moves at most n times, and the read/write scan touches every input once. No sorting is performed; sorted input is a precondition. Sorting first would add O(n log n).

Example input and output

Read n target (0≤n≤200000), then n NONDECREASING values with |value|≤10^9. Print one pair of distinct zero-based indices summing to target, or NONE; then print the deduplicated sorted sequence.

Input

5 4
1 1 2 3 5

Output

0 3
1 2 3 5

The sum 1+5 is too large; moving the right endpoint to 3 produces 1+3=4. Duplicate compaction keeps one 1.

Practical applications

Use for sorted pair-sum witnesses, merging ordered sequences, deduplication and other scans with a monotone elimination rule. Sliding windows are a same-direction relative of the idea, but require a different invariant. A hash table can find unsorted pair sums with expected linear time, at additional space and hashing tradeoffs.

Check your understanding

Why may left advance when the current extreme sum is too small?

Put it into practice

Count all target-sum index pairs, including duplicate-value multiplicities.