# Ruby O(n) time and space - iterating smartly makes all the difference!

• Code is posted underneath.
In both cases, the hash contains key value pairs of (`target - n`, `i`), so when we iterate through the array again, we can check the hash for a hit and if we get a hit the value is the index of the other element which adds up to target when added to the current element.

In the method `with_hash`, we compute the complete hash first and then run through the array checking if we find a match.

In the method `with_hash_smarter`, we do a single iteration where we populate hash with entries corresponding to whatever we've seen so far and keep checking current element in it.

``````# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
# brute force is O(n^2)
# if we sort, we can do this in O(nlgn), but that's not gonna work because we need to return original indices
# we could do it in O(n) time with O(n) space

# with_hash(nums, target)
# with_sort(nums,target)
with_hash_smarter(nums, target)
end

# O(n) space and time - 97%ile
def with_hash_smarter(nums, target)
wanted = {} # set of numbers that we are looking out for
nums.each_with_index do |n, i|
j = wanted[n]
if !j.nil?
return [i,j].sort
end
wanted[target-n] = i
end
nil
end

# O(n) space and time - 19%ile
def with_hash(nums, target)
wanted = {}
nums.each_with_index do |a, i|
wanted[target-a] = i
end
nums.each_with_index do |b, j|
i = wanted[b]
# print "b: ", b,", i: ", i,", j: ", j, "\n"
if !i.nil? && i != j
if i > j
return [j, i]
else
return [i, j]
end
end
end
end
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.