Python code with nested for loops is too slow

I am doing a problem from HackerRank. This problem defines a zero array of size n at the beginning and then does operations on it. So let's say that array is x = [0, 0, 0, 0, 0, 0]. So n = 6 here. Now consider the operation (they call it query in the problem) [1, 2, 5]. This means that in the array x, add 5 from index 0 to 1. So x now becomes x = [5, 5, 0, 0, 0, 0]. And there could be many such operations(queries). At the end, we just need to find the max element of the final array x. So sample input is

HackerRank

x = [0, 0, 0, 0, 0, 0]

n = 6

[1, 2, 5]

x

x

x = [5, 5, 0, 0, 0, 0]

x

5 3
1 2 100
2 5 100
3 4 100


So we need to have array x of size 5 (initialized to zeros) and there are 3 queries to run on it. If we go through the queries, we find that the max element in the final array is 200. I have done code using nested for loop here. Outer for loop runs through the queries and inner for loop manipulates the array x.
For small values of array size of x, my code works good. But when n = 1000000 and number of queries, m = 100000, the nested for loops runs forever (It acts like an infinite loop). I want to know how can I make this faster.
Following is the nested for loop

x

x

x

n = 1000000

m = 100000

# Construct a zero list of length n
worklist = list([0]*n)
# Loop through the queries
for query in queries:
# Since the problem defines the queries vector
# as one based index, we need to modify the
# indices of query
index0, index1 = query[0]-1, query[1]-1
# Now construct the new list with addition
for i in range(index0, index1+1):
worklist[i] = worklist[i] + query[2]


I think I need to modify my algorithm for doing this. Suggestions welcome.

2 Answers
2

My answer addresses only the algorithmic part of your question, I'm going to simplify i/o and not to implement it as a function, to leave something on which to test your skills.

The idea is, don't store the result but the cumulative delta for each position and, afterwards, find the maximum with a cumulative summation.

Let' s see the first example reported in the statement of the problem,

10 3
1 5 3
4 8 7
6 9 1


We start with l, a list of zeros with length equal to n+1 (why n+1? because we need a little extra space to store a delta when b==n); we want to store in l just the delta's

l

n+1

n+

b==n

l

n, m = 10, 3
l = [0]*(n+1)


We repeat the same ops for the 3 queries and report the state of our list l in a comment

l

a, b, k = 1, 5, 3
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 0, 0, -3, 0, 0, 0, 0, 0]

a, b, k = 4, 8, 7
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 7, 0, -3, 0, 0, -7, 0, 0]

a, b, k = 6, 9, 1
l[a-1] += k ; l[b] -= k
# [0, 0, 3, 7, 1, -3, 0, 0, -7, -1, 0]

current_max = 0
current_sum = 0
debug = 1
for num in l[:-1]:
current_sum += num
if debug: print(current_sum)
current_max = max(current_max, current_sum)

print(current_max)


Executing the above code gives me

3
3
3
10
10
8
8
8
1
0
10


The first ten numbers are the elements of the summed list, to be compared with the problem statement, and the last number is the required maximum value

In the Discussions page of this problem, there is a O(n) solution there,
It's the problem about overlap.

The basic thinking is, you just need to mark "add" point and "remove" point in the array, so the final stage you only need to go though the array once and keep "current sum" in current index and you can record the max one for answer.

For example
5 3

1 2 100

2 5 100

3 4 100

your array will simplify to be

0, 0, 0, 0, 0, 0

when take first input record (1 2 100):

100, 0, -100, 0, 0, 0

this means when you doing final scan sum summary, your loop will calculate in step

index 0, sum 100

index 1, sum 100

index 2, sum 0

index 3, sum 0
...

when take second input record (2 5 100):

100, 100, -100, 0, 0, -100

this means when you doing final scan sum summary, your loop will calculate in step

index 0, sum 100

index 1, sum 200

index 2, sum 100

index 3, sum 100

index 4, sum 100

index 5, sum 0

so the max is happend at index 1,

when take second input record (3 4 100):

100, 100, 0, 0, -100, -100

this means when you doing final scan sum summary, your loop will calculate in step

index 0, sum 100

index 1, sum 200

index 2, sum 200

index 3, sum 200

index 4, sum 100

index 5, sum 0

so the max is happend at index 1,

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy