Two Sum Problem

Problem 1 – Unsorted Array (0-indexed)

Problem:
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

Each input has exactly one solution.
You cannot use the same element twice.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Approach (Unsorted Array)

Use a hash map (dictionary) to store numbers and their indices.
Traverse the array.
For each number, check if target - num exists in the hash map.
If yes, return the indices [hashmap[target-num], current_index].
Else, store the current number in the hash map.

This gives O(n) time and O(n) space.

Python Code(Unsorted Array)

class Solution:
def twoSum(self, nums, target):
d = {}

    for i in range(len(nums)):
        diff = target - nums[i]

        if diff in d:
            return [d[diff], i]

        d[nums[i]] = i

Output
Output: [0, 1]

Problem 2 – Sorted Array (1-indexed, constant space)

Problem:
Given a sorted array numbers and a target, find two numbers that add up to target. Return 1-based indices.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Approach (Sorted Array)

Use two pointers, one at the start (left) and one at the end (right).
Calculate sum = numbers[left] + numbers[right].
If sum == target, return left+1, right+1.
If sum < target, move left pointer forward.
If sum > target, move right pointer backward.
This uses O(1) space and O(n) time.

Python Code (Sorted Array)

class Solution:
def twoSum(self, numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1
else:
right -= 1
numbers = [2,7,11,15]
target = 9
ret = Solution().twoSum(numbers, target)
print("Output:", ret)

Output
Output: [1, 2]