1. Two Sum

Reformulated question¶

Return the indices of two distinct elements in nums whose sum is target.

Example:

nums=[3,2,4], target=6 -> [1,2]   # nums[1] + nums[2] = 6

Key trick¶

Use a hash map from value to index while scanning once.

For each x at index i, look for target - x in the map.
If found, return the stored index and i.
Otherwise store x -> i.

Trap¶

Common mistakes:

Using the same element twice.
Storing before checking, which breaks cases like nums=[3,3], target=6.
Returning values instead of indices.
Writing the \(O(n^2)\) double loop and missing the follow-up.

Why is this question interesting?¶

It tests the classic move from brute force to hashing.

Naive: check all pairs.
Better: trade memory for time and get \(O(n)\).

Solve the problem with idiomatic python¶

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen = {}  # value -> index

        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [seen[need], i]
            seen[x] = i

        # Problem guarantees exactly one solution.
        raise ValueError("No solution")

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("nums", "target", "expected"),
    [
        ([2, 7, 11, 15], 9, [0, 1]),
        ([3, 2, 4], 6, [1, 2]),
        ([3, 3], 6, [0, 1]),
        ([-1, -2, -3, -4, -5], -8, [2, 4]),
        ([0, 4, 3, 0], 0, [0, 3]),
        ([1, 5, 1, 5], 10, [1, 3]),
    ],
)
def test_two_sum(nums, target, expected):
    assert Solution().twoSum(nums, target) == expected

Comment my solution¶

Your solution is correct, but it is quadratic.

Time complexity is \(O(n^2)\).
The expected interview improvement is the hash map solution with \(O(n)\) time and \(O(n)\) space.

Small notes:

Your test should prefer cases with a unique valid answer.
Comparing with sorted(...) is fine if order does not matter.
The case [1, 3, 4, 5, 8, 8, 5], 10 is not ideal because it has multiple valid answers.

import pytest

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

@pytest.mark.parametrize(
    ("nums", "target", "output"),
    [
        ([2,7,11,15], 9, [0,1]),
        ([3,2,4], 6, [1,2]),
        ([3,3], 6, [0, 1]),
        ([1, 3, 4, 5, 8, 8, 5], 10, [3, 6])
    ]
)
def test_twoSum(nums, target, output):
    assert sorted(Solution().twoSum(nums, target)) == sorted(output)