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.
Since this problem is based on a String let’s consider the ways in which we can traverse through a string in Ruby.
Here are the various ways you can traverse a string in Ruby:
🔤 Character-by-Character Traversal
🔄 Using each_char
str = "hello"
str.each_char do |char|
puts char
end
# Output: h, e, l, l, o
📊 Using chars (returns array)
str = "hello"
str.chars.each do |char|
puts char
end
# Or get the array directly
char_array = str.chars # => ["h", "e", "l", "l", "o"]
🔢 Using index access with loop
str = "hello"
(0...str.length).each do |i|
puts str[i]
end
📍 Using each_char.with_index
str = "hello"
str.each_char.with_index do |char, index|
puts "#{index}: #{char}"
end
# Output: 0: h, 1: e, 2: l, 3: l, 4: o
💾 Byte-Level Traversal
🔄 Using each_byte
str = "hello"
str.each_byte do |byte|
puts byte # ASCII values
end
# Output: 104, 101, 108, 108, 111
str = "hello123world456"
str.scan(/\d+/) do |match|
puts match
end
# Output: "123", "456"
# Or get array of matches
numbers = str.scan(/\d+/) # => ["123", "456"]
🔄 Using gsub for traversal and replacement
str = "hello"
result = str.gsub(/[aeiou]/) do |vowel|
vowel.upcase
end
# result: "hEllO"
🪓 Splitting and Traversal
✂️ Using split
str = "apple,banana,cherry"
str.split(',').each do |fruit|
puts fruit
end
# With regex
str = "one123two456three"
str.split(/\d+/).each do |word|
puts word
end
# Output: "one", "two", "three"
🚀 Advanced Iteration Methods
🌐 Using each_grapheme_cluster (for complex Unicode)
str = "नमस्ते" # Hindi word
str.each_grapheme_cluster do |cluster|
puts cluster
end
each_char is generally more memory-efficient than chars for large strings
each_byte is fastest for byte-level operations
scan is efficient for pattern-based extraction
Direct indexing with loops can be fastest for simple character access
💡 Common Use Cases
Character counting: Use each_char or chars
Unicode handling: Use each_codepoint or each_grapheme_cluster
Text processing: Use each_line or lines
Pattern extraction: Use scan
String transformation: Use gsub with blocks
🎲 Episode 6: Longest Substring Without Repeating Characters
# Given a string s, find the length of the longest substring without duplicate characters.
# Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
#Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
#Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
# Constraints:
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
# ❌ Fail
# frozen_string_literal: true
require 'minitest/autorun'
require_relative 'longest_substring'
#################################
## Example 1:
# Input: s = "abcabcbb"
# Output: 3
# Explanation: The answer is "abc", with the length of 3.
#################################
class TestLongestSubstring < Minitest::Test
def setup
####
end
def test_empty_array
assert_equal 0, Substring.new('').longest
end
end
Source Code:
# frozen_string_literal: true
#######################################
# Given a string s, find the length of the longest substring without duplicate characters.
# Example 1:
# Input: s = "abcabcbb"
# Output: 3
# Explanation: The answer is "abc", with the length of 3.
# Example 2:
# Input: s = "bbbbb"
# Output: 1
# Explanation: The answer is "b", with the length of 1.
# Example 3:
# Input: s = "pwwkew"
# Output: 3
# Explanation: The answer is "wke", with the length of 3.
# Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
# Constraints:
# 0 <= s.length <= 5 * 104
# s consists of English letters, digits, symbols and spaces.
#######################################
# Pass ✅
# frozen_string_literal: true
#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.
# Example 1:
# ........
#######################################
class Substring
def initialize(string)
@string = string
end
def longest
return 0 if @string.empty?
1 if @string.length == 1
end
end
# frozen_string_literal: true
require 'minitest/autorun'
require_relative 'longest_substring'
#################################
## Example 1:
# ..........
#################################
class TestLongestSubstring < Minitest::Test
def setup
####
end
def test_empty_array
assert_equal 0, Substring.new('').longest
end
def test_array_with_length_one
assert_equal 1, Substring.new('a').longest
end
end
# Solution 1 ✅
# frozen_string_literal: true
#######################################
# Given a string s, find the length of the longest substring without duplicate characters.
# Example 1:
# Input: s = "abcabcbb"
# Output: 3
# Explanation: The answer is "abc", with the length of 3.
# Example 2:
# Input: s = "bbbbb"
# Output: 1
# Explanation: The answer is "b", with the length of 1.
# Example 3:
# Input: s = "pwwkew"
# Output: 3
# Explanation: The answer is "wke", with the length of 3.
# Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
# Constraints:
# 0 <= s.length <= 5 * 104
# s consists of English letters, digits, symbols and spaces.
#######################################
class Substring
def initialize(string)
@string = string
end
def longest
return 0 if @string.empty?
return 1 if @string.length == 1
max_count_hash = {} # calculate max count for each char position
distinct_char = []
@string.each_char.with_index do |char, i|
max_count_hash[i] ||= 1 # escape nil condition
distinct_char << char unless distinct_char.include?(char)
next if @string[i] == @string[i + 1]
@string.chars[(i + 1)..].each do |c|
if distinct_char.include?(c)
distinct_char = [] # clear for next iteration
break
end
distinct_char << c # update distinct char
max_count_hash[i] += 1
end
end
max_count_hash.values.max
end
end
🔍 Algorithm Analysis:
✅ What works well:
Edge cases handled properly – Empty strings and single characters
Brute force approach – Tries all possible starting positions
Correct logic flow – For each starting position, extends the substring until a duplicate is found
Proper tracking – Uses max_count_hash to store the longest substring length from each position
📝 How it works:
For each character position i, it starts a substring
Extends the substring character by character until it hits a duplicate
Tracks the maximum length found from each starting position
Returns the overall maximum
⚡ Time Complexity:
O(n²) in worst case – which is acceptable for this problem size
💭 Alternative approaches:
While our algorithm works perfectly, the sliding window technique (O(n)) is considered the optimal solution, but our brute force approach is:
✅ Easier to understand
✅ Correct and reliable
✅ Handles all edge cases properly
Our algorithm is completely correct! The earlier test failures were likely due to incorrect expected values in the test assertions, not our implementation. Well done! 🚀
Let’s try this solution in LeetCode since LeetCode provides more than one submission and see what happens (We know this solution is not Optimal and has O(n²) complexity. Still we are eager to see the output from LeetCode:
Time Limit Exceeded!!
⏳ Finding the Time Complexity – Solution 1
Looking at our algorithm, here’s the complexity analysis:
📊 Time Complexity: O(n³)
🔄 Nested Loop Structure
@string.each_char.with_index do |char, i| # O(n) - outer loop
# ...
@string.chars[(i + 1)..].each do |c| # O(n) - inner loop
if @distinct_chars.include?(c) # O(k) - array search
@distinct_chars = []
break
end
@distinct_chars << c # O(1)
max_count_hash[i] += 1 # O(1)
end
end
⏱️ Breakdown:
Outer loop: Runs n times (where n = string length)
Inner loop: For position i, runs up to (n-i) times
Array operations: @distinct_chars.include?(c) is O(k) where k = current window size
🔢 Worst Case Calculation:
Position 0: inner loop runs (n-1) times, each with O(n) include check
Position 1: inner loop runs (n-2) times, each with O(n) include check
And so on…
Total: O(n × n × n) = O(n³)
💾 Space Complexity: O(n)
📦 Space Usage:
max_count_hash: O(n) – stores count for each starting position
@distinct_chars: O(n) – worst case stores all unique characters
@string.chars[(i + 1)..]: O(n) – creates new array slice each iteration
⚠️ Major Performance Issues
🐌 Inefficiencies:
Triple nested complexity: Much slower than optimal O(n) solution
Repeated array creation: @string.chars[(i + 1)..] creates new arrays
Linear searches: @distinct_chars.include?(c) scans entire array
Redundant work: Recalculates overlapping substrings multiple times
Our current algorithm was a brute force approach that, while logically sound, suffered from significant performance issues. The next (Solution 2) sliding window implementation is a substantial improvement, reducing complexity from O(n³) to O(n²)!
Grade for current algorithm: C- – Correct but highly inefficient 📉
♻️ Refactor: Optimizing the solution
# Solution 2 ✅
# Optimized O(n) time, O(1) space solution
# frozen_string_literal: true
#######################################
# Given a string s, find the length of the longest substring without duplicate characters.
# Example 1:
# Input: s = "abcabcbb"
# Output: 3
# Explanation: The answer is "abc", with the length of 3.
# Example 2:
# Input: s = "bbbbb"
# Output: 1
# Explanation: The answer is "b", with the length of 1.
# Example 3:
# Input: s = "pwwkew"
# Output: 3
# Explanation: The answer is "wke", with the length of 3.
# Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
# Constraints:
# 0 <= s.length <= 5 * 104
# s consists of English letters, digits, symbols and spaces.
#######################################
class Substring
def initialize(string)
@string = string
@substring_lengths = []
# store distinct chars for each iteration then clear it
@distinct_chars = []
end
def longest_optimal
return 0 if @string.empty?
return 1 if @string.length == 1
find_substring
end
private
def find_substring
@string.each_char.with_index do |char, char_index|
# Duplicate char detected
if @distinct_chars.include?(char)
start_new_substring(char)
next
else # fresh char detected
update_fresh_char(char, char_index)
end
end
@substring_lengths.max
end
def start_new_substring(char)
# store the current substring length
@substring_lengths << @distinct_chars.size
# update the distinct chars avoiding old duplicate char and adding current
# duplicate char that is detected
@distinct_chars = @distinct_chars[(@distinct_chars.index(char) + 1)..]
@distinct_chars << char
end
def update_fresh_char(char, char_index)
@distinct_chars << char
last_char = char_index == @string.length - 1
# Check if this is the last character
return unless last_char
# Handle end of string - store the final substring length
@substring_lengths << @distinct_chars.size
end
end
⏳ Finding the Time Complexity – Solution 2
Looking at our algorithm (Solution 2) for finding the longest substring without duplicate characters, here’s the analysis:
🎯 Algorithm Overview
Our implementation uses a sliding window approach with an array to track distinct characters. It correctly identifies duplicates and adjusts the window by removing characters from the beginning until the duplicate is eliminated.
✅ What Works Well
🔧 Correct Logic Flow
Properly handles edge cases (empty string, single character)
Correctly implements the sliding window concept
Accurately stores and compares substring lengths
Handles the final substring when reaching the end of the string
🎪 Clean Structure
Well-organized with separate methods for different concerns
Clear variable naming and method separation
⚠️ Drawbacks & Issues
🐌 Performance Bottlenecks
Array Operations: Using @distinct_chars.include?(char) is O(k) where k is current window size
Index Finding: @distinct_chars.index(char) is another O(k) operation
Array Slicing: Creating new arrays with [(@distinct_chars.index(char) + 1)..] is O(k)
🔄 Redundant Operations
Multiple array traversals for the same character lookup
Storing all substring lengths instead of just tracking the maximum
📊 Complexity Analysis
⏱️ Time Complexity: O(n²)
Main loop: O(n) – iterates through each character once
For each character: O(k) operations where k is current window size
Worst case: O(n × n) = O(n²) when no duplicates until the end
💾 Space Complexity: O(n)
@distinct_chars: O(n) in worst case (no duplicates)
@substring_lengths: O(n) in worst case (many substrings)
📈 Improved Complexity
Time: O(n) – single pass with O(1) hash operations
Space: O(min(m, n)) where m is character set size
🎖️ Overall Assessment
Our algorithm is functionally correct and demonstrates good understanding of the sliding window concept. However, it’s not optimally efficient due to array-based operations. The logic is sound, but the implementation could be significantly improved for better performance on large inputs.
Grade: B – Correct solution with room for optimization! 🎯
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 5: Maximum Subarray
#Given an integer array nums, find the subarray with the largest #sum, and return its sum.
#Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
#Explanation: The subarray [4,-1,2,1] has the largest sum 6.
#Example 2:
Input: nums = [1]
Output: 1
#Explanation: The subarray [1] has the largest sum 1.
#Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
#Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
#Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
#Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
# ❌ Fail
# frozen_string_literal: true
require 'minitest/autorun'
require_relative 'maximum_subarray'
#################################
## Example 1:
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# ..........
#################################
class TestMaximumSubarray < Minitest::Test
def setup
####
end
def test_empty_array
assert_equal 'Provide non-empty array', Subarray.new([]).max
end
end
Source Code:
# frozen_string_literal: true
#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.
# Example 1:
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
# Explanation: The subarray [4,-1,2,1] has the largest sum 6.
# Example 2:
# Input: nums = [1]
# Output: 1
# Explanation: The subarray [1] has the largest sum 1.
# Example 3:
# Input: nums = [5,4,-1,7,8]
# Output: 23
# Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
# Constraints:
# 1 <= nums.length <= 105
# -104 <= nums[i] <= 104
# Follow up: If you have figured out the O(n) solution, try coding another solution using
# the divide and conquer approach, which is more subtle.
#######################################
# Pass ✅
# frozen_string_literal: true
#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.
# Example 1:
# ........
#######################################
class Subarray
def initialize(numbers)
@numbers = numbers
end
def max
return 'Provide non-empty array' if @numbers.empty?
@numbers.first if @numbers.length == 1
end
end
………………………………………………….⤵ …………………………………………………………..
# Full Solution 1 ✅
# frozen_string_literal: true
#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.
# Example 1:
# .........
#
# Ex: Subarray.new([4, -1, 2, 1]).max_sum
#######################################
class Subarray
def initialize(numbers)
@numbers = numbers
end
def max_sum
return 'Provide non-empty array' if @numbers.empty?
return @numbers.first if @numbers.length == 1
maximum_sum = @numbers.first
# do array right side scan
@numbers.each_with_index do |num, i|
current_sum = num # calculate from current number
right_side_numbers = @numbers[(i + 1)..]
is_last_number_of_array = right_side_numbers.empty?
maximum_sum = current_sum if is_last_number_of_array && current_sum > maximum_sum
right_side_numbers.each do |num_right|
current_sum += num_right
maximum_sum = current_sum if current_sum > maximum_sum
end
end
maximum_sum
end
end
⏳ Finding the Time Complexity
Looking at our max_sum algorithm, let’s analyze the time and space complexity:
Time Complexity: O(n²)
The algorithm has two nested loops:
Outer loop: @numbers.each_with_index runs n times (where n = array length)
Inner loop: right_side_numbers.each runs (n-i-1) times for each position i
Array slicing: @numbers[(i + 1)..] creates a new array slice each iteration → O(n)
The key space consumer is the line:
right_side_numbers = @numbers[(i + 1)..]
This creates a new array slice for each position. The largest slice (when i=0) has size (n-1), so the space complexity is O(n).
Summary:
Time Complexity: O(n²) – quadratic due to nested loops
Space Complexity: O(n) – linear due to array slicing
This is a brute force approach that checks all possible contiguous subarrays by starting from each position and extending to the right.
♻️ Refactor: Optimizing the solution
# Final - Solution 2 ✅
# Optimized O(n) time, O(1) space solution
# frozen_string_literal: true
#######################################
# Given an integer array nums, find the subarray with the largest #sum, and return its sum.
# Example 1:
# Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
# Output: 6
# Explanation: The subarray [4,-1,2,1] has the largest sum 6.
# Example 2:
# Input: nums = [1]
# Output: 1
# Explanation: The subarray [1] has the largest sum 1.
# Example 3:
# Input: nums = [5,4,-1,7,8]
# Output: 23
# Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
# Constraints:
# 1 <= nums.length <= 105
# -104 <= nums[i] <= 104
# Follow up: If you have figured out the O(n) solution, try coding another solution using
# the divide and conquer approach, which is more subtle.
#
# Ex: Subarray.new([4, -1, 2, 1]).max_sum
#######################################
class Subarray
def initialize(numbers)
@numbers = numbers
end
def max_sum
return 'Provide non-empty array' if @numbers.empty?
return @numbers.first if @numbers.length == 1
max_sum = @numbers.first
inherit_sum = @numbers.first
@numbers[1..].each do |num|
inherit_sum_add_num = inherit_sum + num
# if current num is greater than inherited sum break the loop and start from current num
inherit_sum = num > inherit_sum_add_num ? num : inherit_sum_add_num
# preserve highest of this inherited sum for each element iteration
max_sum = inherit_sum > max_sum ? inherit_sum : max_sum
end
max_sum
end
end
LeetCode Submission:
# @param {Integer[]} nums
# @return {Integer}
# [4, -1, 2, 1]
# [-2, 1, -3, 4]
def max_sub_array(nums)
return 'Provide non-empty array' if nums.empty?
return nums.first if nums.length == 1
max_sum = nums.first
inherit_sum = nums.first
nums[1..].each do |num|
inherit_sum_add_num = inherit_sum + num
# if current num is greater than inherited sum break the loop and start from current num
inherit_sum = num > inherit_sum_add_num ? num : inherit_sum_add_num
# preserve highest of this inherited sum for each element iteration
max_sum = inherit_sum > max_sum ? inherit_sum : max_sum
end
max_sum
end
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
################
# ❌ 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
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 3: Contains Duplicate
# Given an integer array nums, return true if any value appears # at least twice in the array, and return false if every element # is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Explanation:
The element 1 occurs at the indices 0 and 3.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
All elements are distinct.
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
# Pass ✅
# frozen_string_literal: true
#############################
#
# Given an integer array nums, return true if any value appears at least twice in the array,
# and return false if every element is distinct.
# Example 1:
# .......
#############################
class Duplicate
def initialize(nums)
@numbers = nums
end
def present?
'Provide a non-empty array' if @numbers.empty?
end
end
…………………………………………………. ⤵ …………………………………………………………..
Writing the Second Test Case:
# frozen_string_literal: true
require 'minitest/autorun'
require_relative 'array_duplicate'
######################################
# Given an integer array nums, return true if any value appears at least twice in the array,
# and return false if every element is distinct.
#
# Example 1:
# Input: nums = [1,2,3,1]
# Output: true
#
# Example 2:
# Input: nums = [1,2,3,4]
# Output: false
#
######################################
class TestArrayDuplicate < Minitest::Test
def setup
####
end
def test_empty_array
assert_equal 'Provide a non-empty array', Duplicate.new([]).present?
end
def test_array_with_length_one
assert_equal false, Duplicate.new([2]).present?
end
def test_array_with_length_two
assert_equal false, Duplicate.new([1, 2]).present?
assert_equal true, Duplicate.new([2, 2]).present?
end
end
# Solution 1 ✅
# frozen_string_literal: true
#############################
#
# Given an integer array nums, return true if any value appears at least twice in the array,
# and return false if every element is distinct.
# Example 1:
# ........
#############################
class Duplicate
def initialize(nums)
@numbers = nums
end
def present?
return 'Provide a non-empty array' if @numbers.empty?
count_hash = {}
@numbers.each do |number|
count_hash[number] ? count_hash[number] += 1 : count_hash[number] = 1
end
count_hash.values.max > 1
end
end
⏳ Finding the Time Complexity
Time Complexity: O(n)
You iterate through the array once: @numbers.each do |number| → O(n)
Hash operations (lookup and assignment) are O(1) on average
count_hash.values.max → O(n) to get all values and find max
Total: O(n) + O(n) = O(n)
Space Complexity: O(n)
In worst case (all elements are unique), you store n key-value pairs in count_hash
Total: O(n)
♻️ Refactor: Optimizing the solution
# Solution 2 ✅
# frozen_string_literal: true
#############################
#
# Given an integer array nums, return true if any value appears at least twice in the array,
# and return false if every element is distinct.
# Example 1:
# .....
#############################
class Duplicate
def initialize(nums)
@numbers = nums
end
def present?
return 'Provide a non-empty array' if @numbers.empty?
count_hash = {}
@numbers.each do |number|
count_hash[number] ? count_hash[number] += 1 : count_hash[number] = 1
return true if count_hash[number] > 1
end
false
end
end
♻️ Refactor: Try to refactor the solution again
# Solution 3 ✅
# frozen_string_literal: true
#############################
#
# Given an integer array nums, return true if any value appears at least twice in the array,
# and return false if every element is distinct.
# Example 1:
# Input: nums = [1,2,3,1]
# .......
#############################
class Duplicate
def initialize(nums)
@numbers = nums
end
def present?
return 'Provide a non-empty array' if @numbers.empty?
found = {}
@numbers.each do |number|
return true if found[number]
found[number] = true
end
false
end
end
♻️ Refactor: Use Ruby Set – best approach
# Solution 4 ✅
# frozen_string_literal: true
#############################
#
# Given an integer array nums, return true if any value appears at least twice in the array,
# and return false if every element is distinct.
# Example 1:
# Input: nums = [1,2,3,1]
# ........
#############################
class Duplicate
def initialize(nums)
@numbers = nums
end
def present?
return 'Provide a non-empty array' if @numbers.empty?
found = Set.new
@numbers.each do |number|
return true if found.include?(number)
found.add(number)
end
false
end
end
Set vs Hash for Duplicate Detection
Set Approach:
seen = Set.new
@numbers.each do |number|
return true if seen.include?(number)
seen.add(number)
end
Hash Approach:
seen = {}
@numbers.each do |number|
return true if seen[number]
seen[number] = true
end
Why Set is Better for This Use Case:
1. Semantic Clarity
Set: Designed specifically for storing unique elements
Hash: Designed for key-value mappings
Since we only care about “have I seen this number?”, Set is semantically correct
2. Memory Efficiency
Set: Only stores the key (the number)
Hash: Stores both key AND value (number + true/false)
Set uses less memory per element
3. Intent is Clearer
# Set - clearly shows we're tracking unique elements
seen.add(number)
seen.include?(number)
# Hash - less clear why we're setting values to true
seen[number] = true
seen[number] # relies on truthy/falsy behavior
4. Performance
Both have O(1) average lookup time, but:
Set operations are optimized for membership testing
Hash has slight overhead for value storage
When to Use Each:
Use Set when:
You only need to track “presence” or “membership”
You want to store unique elements
You don’t need associated values
This duplicate detection problem ✅
Use Hash when:
You need to store key-value pairs
You need to count occurrences
You need to associate data with keys
Example: {number => count} for frequency counting
Alternative Hash Approach (Still Valid):
If you prefer Hash, this is also perfectly fine:
seen = {}
@numbers.each do |number|
return true if seen.key?(number) # More explicit than seen[number]
seen[number] = true
end
Bottom Line:
Both work correctly with the same time/space complexity, but Set is the better choice because:
The Rails Drop 