1. Two Sum

Step by Step Algorithm

1. Initializing a Dictionary:
   • We initialize an empty dictionary called paid_index. This dictionary will be used to store the indices of numbers encountered during the iteration.

pair_index = {}

2. Iterating Through the List:
   • We use the ‘enumerate()’ function to iterate through the nums list along with their indices.
   • At each iteration, i represents the index of the current number, and ‘num’ represents the actual value.

for i, num in enumerate(nums):

3. Checking for Complementary Pair:
   • We check if the difference target - num exists as a key in the paid_index dictionary.
   • If it exists, it means that we have found a pair of numbers whose sum equals the target.

if target - num in paid_index:

4. Returning the Result:
   • If we find the complementary pair, we return a list containing the indices of the current number i and the index of the complementary number stored in the pair_index dictionary.

return [i, pair_index[target - num]]

5. Storing
   • If the complementary pair is not found, we store the current number num along with its index i in the pair_index dictionary.
   • This allows us to later look up whether the complementary number exists in the list.

pair_index[num] = i

Summary

This algorithm efficiently finds a pair of numbers in the nums list whose sum equals the target value. It does so by using a dictionary to store the indices of numbers encountered so far and checking for the existence of complementary numbers during the iteration.

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

Complexity

• Time complexity: O(n)
  n is number of elements in input array.

• Space complexity: O(n)
  n is number of elements in input array. In the worst case, we put all numbers in pair_idx.

Alternatives

class Solution:
	def twoSum(self, nums: List[int], target: int) -> List[int]:
		for i in range(len(nums)):
			for j in range(i + 1, len(nums)):
				if nums[j] == target - nums[i]:
					return [i, j]
					
		return []