Two Sum LeetCode Ruby Solution cheat sheet

Two Sum is in the easy category and a really popular algorithm. There is a lot of literature in other languages about it, this will be a quick and simple solution using Ruby.

The challenge

“Given an array of integer 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.”

NOTE

1. array of integer

2. addition of two different elements equal target

3. return index array

4. One solution.

Input: nums = [3,2,4], target = 7              0  1  2Return: [0,2]

Brut force solution O(n²).

Use two pointers i and j in nested loops and return the index if the addition of nums[i] + nums[j] equal the targetnums = [3,2,4], target = 7        | |        i j

Code 1

def two_sum(nums, target)nums.each_with_index do |value, i|((i+1)…nums.length).each do |j|return [i,j] if value+nums[j] == targetendendend

Optimized solution using hash O(n)

We start with an empty hash “compared” that we populate with key-value pairs

key = reminder

value = index of num

if already present in the compared hash return the solution

examplenums = [3,2,4], target = 7compared = { }is 3 in compared ? no7–3 =4compared { 4:0 }is 2 in compared ? no7–2 = 5compared { 4:0, 5:1}is 4 in compared ? yes7–4 = 3 we already have 4 in the compared hash { 4:0, 5:1, 3:2 } so wereturn solution [0,2]

code 2

def two_sum(nums, target)compared = {}nums.each_with_index do |num, i|reminder = target — numreturn [compared[reminder], i] if compared[reminder]compared[num] = iendend