Ruby Complexity / Time explaination

Question

I am using HackerRank to improve my ruby skills. I am on the Data Structures - Array Manipulation problem: https://www.hackerrank.com/challenges/crush/problem

My solution is listed first, a supposedly "correct" solution I haven't been able to implement is listed last. My solution works for all test cases except **VERY ** large numbers, it fails due to timeout. I know this is because of a loop, but can someone offer a different solution, and explain why theirs works?

EXPLAINATION OF PROBLEM:

Sample Input

5 3
1 2 100
2 5 100
3 4 100
#n=5 m=3, then following numbers leftIndex=1 rightIndex=3 sum=100 and so on

Sample Output

Explanation

After the first update list will be 100 100 0 0 0. 
After the second update list will be 100 200 100 100 100. 
After the third update list will be 100 200 200 200 100. 
The required answer will be 200.

OR

Explain how the why the bottom solution can work without looping?

#Problem Data Set, my solution times out for the listed data set

10000000 100000
[
 [1400906,9889280,90378],
 [6581237,9872072,87106],
 [4386373,9779851,52422],
 [198648,4373818,5289]
]
# For this problem, variables will look like:
n = 10000000
m = 100000
q = [[1400906,9889280,90378],[6581237,9872072,87106],[4386373,9779851,52422],[198648,4373818,5289]]


def arrayManipulation(n, q)
  arr = Array.new(n,0)
  max = 0
  q.size.times do |i|
    left, right, value = q[i][0],q[i][1],q[i][2]
    left -= 1
    (left...right).each do |j|
      arr[j] += value
      max = arr[j] if max < arr[j]
    end
  end
  return max
end
# this times out on HackerRank, please explain better solution, 
#or why the bottom solution works!

result = arrayManipulation n, queries

Working SOlution on Discussion board

N, M = gets.chomp.split(' ').map(&:to_i)

# create array of zeros of length N + 1
arr = Array.new(N + 1, 0)

M.times do
  # cycle through and get the inputs
  start, finish, value = gets.chomp.split(' ').map(&:to_i)

  # increment value at start of sequence
  arr[start - 1] += value

  # decrement value at first position after sequence
  arr[finish] -= value
end

tmp = 0
max = 0

arr.each do |value|
  # step through summing array
  tmp += value

  # capture the max value of tmp
  max = tmp if max < tmp
end

puts max

Please post the problem itself into the question. Questions should be as independent as possible; additional data or different presentation is welcome on links, but the question should be understandable without them. — Amadan, Jul 02 '18 at 04:17
See this [thread](https://stackoverflow.com/a/55569655/1601309) for run time analysis of this problem. https://stackoverflow.com/a/55569655/1601309 — Kanahaiya, Apr 08 '19 at 09:42

score 4 · Answer 1 · answered Jul 02 '18 at 04:28

Your code is O(m * n) as you have a nested loop to update the array for each entry.

The working code is O(m + n): it never really stores the array, it stores the delta array, the array of changes that makes it possible to reconstruct the array. In your first example, it would store:

0    0    0    0    0   0
+100 0    -100 0    0   0
+100 +100 -100 0    0   -100
+100 +100 0    0   -100 -100

This requires only a loop of m iterations, no nested loops; then you need another loop of n iterations to run through the array, keep running total, and identify the maximum of it.

Ruby Complexity / Time explaination

1 Answers1