Problem Statement

Given an array of integers, find two distinct indices such that the corresponding elements sum to a specified target value. Each input is guaranteed to have exactly one solution, and elements cannot be reused.

Example: For input array [2, 7, 11, 15] and target 9, return [0, 1] since 2 + 7 = 9.

Solution Approach

A brute-force solution with nested loops would yield O(n²) time complexity. To optimize, we use a dictionary to store required complements and their indices. This approach achieves O(n) time complexity and O(n) space complexity.

Algorithm walkthrough for the example:

nums = [2, 7, 11, 15]
target = 9
complements = {}

Index 0: Current value 2
  - Check if 2 exists in complements (no)
  - Store complement (9-2=7) with index 0
complements = {7: 0}

Index 1: Current value 7
  - 7 exists in complements
  - Return [complements[7], 1] → [0, 1]

Implementation

class Solution:
    def two_sum(self, numbers, goal):
        complements = {}
        for idx, num in enumerate(numbers):
            if num in complements:
                return [complements[num], idx]
            complements[goal - num] = idx

Performance

This implementation executes in O(n) time and O(n) space, making it optimal for large input sizes.