Jason Cameron

Search

SearchSearch

Two Sum

Jun 27, 20241 min readThe time complexity of the provided `twoSum` function is O(n), where n is the number of elements in the input list `nums`. This is because the function iterates through the list once, performing constant-time operations (dictionary lookups and insertions) for each element. The space complexity is also O(n) in the worst case, as the function uses a dictionary (`nmap`) to store the indices of the elements in `nums`. In the worst scenario, if no two numbers sum up to the target, the dictionary will end up containing all n elements, leading to linear space usage.

Approach

My idea was to simply check if the corresponding “missing” number has already been found and if so, return it’s index + current index. Technically it’s faster to check if it exists in nums instead of in nmap but I could not find a way to quickly deal with ignoring current index in .index.

Code

class Solution:
	def twoSum(self, nums: List[int], target: int) -> List[int]:
		nmap = {}
		for idx, i in enumerate(nums):
			missing = target - i
			if missing in nmap:
				return [idx, nmap[missing]]
			nmap[i] = idx
		return []

Graph View

Backlinks

  • No backlinks found