Jason Cameron

Search

SearchSearch

Two Sum

Jun 27, 20241 min readThe time complexity of the given `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, where no two numbers sum up to the target, the dictionary could end up storing all n elements. In summary, the time complexity is O(n) and the space complexity is O(n).

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