Blog

Two Sum (Solution for Leetcode Problem # 1)

  • Post last modified:July 16, 2022
  • Reading time:3 mins read

Understanding Problem

Integer[] numbers = {1,2,3,4};
int target = 5
  • our goal is to find the indices of two integers from the given array that adds up to the target,
    so in our example, we have number 2 and 3 that adds up to 5, so our output should result in an array with indices [1,2]
  • One important point to note is that there would be exactly one solution exist. So there won’t is more than one solution.
    Additionally, we cannot use the same number twice, meaning if we have target 6, then we cannot add the number 3 twice. The order of the indices is not important.

First Thought About Solution

  • What first thought comes to my mind is that if I can somehow have a list of numbers that tells me the addition of two numbers for example,
Integer[] numbers = {1,2,3,4};
Integer[] combination = {3,4,5,5,6,7}; 
// creating combination      1+2=3, 1+3=4, etc..
  • If I do so, I need to run two for loop over input array integer and create a combination ArrayList. then run one additional for loop to check if the target is present in the list. But if I follow this approach I quickly realize that I will lose index information after performing combination.
  • We can also run two for loop and check the addition result for each combination & if it matches with the target then store the indices of two numbers in the result and return it. this solves our problem. Time complexity would be O(N²) and Space complexity O(N).
  • But can we do better? Let’s think a little bit differently. Each target is the addition of two numbers that x+y=target, so if we need to find x, then x=target-y; so for each input number y, if we can find x=target-y in our input numbers then our job is done.
  • Since map allows us to store index and value hence we can store indices for each element in the map as well.
  • Since we have a Map data structure we can look up a particular key or value on O(1) time without looping through n number of elements. That’s the advantage we get for time complexity, but keep in mind we added space complexity of O(N).

Data structure: HashMap
Time-complexity:O(1)
Space-complexity: O(N) // N is the length of numbers array

Pseudocode

if input_x + input_y = target, 
then input_x = target-input_y;1: So lets travers each element in input array numbers, 2: find the difference between input number and target in Map    input_x = target-input_y;3: If difference exist , then store the index of input array element(input_y) and index of the difference element from map(input_x) into the result array 
result=[index(input_x),index(input_y)] // we dont care order of indices as per the problem statement4: return the result array

Solution

Results

Our solution is accepted by Leetcode ( beating 67.38% of Java Solution )

Conclusion

This Leetcode problem is a good to use case to use HashMap data structure.
I would typically think of using hashmap when I need to improve my runtime performance since it takes care of searching elements in O(1) time.

Let me know if you can find some improvement points in the code which can further increase the efficiency.

Happy LeetCoding!

Tags: , , ,

Leave a Reply