🏃‍♂️ Solving LeetCode Problems the TDD Way (Test-First Ruby): Product of Array Except Self

Welcome to my new series where I combine the power of Ruby with the discipline of Test-Driven Development (TDD) to tackle popular algorithm problems from LeetCode! 🧑‍💻💎 Whether you’re a Ruby enthusiast looking to sharpen your problem-solving skills, or a developer curious about how TDD can transform the way you approach coding challenges, you’re in the right place.

🎲 Episode 4: Product of Array Except Self

################
# Product of Array Except Self
#
# Given an integer array nums, return an array answer such that answer[i] is equal to
# the product of all the elements of nums except nums[i].
# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
# You must write an algorithm that runs in O(n) time and without using the division operation.
# Example 1:

# Input: nums = [1,2,3,4]
# Output: [24,12,8,6]
# Example 2:

# Input: nums = [-1,1,0,-3,3]
# Output: [0,0,9,0,0]

# Constraints:

# 2 <= nums.length <= 105
# -30 <= nums[i] <= 30
# The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

# Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
#
# Ex: Numbers.new([2,3,4]).product_except_self
################

🔧 Setting up the TDD environment

mkdir product_except_self
touch product_except_self.rb
touch test_product_except_self.rb

❌ Red: Writing the failing test

Test File:

# ❌ Fail
# frozen_string_literal: true

require 'minitest/autorun'
require_relative 'product_except_self'
################
# Product of Array Except Self
#
# Given an integer array nums, return an array answer such that answer[i] is equal to
# the product of all the elements of nums except nums[i].
# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
# You must write an algorithm that runs in O(n) time and without using the division operation.
################
class TestProductExceptSelf < Minitest::Test
  def set_up
    ###
  end

  def test_empty_array
    assert_equal 'Provide an aaray of length atleast two', ProductNumbers.new([]).except_self
  end
end

Source Code:

# frozen_string_literal: true

################
# Product of Array Except Self
#
# Given an integer array nums, return an array answer such that answer[i] is equal to
# the product of all the elements of nums except nums[i].
# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
# You must write an algorithm that runs in O(n) time and without using the division operation.
################
class ProductNumbers
  def initialize(nums)
    @numbers = nums
  end

  def except_self; end
end

 ✗ ruby product_except_self/test_product_except_self.rb 
Run options: --seed 12605

# Running:
F
Finished in 0.009644s, 103.6914 runs/s, 103.6914 assertions/s.

  1) Failure:
TestProductExceptSelf#test_empty_array [product_except_self/test_product_except_self.rb:19]:
--- expected
+++ actual
@@ -1 +1 @@
-"Provide an aaray of length atleast two"
+nil

1 runs, 1 assertions, 1 failures, 0 errors, 0 skips
➜  leetcode git:(main) ✗

✅ Green: Making it pass

# Pass ✅ 
# frozen_string_literal: true

################
# Product of Array Except Self
#
# Given an integer array nums, return an array answer such that answer[i] is equal to
# the product of all the elements of nums except nums[i].
# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
# You must write an algorithm that runs in O(n) time and without using the division operation.
# Example 1:
# ......
#
# Ex: Numbers.new([2,3,4]).product_except_self
################
class Numbers
  def initialize(nums)
    @numbers = nums
  end

  def product_except_self
    'Provide an array of length atleast two' if @numbers.length < 2
  end
end

………………………………………………….⤵ …………………………………………………………..

# Solution 1 ✅ 
# frozen_string_literal: true

################
# Product of Array Except Self
#
# Given an integer array nums, return an array answer such that answer[i] is equal to
# the product of all the elements of nums except nums[i].
# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
# You must write an algorithm that runs in O(n) time and without using the division operation.
# Example 1:

# Input: nums = [1,2,3,4]
# Output: [24,12,8,6]
# Example 2:

# Input: nums = [-1,1,0,-3,3]
# Output: [0,0,9,0,0]

# Constraints:

# 2 <= nums.length <= 105
# -30 <= nums[i] <= 30
# The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

# Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
#
# Ex: Numbers.new([2,3,4]).product_except_self
################
class Numbers
  def initialize(nums)
    @numbers = nums
  end

  def product_except_self
    return 'Provide an array of length atleast two' if @numbers.length < 2

    answer = []
    @numbers.each_with_index do |_number, index|
      answer << @numbers.reject.with_index { |_num, i| index == i }.inject(:*)
    end

    answer
  end
end

⏳ Finding the Time Complexity

Let’s analyse time and space complexity of the very first solution found to the current problem.

Time Complexity: O(n²)

Let’s break down the operations:

@numbers.each_with_index do |_number, index|  # O(n) - outer loop
  answer << @numbers.reject.with_index { |_num, i| index == i }.inject(:*)
  #                  ↑ reject: O(n)              ↑ inject: O(n-1) ≈ O(n)
end
  • Outer loop: Runs n times (where n is array length)
  • For each iteration:
  • reject.with_index: O(n) – goes through all elements to create new array
  • inject(:*): O(n) – multiplies all elements in the rejected array

Total: O(n) × O(n) = O(n²)

Space Complexity: O(n) (excluding output array)
  • reject.with_index creates a new temporary array of size n-1 in each iteration
  • This temporary array uses O(n) extra space
  • Although it’s created and discarded in each iteration, we still need O(n) space at any given moment
Performance Impact

Our current solution doesn’t meet the problem’s requirement of O(n) time complexity. For an array of 10,000 elements, our solution would perform about 100 million operations instead of the optimal 10,000.

♻️ Refactor: Optimizing the solution

# Final - Solution 2 ✅ 
# Optimized O(n) time, O(1) space solution
  # frozen_string_literal: true

################
# Product of Array Except Self
#
# Given an integer array nums, return an array answer such that answer[i] is equal to
# the product of all the elements of nums except nums[i].
# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
# You must write an algorithm that runs in O(n) time and without using the division operation.
# Example 1:

# Input: nums = [1,2,3,4]
# Output: [24,12,8,6]
# Example 2:

# Input: nums = [-1,1,0,-3,3]
# Output: [0,0,9,0,0]

# Constraints:

# 2 <= nums.length <= 105
# -30 <= nums[i] <= 30
# The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

# Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
#
# Ex: Numbers.new([2,3,4]).product_except_self
################
class Numbers
  def initialize(nums)
    @numbers = nums
    @answer = []
  end

  # Original O(n²) time, O(n) space solution
  def product_except_self
    return 'Provide an array of length atleast two' if @numbers.length < 2

    answer = []
    @numbers.each_with_index do |_number, index|
      answer << @numbers.reject.with_index { |_num, i| index == i }.inject(:*)
    end

    answer
  end

  # Optimized O(n) time, O(1) space solution
  def product_except_self_optimized
    return 'Provide an array of length atleast two' if @numbers.length < 2

    calculate_left_products
    multiply_right_products

    @answer
  end

  private

  # STEP 1: Fill @answer[i] with product of all numbers TO THE LEFT of i
  def calculate_left_products
    left_product = 1
    0.upto(@numbers.length - 1) do |i|
      @answer[i] = left_product
      left_product *= @numbers[i] # Update for next iteration
    end
  end

  # STEP 2: Multiply @answer[i] with product of all numbers TO THE RIGHT of i
  def multiply_right_products
    right_product = 1
    (@numbers.length - 1).downto(0) do |i|
      @answer[i] *= right_product
      right_product *= @numbers[i] # Update for next iteration
    end
  end
end

Test Case for Above Optimized Solution:

# frozen_string_literal: true

require 'minitest/autorun'
require_relative 'product_except_self'
################
# Product of Array Except Self
#
# Given an integer array nums, return an array answer such that answer[i] is equal to
# the product of all the elements of nums except nums[i].
# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
# You must write an algorithm that runs in O(n) time and without using the division operation.
################
class TestProductExceptSelf < Minitest::Test
  def set_up
    ###
  end

  def test_empty_array
    assert_equal 'Provide an array of length atleast two', Numbers.new([]).product_except_self
    assert_equal 'Provide an array of length atleast two', Numbers.new([]).product_except_self_optimized
  end

  def test_array_of_length_one
    assert_equal 'Provide an array of length atleast two', Numbers.new([4]).product_except_self
    assert_equal 'Provide an array of length atleast two', Numbers.new([4]).product_except_self_optimized
  end

  def test_array_of_length_two
    assert_equal [3, 4], Numbers.new([4, 3]).product_except_self
    assert_equal [6, 5], Numbers.new([5, 6]).product_except_self

    # Test optimized version
    assert_equal [3, 4], Numbers.new([4, 3]).product_except_self_optimized
    assert_equal [6, 5], Numbers.new([5, 6]).product_except_self_optimized
  end

  def test_array_of_length_three
    assert_equal [6, 3, 2], Numbers.new([1, 2, 3]).product_except_self
    assert_equal [15, 20, 12], Numbers.new([4, 3, 5]).product_except_self

    # Test optimized version
    assert_equal [6, 3, 2], Numbers.new([1, 2, 3]).product_except_self_optimized
    assert_equal [15, 20, 12], Numbers.new([4, 3, 5]).product_except_self_optimized
  end

  def test_array_of_length_four
    assert_equal [70, 140, 56, 40], Numbers.new([4, 2, 5, 7]).product_except_self
    assert_equal [216, 54, 36, 24], Numbers.new([1, 4, 6, 9]).product_except_self

    # Test optimized version
    assert_equal [70, 140, 56, 40], Numbers.new([4, 2, 5, 7]).product_except_self_optimized
    assert_equal [216, 54, 36, 24], Numbers.new([1, 4, 6, 9]).product_except_self_optimized
  end

  def test_leetcode_examples
    # Example 1: [1,2,3,4] -> [24,12,8,6]
    assert_equal [24, 12, 8, 6], Numbers.new([1, 2, 3, 4]).product_except_self_optimized

    # Example 2: [-1,1,0,-3,3] -> [0,0,9,0,0]
    assert_equal [0, 0, 9, 0, 0], Numbers.new([-1, 1, 0, -3, 3]).product_except_self_optimized
  end

  def test_both_methods_give_same_results
    test_cases = [
      [4, 3],
      [1, 2, 3],
      [4, 2, 5, 7],
      [1, 4, 6, 9],
      [-1, 1, 0, -3, 3],
      [2, 3, 4, 5]
    ]

    test_cases.each do |nums|
      original_result = Numbers.new(nums).product_except_self
      optimized_result = Numbers.new(nums).product_except_self_optimized
      assert_equal original_result, optimized_result, "Results don't match for #{nums}"
    end
  end
end

LeetCode Submission:

# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
    return 'Provide an array of length atleast two' if nums.length < 2
    answer = []

    answer = left_product_of_numbers(nums, answer)
    answer = right_product_of_numbers(nums, answer)
    answer
end

# scan right and find left side product of numbers 
def left_product_of_numbers(nums, answer)
    left_product = 1 # a place holder for multiplication
    0.upto(nums.length - 1) do |i|
        answer[i] = left_product
        left_product = nums[i] * left_product
    end
    answer
end

# scan left and find right side product of numbers 
def right_product_of_numbers(nums, answer)
    right_product = 1 # a place holder for multiplication
    (nums.length - 1).downto(0) do |i|
        answer[i] = answer[i] * right_product
        right_product = nums[i] * right_product
    end
    answer
end

The Problem: https://leetcode.com/problems/product-of-array-except-self/description/

The Solution: https://leetcode.com/problems/product-of-array-except-self/description/?submissionId=xxxxxx

https://leetcode.com/problems/product-of-array-except-self/submissions/xxxxxxxx/

Happy Algo Coding! 🚀

Unknown's avatar

Author: Abhilash

Hi, I’m Abhilash! A seasoned web developer with 15 years of experience specializing in Ruby and Ruby on Rails. Since 2010, I’ve built scalable, robust web applications and worked with frameworks like Angular, Sinatra, Laravel, Node.js, Vue and React. Passionate about clean, maintainable code and continuous learning, I share insights, tutorials, and experiences here. Let’s explore the ever-evolving world of web development together!

Leave a comment