Getting everything ready for you…

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

0s

Practice › Arrays

Two Sum

Medium · Arrays · Asked at Amazon, Google, Microsoft, Adobe, Flipkart

Given an array of n integers and a target, find two different indices i < j such that a[i] + a[j] = target. Exactly one such pair exists.

Input

Output

Print i j (0-based, with i < j).

Constraints

Example 1

Input

4
2 7 11 15
9

Output

0 1

Example 2

Input

3
3 2 4
6

Output

1 2

Hints

  1. For each a[j], the partner it needs is target − a[j].
  2. Store each value's index in a hash map as you go; check the map before inserting a[j].

Approach

Walk j from left to right. Before storing a[j], look up target − a[j] in a hash map of value → index. If it's there, that index i is earlier than j, so print i j. Checking before inserting keeps an element from pairing with itself.

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

Solution

C++ solution

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    long long target;
    cin >> target;
    unordered_map<long long, int> seen;
    for (int j = 0; j < n; j++) {
        auto it = seen.find(target - a[j]);
        if (it != seen.end()) {
            cout << it->second << " " << j << "\n";
            return 0;
        }
        if (!seen.count(a[j])) seen[a[j]] = j;
    }
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
a = data[1 : n + 1]
target = data[n + 1]
seen = {}
for j, x in enumerate(a):
    if target - x in seen:
        print(seen[target - x], j)
        break
    seen.setdefault(x, j)

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[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        long target = sc.nextLong();
        Map<Long, Integer> seen = new HashMap<>();
        for (int j = 0; j < n; j++) {
            Integer i = seen.get(target - a[j]);
            if (i != null) {
                System.out.println(i + " " + j);
                return;
            }
            seen.putIfAbsent(a[j], j);
        }
    }
}

Solve Two Sum online · All practice problems