CODEWITHSUNDEEP
javafor-loop
S.P.
S.P.

Reputation: 369

Java - Leetcode Two Sum Hashmap Solution

I'm new to Java and I just started to do Leetcode - Two Sum. I found that except brute force solution, the common solution is using Hashmap. But I still cannot get it. For example, this works in my logic:

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
    int[] res = new int[2];
    for (int i = 0; i < nums.length; ++i) {
        m.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; ++i) {
        int t = target - nums[i];
        if (m.containsKey(t) && m.get(t) != i) {
            res[0] = i;
            res[1] = m.get(t);
            break;
        }
    }
    return res;
}

The first for loop put numbers to Hashmap, and use the second for loop to check if we can find the number that equals to target number - nums[i]. However, I saw a lot of accepted solutions combined the two for loops, such as this example:

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
    int[] res = new int[2];
    for (int i = 0; i < nums.length; ++i) {
        if (m.containsKey(target - nums[i])) {
            res[0] = i;
            res[1] = m.get(target - nums[i]);
            break;
        }
        m.put(nums[i], i);
    }
    return res;
}

In my logic, the second solution run the for loop like this:

//[2,7,11,15]
when i=0, m.put(nums[0],2)
when i=1, m.put(nums[1],7)
when i=2, m.put(nums[2],11)
when i=3, m.put(nums[3],15)

And because i < nums.length so when i=4, the code will jump to return res. It won't run the for loop again. But as far as I know, I saw people say that the second solution will iterate through the array, and store the index and value to Hashmap and then iterate again. In my imagination there's only one for loop, how can they use the only one for loop to iterate again?

Upvotes: 2

Views: 10937

Answers (4)

Alex Veleshko
Alex Veleshko

Reputation: 1242

The LeetCode solution is a variation of your HashMap solution.

Imagine that nums[j] + nums[k] = target for some indices j and k, j < k, and you don't break in your second for loop. Then the condition in that loop will trigger twice: for i = j and for i = k. Then imagine that you don't care about the first trigger and okay if the condition only triggers for i = k. This is what the LeetCode solution does. Since when i = j the nums[j] is not yet in the map, the condition won't trigger. It will only trigger when i = k, that is, when the first element of the pair is in the map.

For example, consider nums = [2,7,11,15] and target = 13.

Here is the breakdown how your solution without break would work.

i nums[i] target - nums[i] in the map?
0 2 11 ✓
1 7 5
2 11 2 ✓
3 15 −2

(The last column is marked when the value of target - nums[i] is in the map during the check.)

Compare this with the rundown for the LeetCode solution with removed break:

i nums[i] target - nums[i] map keys in the map?
0 2 11 []
1 7 5 [2]
2 11 2 [2, 7] ✓
3 15 −2 [2, 7, 11]

The LeetCode solution cuts on the number of insertions into the map when the solution is found early. In the worst case, when there are no such j and k, both solutions make the same number of insertions and contains queries.

Upvotes: 0

Kartik Sharma
Kartik Sharma

Reputation: 1

I think this is the best way to solve this question

class Solution {

public int[] twoSum(int[] nums, int target) {
    int[]  result = new int[2];
    for (int i=0; i<nums.length; i++){
        for (int j=i+1; j<nums.length; j++){
            if (nums[i] + nums[j] == target){
                result[0]=i;
                result[1]=j;
                return result;
            }
        }
    }
    return result;
}

}

Upvotes: 0

Raghavendra Prasad
Raghavendra Prasad

Reputation: 36

There is no need for two for loops and this can be done in the single for loop as posted by you.From a perfomance point of view its better to iterate only once in the for loop and break from the loop when the first matching pair is found. This is O(n) in the worst case.

    public static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        int rem = target - num;
        if (map.containsKey(rem)) {
            return new int[] { num, rem };
        }
        map.put(num, num);
    } // for
    return null;
}

Upvotes: 1

AppleCiderGuy
AppleCiderGuy

Reputation: 1297

there wont be any 2nd iteration. In one iteration itself the loop would break if a pair is found.

consider this:

//[2,7,11,15] and target = 13
when i=0, m.put(mums[0],2)
when i=1, m.put(mums[1],7)
when i=2, m.contains(13 - mums[2]) == true // since 13 - 11 = 2 is present at index 0
res[0] = 2
res[1] = 0
break;

and Hence, ..... you are right. there is only one iteration.

Upvotes: 2

Related Questions