In order to prepare myself in a better way, I've started doing problems on Leetcode. Here's starting with first one -
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
For e.g.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Like every other problem, this could be solved by multiple approaches. My approach is using one hash table. This way when we iterate and insert elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.
# Time complexity: O(n)
# Space complexity: O(n)
def two_sum(nums, target)
nums_hash = {}
nums.each_with_index do |i, ix|
if (nums_hash.has_value? (target - i))
return [nums_hash.key(target - i), ix]
end
nums_hash[ix] = i
end
end
Comments !