Photo Credit: Unsplash (Fotis Fotopoulos)

Problem 1: TwoSum

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return [0, 3] since 10 + 7 is 17. Otherwise, return [-1, -1].

Bonus: Can you do this in one pass?

Similar Leetcode problem: https://leetcode.com/problems/two-sum/

Approach 1: Brute Force Method

Let’s try this to approach the problem gradually, and try this with a 2-pass approach.

(Programming Language Used: Python)

def twoSum(nums, target):    res = []
for i in range(len(nums)):
for j in range(1, len(nums)-1):
if nums[i] + nums[j] == target and i != j:
res.append(i)
res.append(j)
return res
return [-1, -1]
# Testing
s = [10, 15, 3, 7]
k = 17
print(twoSum(s, k))
# Output: [0, 3]

Visual Execution:

Check http://pythontutor.com/ for your code-visualization (in steps)

Complexity Analysis:

  • Time Complexity: O(n²) [for 2 for-loops]
  • Space Complexity: O(1) [since the res always holds 2 values]

where, n = length of the elements in nums.

Approach 2: Hash Map / Dictionaries

(This is, of-course, a better solution that the previous one.)

def twoSum(nums, target):
dictionary = {}
for i in range(len(nums)):
if nums[i] not in dictionary:
dictionary[target - nums[i]] = i
else:
return [dictionary[nums[i]], i]
return [-1, -1]
# Testing:
nums = [7, 2, 15, 11]
target = 17
print(twoSum(nums, target))
# Output
[1,2]

Visual Execution:

Complexity Analysis:

  • Time Complexity: O(n) [for 1 for-loop]
  • Space Complexity: O(n) [since the dictionary holds the values from nums till it gets the desired output]

where, n = length of the elements in nums.

Big Data Engineer / Data Modeler @ APS | M.S. in Information Sciences with Big Data Analytics major from University of Pittsburgh.