Overview

I started Let Code to improve my programming skills. I will explain the basic problem TwoSum in Ruby.

Two Sum

problem

Given an array of integers, returns an array of index combinations where the sum of the two elements is the target value.

Example

nums = [2,7,11,15]
target = 9

Is given.

nums[0] + nums[1] = 2+7 = 9

[0, 1]

Returns.

** The goal is to write a method in Ruby that meets the above requirements. ** **

Solution 1 [Brute Force]

Brute Force means "brute force" in Japanese. In other words, solve without thinking.

# @param {Integer[]}nums array of integers
# @param {Integer}target integer
# @return {Integer[]}Array of integers

def two_sum(nums, target)
  (0..nums.length-1).each do |i|
    (i+1..nums.length-1).each do |j|
      return [i, j] if nums[i] + nums[j] == target #Check if it reaches the target value
    end
  end
end

Based on one element, we will search for the elements after that to see if the sum becomes the target value.

Submitting this code will result in the following:

Runtime : 4656 ms(average)
Memory : 9.6 MB(average)

The average is roughly above, but sometimes it's a time limit. (Out as a submission)

This is calculated by ʻeach` an average of n times x n-1 times, so the complexity order is indicated by * O * ($ n ^ 2 $). That is, the larger the number of elements, the more time is required as a quadratic function.

Solution 2 [Two-pass Hash Table]

It is more efficient to look for the complement that is target value-element 1 than to look for the element whose sum is the target value. Hashes are used there.

# @param {Integer[]}nums array of integers
# @param {Integer}target integer
# @return {Integer[]}Array of integers

def two_sum(nums, target)
  hash = {}
  (0..nums.length-1).each do |i|
    hash.store(nums[i], i) #Initialize hash
  end
  (0..nums.length-1).each do |i|
    complement = target - nums[i] #Prepare complement
    return [i, hash.fetch(complement)] if hash.has_key?(complement) && hash.fetch(complement) != i #Complement check
  end
end

Prepare a hash in advance and search for the complement value stored.

By doing this, ʻeach` calculates n times x n-1 times only n times. Therefore, the complexity order is * O * ($ n $). And if you submit this code, the result will be:

Runtime : 43 ms(average)
Memory : 10.2 MB(average)

It uses a little more memory, but it's horribly faster.

Solution 3 [One-pass Hash Table]

This time there is also a technique using the same hash. It is completed in one scan.

# @param {Integer[]}nums array of integers
# @param {Integer}target integer
# @return {Integer[]}Array of integers

def two_sum(nums, target)
  hash = {}
  (0..nums.length-1).each do |i|
    complement = target - nums[i]
    return [hash.fetch(complement), i] if hash.has_key?(complement) #Complement check
    hash.store(nums[i], i) #Added because the complement did not exist
end

The amount of code has been reduced, but it is harder to read. This is a method to add elements when the elements that satisfy the conditions are not found. The amount of memory can be reduced a little because elements are added and searched in one scan. Similarly, the complexity order is * O * ($ n $), and the submission result is as follows.

Runtime : 48 ms(average)
Memory : 9.9 MB(average)

It's a little slower, but it uses less memory. Which method is better than ** Solution 2 ** depends on the situation, I think it's clear how good the hash method is compared to ** Solution 1 **! Also, since the number of trials is 7 each, the accuracy of the average value is not high, but it is clear from this result.

Summary

I explained Two Sum, which is the basic problem of Leet Code. We also found that the execution time can be significantly reduced by taking an appropriate solution. I think I learned a lot just by solving this one problem properly. I want to continue Let Code ...

Try LetCode in Ruby-TwoSum