Two Sum

• This can be done intwo_pass andsingle_pass, pass means number of loops.

Intuition

• temp variable is required_sum - current_element
• if temp exists in hashmap then return true
• if not put current_element as key of hashmap and value as index
• giving value as index will help us twice which index elements are creating the sum
• what is the element has not been inserted in the hashmap and we try to substance that from sum and try to find it? Since the element are getting inserted at the end of the loop.
• No it won’t happen like that, two elements are required to create sum, till the first element is present in array you can’t check for second one.
• 3 sum triplet time complexity was n log n, was there a solution without Sorting that would have given similar or better output? Leetcode code:

Code

Tc: O(n)

# Python program to find if there are
# two elements with given sum
 
# function to check for the given sum
# in the array
 
 
def printPairs(arr, arr_size, sum):
 
    # Create an empty hash map
    # using an hashmap allows us to store the indices
    hashmap = {}
 
    for i in range(0, arr_size):
        temp = sum-arr[i]
        if (temp in hashmap):
            print('Yes')
            return
        hashmap[arr[i]] = i
    print("No")
 
 
# driver code
A = [1, 4, 45, 6, 10, 8]
n = 16
printPairs(A, len(A), n)
 
# This code will also work in case the array has the same number twice
# and target is the sum of those numbers
# Eg: Array = [4,6,4] Target = 8

Leetcode submission

51/60 test cases pass, the test cases where same number come is failing,

• python_trick to iterate through dictionary, use myDict.items() in for loop, you will get key, value

Attempt