Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Hashing & Two Pointers

Pair Sum in a Sorted Array

Easy · Hashing & Two Pointers · Asked at Amazon, Microsoft, TCS, Infosys, Wipro

The array is sorted in non-decreasing order. Count the pairs of indices i < j with a[i] + a[j] = target.

Input

First line: n target. Second line: the sorted array.

Output

The number of pairs.

Constraints

Two pointers from both ends. When the sum matches, count the run of equal values on each side (careful when both pointers are inside the same run).

Example 1

Input

5 6
1 2 3 4 5

Output

2

Example 2

Input

4 4
2 2 2 2

Output

6

Hints

  1. Start with pointers at both ends. If the sum is too small, move the left pointer right; if too big, move the right pointer left.
  2. When the sum matches, count how many copies of a[l] and of a[r] there are. If a[l] == a[r], all remaining elements are equal: there are c·(c−1)/2 pairs.

Approach

Two pointers l = 0, r = n−1. If a[l] + a[r] < target, advance l; if greater, retreat r. On a match with a[l] ≠ a[r], count the run cl of values equal to a[l] and the run cr equal to a[r]; they form cl · cr pairs; skip both runs. If a[l] == a[r], every element between them is that value, so add c(c−1)/2 with c = r − l + 1 and stop. Use 64-bit counts — up to ~5·10^9 pairs.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long t;
    cin >> n >> t;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    long long cnt = 0;
    int l = 0, r = n - 1;
    while (l < r) {
        long long s = a[l] + a[r];
        if (s < t) l++;
        else if (s > t) r--;
        else if (a[l] == a[r]) {
            long long c = r - l + 1;
            cnt += c * (c - 1) / 2;
            break;
        } else {
            long long cl = 1, cr = 1;
            while (l + 1 < r && a[l + 1] == a[l]) l++, cl++;
            while (r - 1 > l && a[r - 1] == a[r]) r--, cr++;
            cnt += cl * cr;
            l++;
            r--;
        }
    }
    cout << cnt << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, t, a = data[0], data[1], data[2:]
cnt, l, r = 0, 0, n - 1
while l < r:
    s = a[l] + a[r]
    if s < t:
        l += 1
    elif s > t:
        r -= 1
    elif a[l] == a[r]:
        c = r - l + 1
        cnt += c * (c - 1) // 2
        break
    else:
        cl = cr = 1
        while l + 1 < r and a[l + 1] == a[l]:
            l += 1
            cl += 1
        while r - 1 > l and a[r - 1] == a[r]:
            r -= 1
            cr += 1
        cnt += cl * cr
        l += 1
        r -= 1
print(cnt)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long t = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        long cnt = 0;
        int l = 0, r = n - 1;
        while (l < r) {
            long s = a[l] + a[r];
            if (s < t) l++;
            else if (s > t) r--;
            else if (a[l] == a[r]) {
                long c = r - l + 1;
                cnt += c * (c - 1) / 2;
                break;
            } else {
                long cl = 1, cr = 1;
                while (l + 1 < r && a[l + 1] == a[l]) { l++; cl++; }
                while (r - 1 > l && a[r - 1] == a[r]) { r--; cr++; }
                cnt += cl * cr;
                l++;
                r--;
            }
        }
        System.out.println(cnt);
    }
}

Solve Pair Sum in a Sorted Array online · All practice problems