Problem

Submissions

Hints & solutions

Discuss

2 Sum

Moderate

0/80

12 upvotes

Asked in companies

Problem statement

Given an integer array Arr of size N and an integer target, your task is to find the indices of two elements of the array such that their sum is equal to target. Return <-1,-1> if no such pair exists.

Note:

If more than one such pair of indices exist, return the lexicographically smallest pair
You may not use the same element twice.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array (Arr).

The second line contains 'N' single space-separated integers, representing the elements in the array.

The third line contains the value of the target.

Output format:

For each test case, print the indices of the elements from the array whose sum is equal to the target.

The output for each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
2 <= N <= 5 * 10^4 
-10^5 <= Arr[i] <= 10^5
2 * (-10^5) <= target <= 2 * 10^5

Where T is the number of test cases, N is the size of the input array, Arr[i] refers to the elements of the array and target is the given value of the sum.

Sample Input 1:

Sample Output 1:

0 1

Explanation of Sample Input 1:

Because Arr[0] + Arr[1] = 9.

Sample Input 2:

Sample Output 2:

-1 -1
0 1

Explanation of Sample Input 2:

In the first test case no pair of indices sums up to the target value 6.
In the second test case there are three pairs of indices which sums up to the given target value 6. So the pair which is lexicographically the smallest is {0,1}.

Hint 1

Hint 2

Hint 3

Explore all the combinations of two integers.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force approach

The idea is to explore all the possible pairs of indices of the array and check whether the sum of any of the pair elements sums up to the target value.

Algorithm :

Create two nested loops with counter i and j respectively.
First loop will run from 0 to N-1 and second loop will run from i+1 to N-1
Check if the sum of the elements present at the ith index and the jth index is equal to the target value or not.
Print the indices of the pair, if found, else return {-1,-1}.

Time Complexity

O(N^2), where ‘N’ is the number of elements in the array.

There are two nested loops traversing the array, so the time complexity is O(N * N) = O(N^2).

Space Complexity

O(1)

Constant extra space is required.

(100% EXP penalty)

2 Sum

Console