1. Two Sum

EasyArrayHash Table
Leetcode Link

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:

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

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.

💪
Level Up Your
Algo Skills

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.

Python Solution

1from typing import List  # Import List for type annotation
2
3class Solution:
4    def twoSum(self, nums: List[int], target: int) -> List[int]:
5        # Create a dictionary to store numbers and their indices
6        index_map = {}
7        # Enumerate through the list of numbers
8        for index, number in enumerate(nums):
9            # Calculate the complement of the current number
10            complement = target - number
11            # If complement is in the index_map, a solution is found
12            if complement in index_map:
13                # Return the indices of the two numbers
14                return [index_map[complement], index]
15            # Otherwise, add the current number and its index to the index_map
16            index_map[number] = index
17        # If no solution is found, this return will not be reached due to guaranteed solution.
18

Java Solution

1import java.util.Map;
2import java.util.HashMap;
3
4class Solution {
5    public int[] twoSum(int[] nums, int target) {
6        // Create a hashmap to store the value and its index
7        Map<Integer, Integer> indexMap = new HashMap<>();
8
9        // Iterate over the array elements
10        for (int i = 0; i < nums.length; i++) {
11            int current = nums[i]; // Current element value
12            int complement = target - current; // The complement which, when added to 'current', equals 'target'
13
14            // Check if the complement is already in the map
15            if (indexMap.containsKey(complement)) {
16                // If complement is found, return the indices of the two numbers
17                return new int[] {indexMap.get(complement), i};
18            }
19
20            // Store the current value and its index in the map
21            indexMap.put(current, i);
22        }
23        // Note: The problem statement guarantees that there will always be exactly one solution,
24        // so no need to return null or throw an exception here.
25        throw new IllegalArgumentException("No two sum solution found");
26    }
27}
28

C++ Solution

1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6    // Function to find the indices of the two numbers that add up to a specific target.
7    std::vector<int> twoSum(std::vector<int>& nums, int target) {
8        // Create a hash map to store the value and its index.
9        std::unordered_map<int, int> num_to_index;
10
11        // Iterate through each number in the vector.
12        for (int i = 0; i < nums.size(); ++i) {
13            int current_num = nums[i];      // Current number in the iteration.
14            int complement = target - current_num;  // Find the complement of the current number.
15
16            // If the complement is found in the map, return the pair of indices.
17            if (num_to_index.count(complement)) {
18                return {num_to_index[complement], i};
19            }
20
21            // If complement is not found, add the current number and its index to the map.
22            num_to_index[current_num] = i;
23        }
24
25        // In case no solution is found (this part is unreachable if input is guaranteed to have one solution as stated in the problem).
26        return {}; // Return an empty vector.
27    }
28};
29

Typescript Solution

1// Define the function signature with input types and return type
2function twoSum(nums: number[], target: number): number[] {
3    // Initialize a map to store the numbers and their indices
4    const numIndexMap = new Map<number, number>();
5
6    for (let i = 0; i < nums.length; i++) {
7        const currentNum = nums[i]; // The current number in the array
8        const complement = target - currentNum; // The number that complements the current number to reach the target
9
10        // Check if the complement is already in the map
11        if (numIndexMap.has(complement)) {
12            // If complement is found, return its index along with the current index
13            return [numIndexMap.get(complement)!, i];
14        }
15
16        // If complement is not found, add current number and its index to the map
17        numIndexMap.set(currentNum, i);
18    }
19
20    // Since the problem guarantees exactly one solution, the loop should never finish without returning.
21    // If no solution is found (which violates the problem's constraints), throw an error.
22    throw new Error('No two sum solution exists');
23}
24
25// The function `twoSum` can now be used as per its signature with TypeScript type checking.
26

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫