Neetcode 150 - Two Sum

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

        return []

Time Complexity: O(N^2).
Space Complexity: O(1)

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])


        # Sort it and binary search
        A.sort()

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

        return []

Time Complexity: O(NlogN).
Space Complexity: O(N).

3. Hash Map (Pre-computed index)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indicies = {} # 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).

4. Hash Map (Dynamic)

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).

Last Updated On October 22, 2025