Breaking down the Two Sum problem on Leetcode

Posted on  • tagged with 

Given a list of integers and a target integer, find which pair of values in the list sum to equal the target value and then return the indices of the pair.

Problem Statement

The Two Sum problem description is below:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

First Approach (Brute Force)

Naturally, my first thought was to reach for loops and traverse the array of integers, more specifically the vector<int> data structure representing nums. Where I would use one outer for loop with a nested for loop. The outer loop would traverse nums at O(n) time and for each element A, we will begin traversing nums starting from the position of A and begin comparing the sum of each item B with A until we obtain a sum that equals target. This nested looping will create O(A * B) runtimes which gives us O(N^2).

O(N^2) runtime (96ms) with 10.1mb memory usage

class Solution {
public:
// O(N*N)=O(N^2) runtime
// An outer loop with nested loop, so we multiply the runtimes O(A * B)
vector<int> twoSum(vector<int>& nums, int target) {
int sum = 0;
int i = 0;
int j = 0;
// Using iterators to traverse `nums`
for (auto it = nums.begin(); it != nums.end(); ++it) {
// Do B for each time you do A
j = i + 1;
for (auto itr = nums.begin() + j; itr != nums.end(); ++itr) {
sum = *it + *itr;
if (sum == target) {
return {i, j};
}
j++;
}
i++;
};
return {0, 0};
}
};

One-pass hash table (Fastest Solution)

The algorithm can be improved to run at O(N) by performing a single pass of a hash table. That is, while iterating and inserting elements into the unordered_map<int, int>, we check if the current elements complement e.g. target - nums[i] already exists in the map. If it does exist, the solution has been found and we return the indices of the pair. The improvement from O(N^2) to O(N) is quite a big improvement, going from a 96ms runtime to 4ms runtime.

A screenshot of my best performing submission on LeetCode for the Two Sum problem

O(N) runtime (4ms) with 10.9mb memory usage

class Solution {
public:
// O(N) runtime - one-pass through an unordered map
vector<int> twoSum(vector<int>& nums, int target) {
// where Key = nums[i] (the value at each iteration)
// and Value = i (control variable, representing position of item in `nums`)
unordered_map<int, int> umap;

for (int i = 0; i < nums.size(); ++i) {
// search the map
auto it = umap.find(target - nums[i]);

// Ensure iterator is not pointing
// at the last element outside the container
if (it != umap.end()) {
// search was successful, return indicies
return vector<int> {i, it->second};
}
// populate the map, where the keys are each number
// in `nums` and value is the position
// e.g. control variable `i` as the value
umap[nums[i]] = i;
}
return {0, 0};
}
};