Two Sum - return index of a pair of array elements with a given sum

Posted by N.K. Chauhan on Feb 04, 2023

Given an array of integers input[] and an integer target, the task is to return the index of two numbers such that they sum up to target.

Input: nums = [1, 4, 45, 6, 10, 8], target = 16
Output: [3,4]

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,4], target = 6
Output: [-1,-1]


Solutions

Method 1: In O(n) time and O(n) space

We can solve this problem in O(n) time and O(n) space.

The goal is to keep a hash map with the key representing target-a[i] and the value representing the index.

Iterate through the array from left to right; if target-currentElement is already in the map, return [map.get(target-currentElement), i]; otherwise, add the current element value and index to the map.

Complexity

The time complexity of this solution is O(n) and space complexity is O(n).

Method 2: In O (n log n) time and O(1) space

We can solve this problem in O(n log n) time and O(1) space.

The idea is to first sort the array and then use two pointers at both ends of the array. i.e. i=0, j= a.length-1.

If i+j < target, do i++, else if i+j > target, do j--, else return return [i, j].

Complexity

The time complexity of this solution is O(n log n) and space complexity is O(1).

Method 3: In O(n*n) time and O(1) space

We can solve this problem in O(n2) time using two nested loops.

The idea is to check for every pair until the target is met; if no pair sums up to the target, return [-1, -1].

Complexity

The time complexity of this solution is O(n*n) and space complexity is O(1).

Related


Find a triplet in an array that sums to a given number

Program to print Union of two sorted arrays

Rain water trapping problem - O(n) time & O(n) space

Merge two sorted arrays in O(1) space

Print all possible permutations of an Array in O(1) space

Print all Subsets (Power Set) of a given array

Word Break Problem (Using HashMap and DP)

Count the number of inversions in an array - in O(n log n) time

Program to print Intersection of two sorted arrays

Longest substring without repeating characters