Problem 01 - Two Sum

Problem

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Examples

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

Example 2:
  Input:  nums = [3,2,4], target = 6
  Output: [1, 2]

Example 3:
  Input:  nums = [3,3], target = 6
  Output: [0, 1]

Constraints

• 2 ≤ nums.length ≤ 10⁴

• –10⁹ ≤ nums[i], target ≤ 10⁹

• Exactly one valid pair exists.

• You can’t use the same element twice.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Start Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

Answer

Brute-Force (O(n²))

That's easy, right? just check every possible pair:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n - 1): # Because indices starts from 0
            for j in range(i + 1, n): # Check the sum of index i and every number after it.
                if nums[i] + nums[j] == target:
                    return [i, j]

• Why it works: We compare each element nums[i] with every other nums[j]} that comes after it.

• The downside: Two nested loops → O(n²) time, which can be slow on large inputs.

One-Pass Hash Map (O(n))

We can do better by trading space for time. As we scan the list, we store each value’s index in a hash map and look up its needed complement on the fly:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}  # value → index
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i

• Key idea: For each num, ask “Have I already seen target – num?”

• Why it’s fast: One pass through the array, constant-time hash lookups → O(n) time and O(n) space (memory).

Lessons Learned

• Hash maps to the rescue: They turn nested-loop searches into single-pass lookups.

• Space–time trade‐off: Using extra memory (the map) can dramatically reduce runtime.