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

Posted by N.K. Chauhan on Mar 31, 2024

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


Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Program to right rotate an array by 'k' elements

Minimize the difference between the heights of smallest and highest tower

Find maximum and minimum element of an array

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Find duplicates in O(n) time and O(n) extra space.

Move all negative numbers to beginning of the array

Maximum Product Subarray (Modified Kadane's Algorithm)

Find largest sum contiguous sub-array (Kadane's Algorithm)

Find duplicates in O(n) time and O(1) extra space

Alternating +ve & -ve in array in O(1) time (maintaining order)