1. Two Sum

Given an array of integers nums and an integer target, your task is to return the indices of two numbers such that they add up to the target.

Problem Description:

  • You may assume that each input has exactly one solution.
  • You cannot use the same element twice.
  • The order of the indices in the result does not matter.

Function Signature:

def twoSum(nums: List[int], target: int) -> List[int]:
  • Input:
    • nums (List[int]): A list of integers, where 2 <= len(nums) <= 104 and -109 <= nums[i] <= 109.
    • target (int): The target sum you are trying to achieve, where -109 <= target <= 109.
  • Output:
    • A list of two integers that represent the indices of the numbers in nums that add up to the target.

Example 1:

Input:

nums = [2,7,11,15]
target = 9

Output:

[0, 1]

Explanation:

Because nums[0] + nums[1] == 9, the answer is [0, 1].

Example 2:

Input:

nums = [3,2,4]
target = 6

Output:

[1, 2]

Explanation:

Because nums[1] + nums[2] == 6, the answer is [1, 2].

Example 3:

Input:

nums = [3,3]
target = 6

Output:

[0, 1]

Explanation:

Because nums[0] + nums[1] == 6, the answer is [0, 1].

Constraints:

  • 2 <= len(nums) <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that runs in less than O(n^2) time complexity?

Problem Description

In this problem, we have an array of integers called nums and a target integer called target. Our task is to find two distinct numbers within the array that when added together, equal the target. One important rule is that we cannot use the same element from the array twice in our sum. The output will be the indices (positions in the array) of these two numbers, and it does not matter in which order we provide these indices. Each valid input to the problem is guaranteed to have exactly one solution.

Intuition

To solve this problem efficiently, we avoid the brute force approach of trying every possible pair of numbers to see if they add up to the target. Instead, we employ a hash table (dictionary in Python), which offers fast lookup times that average out to O(1) complexity. The basic idea is to iterate through the list once, and for each number, we check if the number required to reach the target (target - current_number) has already been seen in the array. If it has, then we have found the two numbers whose sum is equal to the target.

As we iterate through the nums array, we keep track of each number and its index in the hash table. So for each number x, we calculate y which is the difference between target and x. If y is found in the hash table, it means we have previously processed another number such that x + y = target. In that case, we immediately return the pair of indices: one for the current number x, and one for the previously stored number y. If y is not found in the hash table, we store x along with its index in the hash table and move on to the next element in the array. This approach only requires a single pass through the array, making the solution efficient and elegant.

Solution Approach

The solution provided uses a hash table to map each element’s value to its index in the array. This allows for constant-time look-ups which are critical for efficiency. The algorithm proceeds as follows:

  1. Initialize an empty hash table (dictionary in Python dialect), we’ll call it m.
  2. Iterate over the nums array, enumerating both the value x and its index i. Enumeration provides a convenient way of getting both the value and the index without additional overhead.
  3. For every value x, calculate its complement y by subtracting x from target (y = target - x).
  4. Check if y is present as a key in the hash table. If it is found, it means we had already seen the necessary pair earlier in the array. We then retrieve m[y], which is the index of y we had stored, and return a list containing the indices of y and x ([m[y], i]). This satisfies the requirement as their sum is equal to the target.
  5. If y is not in the hash table, add the current value x along with its index i to the hash table (m[x] = i). This stores x for future reference if we later come across its complement y.

By only traversing the array once, the overall time complexity is O(n), where n is the number of elements in nums. The space complexity is also O(n) as in the worst case, we could potentially store all elements in the hash table before finding a match.

Here’s the provided solution approach step in the code:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        m = {}  # Step 1: Initialize the hash table
        
        # Step 2: Enumerate through nums
        for i, x in enumerate(nums):
            y = target - x  # Step 3: Calculate complement y
            
            # Step 4: Check if y is present in the hash table
            if y in m:
                # Return the indices of the two elements adding up to target
                return [m[y], i]
            
            # Step 5: Store x with its index in the hash table for future reference
            m[x] = i

The strength of this approach is that it smartly utilizes the hash table to avoid nested loops and thus reducing the time complexity. The algorithm is linear time as it eliminates the need to examine every possible pair by keeping a record of what is needed to reach the target with the current number.

Example Walkthrough

Let’s work through a small example to illustrate the solution approach.

Suppose our input array nums is [2, 7, 11, 15] and the target is 9.

Following the solution steps:

  1. Initialize an empty hash table (dictionary), which we’ll name m.
  2. Now we start iterating over the nums array:
    • First iteration (i = 0):
      • We take the first element nums[0] which is 2.
      • Calculate its complement y = target - nums[0], which gives us y = 9 - 2 = 7.
      • Check if 7 is present in the hash table m. It isn’t, since m is empty.
      • Store the current value 2 along with its index 0 in the hash table: m[2] = 0.
    • Second iteration (i = 1):
      • Take the next element nums[1], which is 7.
      • Calculate its complement y = target - nums[1], which gives us y = 9 - 7 = 2.
      • Check if 2 is in the hash table m. Yes, it is! The complement 2 was stored during the first iteration.
      • Since the complement is found, we retrieve m[2] which is 0, the index of the complement 2. This gives us the indices [0, 1].

The sum of the numbers at these indices (nums[0] + nums[1]) equals the target (2 + 7 = 9). As expected, the original problem statement guarantees that there is exactly one solution, so the problem is now solved with the output [0, 1].

By using this hash table approach, we efficiently found the two numbers that add up to the target in a single pass through the array, thereby using O(n) time complexity instead of O(n^2) which would result from using a brute force approach with nested loops.

Solution Implementation

class Solution {
    public:
        // Function to find two indices whose values sum up to the target
        vector<int> twoSum(vector<int>& nums, int target) {
            // Loop through the array using the first index 'i'
            for (int i = 0; i < nums.size(); i++) {
                // Loop through the array using the second index 'j', starting from 'i + 1' to avoid repeating pairs
                for (int j = i + 1; j < nums.size(); j++) {
                    // Check if the sum of the two elements equals the target
                    if (nums[i] + nums[j] == target) {
                        // If the condition is true, return the indices as a vector
                        return {i, j};
                    }
                }
            }
            // Return an empty vector if no solution is found
            return {};
        }
    };
Copied!
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Create a map to store numbers and their indices
        Map<Integer, Integer> indexMap = new HashMap<>();

        // Enumerate through the list of numbers
        for (int i = 0; i < nums.length; i++) {
            // Calculate the complement of the current number
            int complement = target - nums[i];

            // If the complement is in the map, a solution is found
            if (indexMap.containsKey(complement)) {
                // Return the indices of the two numbers
                return new int[] { indexMap.get(complement), i };
            }

            // Otherwise, add the current number and its index to the map
            indexMap.put(nums[i], i);
        }

        // If no solution is found, return an empty array (although not needed as per the problem description)
        return new int[] {};  // This line is added to avoid the "missing return value" error
    }
}
Copied!
from typing import List  # Import List for type annotati
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Create a dictionary to store numbers and their indices
        index_map = {}

        # Enumerate through the list of numbers
        for index, number in enumerate(nums):
            # Calculate the complement of the current number
            complement = target - number

            # If the complement is in the index_map, a solution is found
            if complement in index_map:
                # Return the indices of the two numbers
                return [index_map[complement], index]

            # Otherwise, add the current number and its index to the index_map
            index_map[number] = index

        # If no solution is found, return an empty list (although problem guarantees one)
        return []  # This line ensures the function always returns something
Copied!
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    // Set the return size to 2 because the result will always have 2 indices
    *returnSize = 2;
    
    // Allocate memory for the result array to hold 2 integers (the indices)
    int* result = (int*)malloc(*returnSize * sizeof(int));
    
    // Loop through the array using the first pointer 'i'
    for(int i = 0; i < numsSize; i++) {
        // Loop through the array using the second pointer 'j', starting from 'i+1' to avoid repeating pairs
        for(int j = i + 1; j < numsSize; j++) {
            // Check if the sum of the two elements equals the target
            if(nums[i] + nums[j] == target) {
                // If the condition is true, store the indices in the result array
                result[0] = i;
                result[1] = j;
                // Return the result array with the indices
                return result;
            }
        }
    }
    
    // If no solution is found, set return size to 0 and return NULL
    *returnSize = 0;
    return NULL;
}
Copied!
public class Solution 
{
    // Method to find two indices whose values sum up to the target
    public int[] TwoSum(int[] nums, int target)
    {
        // Iterate through the array using the first index 'i'
        for (int i = 0; i < nums.Length; i++)
        {
            // Iterate through the array using the second index 'j', starting from 'i + 1' to avoid repeating pairs
            for (int j = i + 1; j < nums.Length; j++)
            {
                // Check if the sum of the two elements equals the target
                if (nums[i] + nums[j] == target)
                {
                    // If the condition is true, return the indices in an array
                    return new int[] { i, j };
                }
            }
        }
        
        // Return an empty array if no solution is found
        return new int[0];
    }
}
Copied!
function twoSum(nums, target) {
    // Loop through the array with the first index 'i'
    for (let i = 0; i < nums.length; i++) {
      // Loop through the array with the second index 'j', starting from 'i + 1' to avoid repeating pairs
      for (let j = i + 1; j < nums.length; j++) {
        // Check if the sum of the two elements equals the target
        if (nums[i] + nums[j] === target) {
          // If the condition is true, return the indices in an array
          return [i, j];
        }
      }
    }
  }
Copied!
function twoSum(nums: number[], target: number): number[] {
    // Loop through the array with the first index 'i'
    for(let i = 0; i < nums.length; i++) {
        // Loop through the array with the second index 'j', starting from 'i + 1' to avoid repeating pairs
        for(let j = i + 1; j < nums.length; j++) {
            // Check if the sum of the two elements equals the target
            if(nums[i] + nums[j] === target) {
                // If the condition is true, return the indices as an array
                return [i, j];
            }
        }
    }
    // Return an empty array if no solution is found
    return [];
}
Copied!
class Solution {

  function twoSum(array $nums, int $target): array {
    // Loop through the array using the first index '$i'
    for($i = 0; $i < count($nums); $i++) {
        // Loop through the array using the second index '$j', starting from '$i + 1' to avoid repeating pairs
        for($j = $i + 1; $j < count($nums); $j++) {
            // Check if the sum of the two elements equals the target
            if($nums[$i] + $nums[$j] == $target) {
                // If the condition is true, return the indices in an array
                return [$i, $j];
            }
        }
    }
    // Return an empty array if no solution is found
    return [];
  }
}
Copied!
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // Step 1: Initialize a dictionary for fast lookups.
    var dict: [Int: Int] = [:]
    
    // Step 2: Go through each number in the array.
    for (index, num) in nums.enumerated() {
        let complement = target - num
        
        // Step 3: If the complement is found in the dictionary, return its index along with the current number's index.
        if let complementIndex = dict[complement] {
            return [complementIndex, index]
        }
        
        // Step 4: Otherwise, store the current number and its index in the dictionary.
        dict[num] = index
    }
    
    // Step 5: If no matching pair is found, return an empty array.
    return []
    }
}
Copied!
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        // Step 1: Start the first loop to iterate over each number in the array.
        for (i in nums.indices) {
            // Step 2: Begin the second loop to go through the numbers following the current one.
            for (j in i + 1 until nums.size) {
                // Step 3: Check if the current pair of numbers add up to the target.
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        // Step 4: If no such pair is identified, return an empty array.
        return intArrayOf()
    }
}
Copied!
class Solution {
    // Function to find two indices whose values sum up to the target
    List twoSum(List<int> nums, int target) {
      // Loop through the array using the first index 'i'
      for (int i = 0; i < nums.length; i++) {
        // Loop through the array using the second index 'j', starting from 'i + 1' to avoid repeating pairs
        for (int j = i + 1; j < nums.length; j++) {
          // Check if the sum of the two elements equals the target
          if (nums[i] + nums[j] == target) {
            // If the condition is true, return the indices in a list
            return [i, j];
          }
        }
      }
      // Return an empty list if no solution is found
      return [];
    }
  }
Copied!
func twoSum(nums []int, target int) []int {
    // Step 1: Iterate over the numbers in the array.
    for i := 0; i < len(nums); i++ {
        // Step 2: For each number, iterate over the rest of the numbers.
        for j := i + 1; j < len(nums); j++ {
            // Step 3: Check if the current two numbers add up to the target.
            if nums[i]+nums[j] == target {
                return []int{i, j} // Return their indices.
            }
        }
    }
    // Step 4: If no pair is found, return nil.
    return nil
}
Copied!

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the array nums. This is because the code loops through each element in nums exactly once, and each operation within the loop—including checking if an element exists in the map m and adding an element to m—is O(1).

The space complexity of the code is also O(n), since in the worst case, the code may insert each element of the array nums into the map m. Therefore, the space used by the map m grows linearly with the number of elements in nums.

2 thoughts on “1. Two Sum”

  2. Hiya, I am really glad I have found this info. Today bloggers publish only about gossips and net and this is really frustrating. A good website with interesting content, that’s what I need. Thank you for keeping this web-site, I’ll be visiting it. Do you do newsletters? Cant find it.

Leave a Reply

Your email address will not be published. Required fields are marked *