Two Sum LeetCode – Four Algorithms Implemented in R
In this post, we will be going over the two sum LeetCode question in R. We will be going to cover a total of 4 algorithms with different data structures. In the end, we will see which algorithm performs best with a ggplot2 visualization.
Algorithms & Data Structures we are using:
- Double for loop
- Base R built-in function
which() - Named Vector
- Hashmap
If you want to get familiar with the problem, then visit the LeetCode website.
Two Sum LeetCode in R – Double For Loop
two_sum_for <- function(nums, result) {
for(i in seq_along(nums)) {
for(j in seq_along(nums)[-length(nums)]) {
sum <- nums[i] + nums[j + 1]
if(sum == result) {
first <- i
second <- j + 1
indexes <- c(first, second)
return(indexes)
}
}
}
}
In the above solution, we are starting at the beginning of the vector and then see if any element that follows afterward adds up to the desired result. If not, we are going to the second element of the vector and see if any number that follows the second element adds up to the desired result. If the sum is equal to the result, we are going to return i and j, the indexes which numbers give the desired result.
Because the two sum question states that there will always be one solution, we could delete [-length(nums)] in the second for loop. This is just a precaution in case there is no solution and we exceed the length of the vector.
Two Sum LeetCode in R – Base R Built-In Function which()
two_sum_which <- function(nums, result) {
for(i in seq_along(nums)) {
comp <- result - nums[i]
if(comp %in% nums) {
first <- i
second <- which(nums %in% comp)
indexes <- c(first, second)
return(indexes)
}
}
}
The above code is different from the first algorithm. We are subtracting the number at index i from the vector from the result. This number added to the number at index i will equal to the result we are looking for. If this particular number (comp) is in the nums vector, then we know that these two numbers added are equal to the desired result. The which() function tells us, at what index the number, comb, is in the nums vector. Afterward, we return i as our first index and which(nums %in% comp) as the second index.
Consider the code below:
nums <- c(2, 11, 7, 15)
result <- 9
for(i in seq_along(nums)) {
comp <- result - nums[i]
if(comp %in% nums) {
first <- i
second <- which(nums %in% comp)
indexes <- c(first, second)
break
}
}
indexes
When i is equal to 1, nums[i] equals to 2, comp equals 9 – 2 = 7 and hence, comp %in% nums is TRUE. Hence, which(nums %in% comp)returns FALSE, FALSE, TRUE, FALSE and we know the number 7 occurs at index 3. So, we return index number 1 and index number 3.
Two Sum LeetCode in R – Named Vector
In the above code, we used a built-in function to get to the solution. We can get a bit more creative by using a named vector and storing the complements, result – nums[i], in a vector and using the indexes as names. The code would look like this:
two_sum_vec <- function(nums, result) {
vec <- c()
for(i in seq_along(nums)) {
vec[i] <- result - nums[i]
names(vec)[i] <- i
if(nums[i] %in% vec) {
first <- as.integer(names(vec[vec %in% nums[i]]))
second <- i
indexes <- c(first, second)
return(indexes)
}
}
}
In the code above we subtract nums[i] from the result and store that value in a vector, vec. Afterward, we give that entry in the vector a name. The name will be the index i. Then, we check if nums[i] has been saved in the vector before. If it has been saved before, we return the name of that vector entry and i.
This is basically the same algorithm as before, except that we use a named vector instead of the which() function. Here is a small example. Imagine i = 3.
# named vector for i = {1, 2, 3} looks like
# 1 2 3
# 7 -2 2
Now, nums[i] equals 7, and so as.integer(names(vec[vec %in% nums[i]])) gives us the name at index 1 of our named vector.
Two Sum LeetCode in R – Hashmap
two_sum_hash <- function(nums, result) {
vec <- c()
H <- hashmap::hashmap(1, 1)
for(i in seq_along(nums)) {
vec[i] <- result - nums[i]
H$insert(keys = i, values = vec[[i]])
if(nums[i] %in% H$values()) {
first <- H$data.frame()$Keys[H$data.frame()[, "Values"] == nums[i]]
second <- i
indexes <- c(first, second)
return(indexes)
}
}
}
The hashmap algorithm is the same as the named vector algorithm. When i equals 3, then:
H$data.frame() # Keys Values # 1 7 # 2 -2 # 3 2
Then, we want to find the key that belongs to nums[i] and we are done.
Two Sum LeetCode – Comparison of Algorithms
Now, we are going to compare the four different algorithms and see which one is fastest.
algo_timer <- function(fun, steps, iter) {
steps <- steps
timer <- vector(mode = "double", length = length(steps))
for(i in seq_along(steps)) {
mean_timer <- vector(mode = "list", length = iter)
for(j in 1:iter) {
set.seed(i + j)
vec <- 1:steps[i]
size <- steps[i]
vec <- as.integer(sample(vec, size))
index <- sample(1:size, size = 2)
result <- as.integer(vec[index[1]] + vec[index[2]])
system.time(
eval(rlang::parse_expr(fun))
) -> mean_timer[[j]]
}
purrr::map(mean_timer, 1) %>%
purrr::flatten_dbl() %>%
mean() -> timer[i]
}
return(timer)
}
We do that with the code above.
fun <- "two_sum_for(vec, result)" double_for <- algo_timer(fun, c(1000, 10000, 100000, 250000, 500000, 1000000), 500) fun <- "two_sum_which(vec, result)" which <- algo_timer(fun, c(1000, 10000, 100000, 250000, 500000, 1000000), 500) fun <- "two_sum_vec(vec, result)" named_vec <- algo_timer(fun, c(1000, 10000, 100000, 250000, 500000, 1000000), 500) fun <- "two_sum_hash(vec, result)" hash <- algo_timer(fun, c(1000, 10000, 100000, 250000, 500000, 1000000), 500)
I hope you have enjoyed this tutorial. If you have any questions or suggestions, let me know in the comments below.