0001.Two Sum

• Link: 1. Two Sum - Easy
• Track: NeetCode150

Question

Restate the problem

• Given an integer array nums and an integer target
• Find the indices of two nums, sum up equal to target
• Return the indices of the two numbers
• Notes:
  • Each input has exactly one solution
  • You may not use the same element twice

Edge Case

• Negative numbers - Exist
• Duplicate values - Yes

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Hashmap	O(n)	O(n)
Method 2	Sort + Two pointers	O($nlogn$)	O(n)

Method 1 - Hashmap

Approach

• Use a hashmap to store each number’s index
• For each num in indexi, compute target - num
  • If target - num is already in the map, immediately return [map[need], i]
  • Otherwise, store {num: index in the map and continue.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Code

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

Method 2 - Sort + Two pointer

Approach

• Create pairs (value, index) to keep original indices
• Sort by value
• Use two pointer (left, right) to find the target sum

Complexity

• Time Complexity: O($nlogn$)
• Space Complexity: O(n)

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        pairs = [(num, idx) for idx, num in enumerate(nums)]
        
        pairs.sort()
        
        left = 0
        right = len(pairs) - 1
        
        while left < right:
            total = pairs[left][0] + pairs[right][0]
            if total == target:
                return [pairs[left][1], pairs[right][1]]
            elif total < target:
                left += 1
            else:
                right -= 1

---

Mistake