Try LetCode in Ruby-TwoSum

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 

So

[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 ...

Recommended Posts

Try LetCode in Ruby-TwoSum
Try using RocksDB in Java
Try calling JavaScript in Java
Try developing Spresense in Java (1)
Try functional type in Java! ①
Try using gRPC in Ruby
Try implementing asynchronous processing in Azure
Try implementing GraphQL server in Java
Try to implement Yubaba in Ruby
Try running ruby-net-nntp and tmail in 2020
Try running Selenuim 3.141.59 in eclipse (java)
Try an If expression in Java
Try running AWS X-Ray in Java
Try to implement Yubaba in Java
Try file locking in Ruby directory
Try to solve Project Euler in Java
Try to implement n-ary addition in Java
Try using JSON format API in Java
Try calling the CORBA service in Java 11+
Try making a calculator app in Java
Try putting Docker in ubuntu on WSL
Try with resources statement in web app