Domain 1EasyCORE

Two Sum

The problem asks us to find two indices in an array such that the elements at those indices add up to a given target value. The inputs are: - An array of integers `nums`. - An integer `target`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table

1. Two Sum

Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 46.7%


Problem Breakdown

The problem asks us to find two indices in an array such that the elements at those indices add up to a given target value. The inputs are:

  • An array of integers nums.
  • An integer target.

The output should be:

  • A list containing the two indices.

Constraints:

  • Each input will have exactly one solution.
  • The same element cannot be used twice.

Edge cases to consider:

  • Duplicates in the array.
  • Negative numbers in the array.
  • Overflow conditions (though unlikely given the constraints).

Intuition

The brute-force approach would involve checking every possible pair of elements in the array to see if their sum equals the target. This approach has a time complexity of O(n^2) because we need to check n*(n-1)/2 pairs, where n is the length of the array.

A better approach involves using a hash table (dictionary in Python) to store each number and its index as we iterate through the array. For each number, we can calculate the complement (target - number) and check if it exists in the hash table. If it does, we have found our solution. This approach reduces the time complexity to O(n) because we only need to make a single pass through the array.

Approach

  1. Initialize an empty dictionary num_to_index to store numbers and their indices.
  2. Iterate through the array using a for loop with index i and value num.
  3. For each number, calculate its complement as complement = target - num.
  4. Check if the complement exists in the dictionary:
    • If it does, return the current index i and the index of the complement from the dictionary.
    • If it doesn’t, add the current number and its index to the dictionary.
  5. If no solution is found (though the problem guarantees one), return an empty list.

Complexity Analysis

  • Time Complexity: O(n) because we iterate through the array once.
  • Space Complexity: O(n) in the worst case where all elements are stored in the dictionary.

Solution

def twoSum(nums, target):
    num_to_index = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i

Edge Cases Handled

  • Duplicates: The code correctly handles duplicates by storing the first occurrence of each number. If a duplicate is needed to form the target sum, it will be found in subsequent iterations.
  • Negative Numbers: The code works with negative numbers as well since subtraction and dictionary lookups are valid operations for them.
  • Single Solution Guarantee: The problem guarantees that there is exactly one solution, so the code does not need to handle cases where no solution exists.