[LeetCode] 1. Two Sum

1. Description

Given an array of integers nums and an integer target, return indices of 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.

 

constraints :

• 2 <= nums.length <= \(10^4\)
• \(-10^9\) <= nums[i] <= \(10^9\)
• \(-10^9\) <= target <= \(10^9\)
• Only one valid answer exists.

 

2. Algorithms

If i use brute froce algorithm for searching indices of two numbers such that they add up to target, then the time complexity of this algorithm will be \(O(N^2)\).

 

Because the recommmended algorithm of solving this problem is less than \(O(N^2)\) time complexity, we need to use more optimized data structures.

 

Let's consider when we use dictionary datastructure to solve this problem. To check the leftover between target and nums

is in nums, we need to store the element of nums as key. So our dictionary will store key : value pairs as num : index.

 

By storing key and value in dictionary at last, we can compare the leftover from current value with dictionary immediately.

 

nums = [2, 7, 11, 15], target = 9

hash_table = {2 : 0, 7 : 1, 11 : 2, 15 : 3}

iteration 1 : left_over = 7 is not in hash_table 
iteration 2 : left_over = 2 is in hash_table -> return result

 

And using this operation, we can escape exception that finds the same index if there are only same value in nums.

 

1. Start
2. Declare variable named hash_table
3. Initialize hash_table to empty dictionary
4. Repeat the steps through indexes and elements of nums 
   1. Calculate leftover between target and num
   2. If leftover is in hash_table,
      1. Return its index and value of leftover stored in hash_table 
   3.  Update dictionary with num : i
5.  End

 

3. Codes

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = {} 

        # Store key : value -> num : target - num 
        for i, num in enumerate(nums): 
            left_over = target - nums[i] 
            if left_over in hash_table: 
                return (i, hash_table[left_over])
            
            hash_table[num] = i

 

4. Conclusion

 

Time Complexity : \(O(N^2)\)

Space Complexity : \(O(N)\)