Two Sum

Given an array of integers and a target, return the indices of two numbers that add up to the target.

Easy

Examples

Example 1: nums = [2,7,11,15], target = 9 → [0,1]
Solve on LeetCode

Implementation

Ruby 
  # 🧮 1. Two Sum
  # Given an array of integers and a target, return the indices of two numbers that add up to the target.
  # Uses a hash map to store complements for quick lookup.
  #
  # Time Complexity: O(n)
  # Why: One pass through nums with constant-time hash lookups.
  def two_sum(nums, target)
    hash = {}
    nums.each_with_index do |num, i|
      complement = target - num
      return [ hash[complement], i ] if hash.key?(complement)
      hash[num] = i
    end
    []  # no solution

Complexity Analysis

Time Complexity:
O(n)?
Why O(n)?
Single pass through the array
We visit each element exactly once in the loop. For each element, hash lookup and insertion are O(1) operations.
Example: Array of 1000 elements = ~1000 operations
Space Complexity:
O(n)?
Why O(n)?
Hash map stores up to n elements
In the worst case, we might store almost every element in the hash map before finding the solution.
Example: Array [1,2,3,4] with target 7 stores 3 elements in hash

Patterns & Techniques

Hash Map Array

Problem Details

Category: Array Hashing Examples
Difficulty: Easy
Module: ArrayHashingExamples
Method: two_sum

Related Problems

Contains Duplicate
Easy O(n)
Group Anagrams
Medium O(n * k log k)
Top K Frequent Elements
Medium O(n log n)
← Back to Array Hashing Examples
View All Categories