2025-08-27

1. Two Sum

Given an array of integers and a target number return two indices who would add up to that number. Assume that there is only one solution

First solution

Create a key:value pair of value:indices Because some elements may repeat

Then iterate through the list and check if target-element exists

This seems harder than I thought for the example of [3,3], the map would be 3 => [0, 1] I would have to check if the element is itself.

This take O(n) time and O(n) space

dict_ = {}
for n, elem in enumerate(nums):
	dict_.setdefault(elem, []).append(n)
	if (target - elem) in dict_:
		for other_elem_ind in dict_[target - elem]:
			if other_elem_ind != n:
				return (
					(n, other_elem_ind)
					if (n < other_elem_ind)
					else (other_elem_ind, n)
				)
			else:
				pass

Better solution

What is wrong with the above solution?

• Sucks on the LC time and space complexity graphs

target = foo + bar
foo_ind and bar_ind are unique for each list

I essence we just have to check if target-bar exists if we are iterating through with foo But problem is that if foo and bar have the same value, then we cannot just hash them directly. We would have to store a list. That may slow this down

So solution don’t require that we store these things in a list. They just overwrite it. This will work as the solution is unique. Suppose we saw 3 at index 0. Then we encounter 3 at index 5. We will check if target-3 exists in the map and return that index with the current. So we don’t have to worry about storing them in a list.

that’s what made the above solution slow.