CODEWITHSUNDEEP
arraysruby
svelandiag
svelandiag

Reputation: 4320

What's the most efficient way to manipulate Arrays in Ruby

Im trying to make the following code more efficient but ran out of ideas, so looking for some help:

I receive an interval x and an Array of Integers space, I need to separate the space array into segments of x interval so for example if

space = [1, 2, 3, 1, 2]
x = 2
# The intervals Would be
[1, 2][2, 3][3, 1][1, 2]

So Then I need to find the minimum on each interval and then find the Max value of the minimums, so in the example above the minimums would be:

[1, 2, 1, 1]

Then I need to return the max value of the minimums that would be 2

Below is my solution, most test cases pass but some of them are failing because the time execution is exceeded. Any idea about how to make the following code more efficient?

def segment(x, space)
    minimums = {}
    space.each_with_index do |_val, index|
        # 1 Create the segment
        mark = x - 1
        break if mark >= space.length 
        segment = space[index..mark]
        x = x + 1    
        # 2 Find the min of the segment
        minimum = segment.min
        minimums[index] = minimum
    end
    
    # Compare the maximum of the minimums
    return minimums.values.max
end

I tried making the minimums a hash instead of an array but didn't work. Also I thought I would convert the space array to a hash and manipulate the a hash instead of an Array, but I think that would be even more complicated...

Upvotes: 0

Views: 177

Answers (1)

matt
matt

Reputation: 534925

You don’t need to collect the segments and process them later. Just walk the array once, keeping the largest min of each segment as you go.

Also each_with_index is a waste. Just walk the array yourself taking successive slices.

Simple example:

# initial conditions
space = [1, 2, 3, 1, 2]
x = 2
# here we go
min = space.min
(0..space.length-x).each do |i|
  min = [space[i,x].min, min].max
end
puts min

As usual in ruby, there's always a more elegant way. For example, no need to create the slices; let ruby do it (each_cons):

# initial conditions
space = [1, 2, 3, 1, 2]
x = 2
# here we go
min = space.min
space.each_cons(x) do |slice|
  min = [slice.min, min].max
end
puts min

And of course once you understand how this works, it can be refined even further (e.g. as shown in the comment below).

Upvotes: 2

Related Questions