Posts Two Sum
Post
Cancel

Two Sum

This question is part of NeetCode150 series.

Problem Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
leetcode

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    
    public int[] twoSum(int[] nums, int target) {
        
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<nums.length; i++){
            int diff = target - nums[i];
            if(map.containsKey(diff)){
                return new int[]{map.get(diff), i};
            }else{
                map.put(nums[i], i);
            }
        }
        
        return new int[]{};
        
    }
}

Modified Version of the Problem (Interviewbit)

2 Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class Solution {

    public int[] twoSum(final int[] A, int B) {

        int n = A.length;

        Map<Integer, Integer> map = new HashMap<>();

        //init with max because we need the least index
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;

        for(int i=0; i<n; i++){

            int current = A[i];

            //current + secondNumber = B
            //=> secondNumber = B - current
            if(map.containsKey(B-current)){
                
                int x = map.get(B-current);
                int y = i;

                //as per the questions, choose the one with min index for second number
                if(y < b){

                    a = x;
                    b = y;

                //if index of second number is equal, then choose the one with least index for the first number
                }else if(y == b){

                    if(x < a){
                        a = x;
                        b = y;
                    }
                }

            //if current number does not exist in the hash map, only then add it so that we don't update it to the higher index element
            }else{

                if(!map.containsKey(current)) //this is important because we need to min index for any element
                    map.put(current, i);

            }

        }

        if(a != Integer.MAX_VALUE){
            return new int[]{a+1, b+1};
        }

        return new int[]{};

    }
}
This post is licensed under CC BY 4.0 by the author.