Category: TDD

#####################################
#   Problem 1: The Two Sum Problem
#####################################

# Given an array of integers 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.
# Example 1:

# Input: nums = [2,7,11,15], target = 9
# Output: [0,1]
# Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
# Example 2:

# Input: nums = [3,2,4], target = 6
# Output: [1,2]
# Example 3:

# Input: nums = [3,3], target = 6
# Output: [0,1]

# Constraints:
# Only one valid answer exists.

# We are not considering following concepts for now:
# 2 <= nums.length <= 104
# -109 <= nums[i] <= 109
# -109 <= target <= 109

# Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

mkdir two_sum
touch test_two_sum.rb
touch two_sum.rb

# frozen_string_literal: true

require 'minitest/autorun'
require_relative 'two_sum'

###############################
# This is the test case for finding the index of two numbers in an array
# such that adding both numbers should be equal to the target number provided
#
#  Ex:
#    two_sum(num, target)
#    num: [23, 4, 8, 92], tatget: 12
#    output: [1, 2] => index of the two numbers whose sum is equal to target
##############################
class TestTwoSum < Minitest::Test
  def setup
    ####
  end

  def test_array_is_an_empty_array
    assert_equal 'Provide an array with length 2 or more', two_sum([], 9)
  end
end

# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

def two_sum(nums, target)
end

ruby test_two_sum.rb

Run options: --seed 58910
# Running:
F
Finished in 0.008429s, 118.6380 runs/s, 118.6380 assertions/s.

  1) Failure:
TestTwoSum#test_array_is_an_empty_array [test_two_sum.rb:21]:
--- expected
+++ actual
@@ -1 +1 @@
-"Provide an array with length 2 or more"
+nil

1 runs, 1 assertions, 1 failures, 0 errors, 0 skips

# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

def two_sum(nums, target)
  'Provide an array with length 2 or more' if nums.empty?
end

❌
# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

def two_sum(nums, target)
  return 'Provide an array with length 2 or more' if nums.empty?

  nums.each_with_index do |selected_num, selected_index|
    nums.each_with_index do |num, index|
      if selected_index != index
        sum = selected_num[selected_index] + num[index]
        return [selected_index, index] if sum == target
      end
    end
  end
end

❌
# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

def two_sum(nums, target)
  return 'Provide an array with length 2 or more' if nums.empty?

  nums.each_with_index do |selected_num, selected_index|
    nums.each_with_index do |num, index|
      next if selected_index == index

      sum = selected_num[selected_index] + num[index]
      return [selected_index, index] if sum == target
    end
  end
end

✅ 
# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

def two_sum(nums, target)
  return 'Provide an array with length 2 or more' if nums.empty?

  nums.each_with_index do |selected_num, selected_index|
    nums.each_with_index do |num, index|
      next if index <= selected_index

      return [selected_index, index] if selected_num + num == target
    end
  end
end

# frozen_string_literal: true

require 'minitest/autorun'
require_relative 'two_sum'

###############################
# This is the test case for finding the index of two numbers in an array
# such that adding both numbers should be equal to the target number provided
#
#  Ex:
#    two_sum(num, target)
#    num: [23, 4, 8, 92], tatget: 12
#    output: [1, 2] => index of the two numbers whose sum is equal to target
##############################
class TestTwoSum < Minitest::Test
  def setup
    ####
  end

  def test_array_is_an_empty_array
    assert_equal 'Provide an array with length 2 or more elements', two_sum([], 9)
  end

  def test_array_with_length_one
    assert_equal 'Provide an array with length 2 or more elements', two_sum([9], 9)
  end

  def test_array_with_length_two
    assert_equal [0, 1], two_sum([9, 3], 12)
  end

  def test_array_with_length_three
    assert_equal [1, 2], two_sum([9, 3, 4], 7)
  end

  def test_array_with_length_four
    assert_equal [1, 3], two_sum([9, 3, 4, 8], 11)
  end

  def test_array_with_length_ten
    assert_equal [7, 8], two_sum([9, 3, 9, 8, 23, 20, 19, 5, 30, 14], 35)
  end
end

# Solution 1 ✅ 

# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

def two_sum(nums, target)
  return 'Provide an array with length 2 or more elements' if nums.length < 2

  nums.each_with_index do |selected_num, selected_index|
    nums.each_with_index do |num, index|
      already_added = index <= selected_index
      next if already_added

      return [selected_index, index] if selected_num + num == target
    end
  end
end

# Solution 2 ✅ 

#####################################
# Solution 2
# TwoSum.new([2,7,11,15], 9).indices
#####################################
class TwoSum
  def initialize(nums, target)
    @numbers_array = nums
    @target = target
  end

  # @return [index_1, index_2]
  def indices
    return 'Provide an array with length 2 or more elements' if @numbers_array.length < 2

    @numbers_array.each_with_index do |num1, index1|
      next if num1 > @target # number already greater than target

      remaining_array = @numbers_array[index1..(@numbers_array.length - 1)]
      num2 = find_number(@target - num1, remaining_array)

      return [index1, @numbers_array.index(num2)] if num2
    end
  end

  private

  def find_number(number, array)
    array.each do |num|
      return num if num == number
    end
    nil
  end
end

O(n * (n + n + n)) = O(n * 3n) = O(3n²) = O(n²)

# Use a hash map to store numbers and their indices

# Solution 3 ✅  - Use Hash Map

# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

class TwoSum
  def initialize(nums, target)
    @numbers_array = nums
    @target = target
  end

  # @return [index_1, index_2]
  def indices
    return 'Provide an array with length 2 or more elements' if @numbers_array.length < 2

    hash = {}

    @numbers_array.each_with_index do |num, index|
      complement = @target - num

      # store first number to hash
      if index == 0
        hash[num] = index
      else
        # if not first number check store has
        return [hash[complement], index] if hash.key?(complement)

        # if not found store the num
        hash[num] = index
      end
    end
  end
end

def indices
  return 'Provide an array with length 2 or more elements' if @numbers_array.length < 2

  hash = {}

  @numbers_array.each_with_index do |num, index|
    complement = @target - num

    # store first number to hash
    if index == 0
      hash[num] = index 
    else
      # if not first number check store has 
      if hash.key?(complement)
        return [hash[complement], index]
      else
        # if not found store the num
        hash[num] = index
      end
    end
  end
end

# ♻️ Refactor Solution 3 ✅  - Use Hash Map

# frozen_string_literal: true

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}

class TwoSum
  def initialize(nums, target)
    @numbers_array = nums
    @target = target
  end

  # @return [index_1, index_2]
  def indices
    return 'Provide an array with length 2 or more elements' if @numbers_array.length < 2

    hash = {}

    @numbers_array.each_with_index do |num, index|
      complement = @target - num

      return [hash[complement], index] if hash.key?(complement)

      hash[num] = index
    end
  end
end

# Input Sample
TwoSum.new([2,7,11,15], 9)

   hash = {}  # Empty hash map
   target = 9

   complement = 9 - 2 = 7
   hash = {}  # Empty, so complement 7 not found
   hash[2] = 0  # Store 2 with its index 0

   complement = 9 - 7 = 2
   hash = {2 => 0}  # Found complement 2 in hash!
   return [hash[2], 1]  # Returns [0, 1]

@numbers_array.each_with_index do |num, index|
  complement = @target - num  # Calculate what number we need

  if hash.key?(complement)   # Check if we've seen the number we need
    return [hash[complement], index]  # If found, return both indices
  end

  hash[num] = index  # If not found, store current number and its index
end

# Solution 4 ✅  - Use Hash Map
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
  return 'Provide an array with length 2 or more elements' if nums.length < 2

  # number index store, use hash map, store first number in store
  store = { nums[0] => 0}
  
  # check the pair from second element
  nums.each_with_index do |num, index|
    next if index == 0 # already stored first
    pair = target - num

    return [store[pair], index] if store[pair]

    store[num] = index
  end
end