Arrays - Two Sum

Given an array of integers nums and a target k, find a pair of numbers from an array whose sum is equal to k and return their indices as output.

Example 1

Input: nums = [3, 2, 4] and K = 6 Output: [1, 2] Explanation: after adding up values at index 1 and 2 , that adds up to the target 6.

Example 2

Input: nums = [3, 3] and K = 6 Output: [0,1] Explanation: after adding up values at index 0 and 1 , that adds up to the target 6.

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

Solution 1 - Using HashMap

Using HashMap

The main intution behind this solution is, as per the problem statement x + y = k, given the value k, we have to find (x, y) pair. If we know one number x, then all we have to do is find the other number, which is k-x. So, in this approach we will loop through all elements of input array nums, and for every number at i^th index x = nums[i], we will find if the other number for the pair k-x is visited or not using a HashMap.

Implementation steps:

We will first create a HashMap, to store elements of input array nums and their indexes, call it map.
Then, loop through every element of nums, and check if map contains K- nums[i] or not, if it contains, that means we have found the pair, so return their indexes as an array. If we dont find it, then add current element and it's index to the map.

public int[] twoSum(int[] array, int target) { // base case to find a pair we need atleast two elements. if(array == null || array.length < 2) { throw new IllegalArgumentException("input array should contain atleast two elements"); } Map<Integer, Integer> map = new HashMap<>(); for(int i=0; i<array.length; i++) { int current = array[i]; int diff = target - current; Integer pairIndex = map.get(diff); if(pairIndex != null) { // we found other number index which adds up to target k return new int[] {pairIndex, i}; } else { map.put(current, i); // store the number and its index } } return null; // none found }

Complexity Analysis:

Above code runs in O(n) time complexity where n is the size of the array, as we are looping through the array.
Space complexity is O(n) as we are storing elements into HashMap.

illustration:

Consider below example

Input Array : [2, 7, 11, 15] and Target = 18.

Step 1 We initialize an intermediate data structure HashMap to store element and it's index.

Step 2 Loop through elements and find if the other pair element visited or not.

In 1^st iteration, take the diff between target and first element 18 - 2 = 16 , is 16 already present in HashMap ? HashMap is empty, so store current number 2 and its index 0 into map and continue with next element.

Number	Index
2	0

In 2^nd iteration, take the diff between target and second element 18 - 7 = 11 , is 11 already present in HashMap ? No, so store current number 7 and its index 1 into map and continue with next element.

Number	Index
2	0
7	1

In 3^rd iteration, take the diff between target and third element 18 - 11 = 7 , is 7 already present in HashMap ? Yes, we found our answer. We now have have the indices of current element and element 7 from map {1, 2}.