1. Understand the problem

• We’re given an array of integers nums and an integer target. We need to find two indices i and j such that nums[i] + nums[j] == target.

• Return their indices (order doesn’t matter).

2. Ask clarify questions

• Are there exactly one solution, or can there be multiple?

• Can the same element be used twice? (usually no)

• Should we return indices or the numbers themselves?

• What if no solution exists?

• What’s the expected time complexity — O(n²) acceptable or aim for O(n)?

3. Work through examples

Example 1:

• nums = [2,7,11,15], target = 9 → indices [0,1] (2+7=9)

Example 2:

• nums = [3,2,4], target = 6 → indices [1,2] (2+4=6)

Example 3:

• nums = [3,3], target = 6 → indices [0,1]

4. Brainstorm 2–3 solutions

1. Naive (O(n²)):

• Check all pairs (i, j) → return when sum == target.

1. Optimized (O(n)):

• Use a hash map (dictionary) to store {value: index}.

• For each number, check if target - num already exists in map.

5. Implement solution

5.1. Brute Force

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[i] + nums[j] == target:
                    return [i, j]
        return []

• Time Complexity: O(N^2).

• Space Complexity: O(1).

5.2. Sorting

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        A = []
        for i, num in enumerate(nums):
            A.append([num, i])

        A.sort()
        i, j = 0, len(nums) - 1
        while i < j:
            cur = A[i][0] + A[j][0]
            if cur == target:
                return [min(A[i][1], A[j][1]),
                        max(A[i][1], A[j][1])]
            elif cur < target:
                i += 1
            else:
                j -= 1
        return []

• Time Complexity: O(NlogN).

• Space Complexity: O(N).

5.3. Hash Map (Two Pass)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = {}  # val -> index

        for i, n in enumerate(nums):
            indices[n] = i

        for i, n in enumerate(nums):
            diff = target - n
            if diff in indices and indices[diff] != i:
                return [i, indices[diff]]

• Time Complexity: O(N).

• Space Complexity: O(N).

5.4. Hash Map (One Pass)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i

• Time Complexity: O(N).

• Space Complexity: O(N).

6. Test your code

Example: nums = [2,7,11,15], target = 9

Step	num	complement	seen	result
0	2	7	{2:0}	—
1	7	2	found 2 → return [0,1]	✅

• Time Complexity: O(N).

• Space Complexity: O(N).