🏃‍♂️ Solving LeetCode Problems the TDD Way (Test-First Ruby): Maximum Subarray

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.

🔧 Setting up the TDD environment

mkdir maximum_subarray
touch maximum_subarray/maximum_subarray.rb
touch maximum_subarray/test_maximum_subarray.rb

❌ Red: Writing the failing test

Test File:

# ❌ 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.
#######################################


✗ ruby maximum_subarray/test_maximum_subarray.rb
Run options: --seed 18237

# Running:
E.

Finished in 0.000404s, 4950.4950 runs/s, 0.0000 assertions/s.

  1) Error:
TestMaximumSubarray#test_empty_array:
NameError: uninitialized constant TestMaximumSubarray::Subarray
    maximum_subarray/test_maximum_subarray.rb:31:in 'TestMaximumSubarray#test_empty_array'

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

✅ Green: Making it pass

# frozen_string_literal: true

require 'minitest/autorun'
require_relative 'maximum_subarray'
#################################
## Example 1:
# ..........
#################################
class TestMaximumSubarray < Minitest::Test
  def setup
    ####
  end

  def test_empty_array
    assert_equal 'Provide non-empty array', Subarray.new([]).max
  end

  def test_array_with_length_one
    assert_equal 1, Subarray.new([1]).max
  end
end


✗ ruby maximum_subarray/test_maximum_subarray.rb
Run options: --seed 52896

# Running:
.

Finished in 0.000354s, 2824.8588 runs/s, 2824.8588 assertions/s.
1 runs, 1 assertions, 0 failures, 0 errors, 0 skips

# 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

The total number of operations is:

  • i=0: inner loop runs (n-1) times
  • i=1: inner loop runs (n-2) times
  • i=2: inner loop runs (n-3) times
  • …
  • i=n-1: inner loop runs 0 times

Total iterations = (n-1) + (n-2) + (n-3) + … + 1 + 0 = n(n-1)/2 = O(n²)

Space Complexity: O(n)

The space usage comes from:

  • Constant space: maximum_sum, current_sum, is_last_number_of_array → O(1)
  • 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

The Problem: https://leetcode.com/problems/maximum-subarray/description/

The Solution: https://leetcode.com/problems/maximum-subarray/description/?submissionId=1666303592

https://leetcode.com/problems/maximum-subarray/description/submissions/1666303592/

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