Adding a value to a range of values in an array in Python without using a for loop-CodePudding

I'm trying to learn Python and I have run into a problem.

I am attempting to complete the Array Manipulation challenge on hackerrank.

A part of solving it requires me to add a number to a range of values in an array multiple times.

So far I have been able to come up with this:

def arrayManipulation(n, queries):
 x = [0]*n
 for i in range(len(queries)): 
    for i2 in range(queries[i][0], queries[i][1] 1):
        x[i2-1] = queries[i][2]         
 return max(x)

But I'm not able to solve 7 of the test cases due to timeout, and I'm guessing I am missing something that would allow me to solve this without the 2nd for loop. Any ideas?

CodePudding user response：

For a very large n, building an actual list/array of n is likely to be inefficient and unnecessary. Consider the input:

n = 1000
queries = [
    [100, 500, 3],
    [400, 800, 7],
    [600, 900, 1],
]

You don't have 1000 unique values, you really just have 7 chunks:

range(0, 100)
range(100, 400)
range(400, 500)
range(500, 600)
range(600, 800)
range(800, 900)
range(900, 1000)

Each query will map to some subset of these chunks; no query will apply to only part of a chunk. Consequently, you can compute the effect of each query in its entirety without ever having to iterate over the full range of n, or having to iterate over range(a, b 1) at all.

Actually implementing this as a solution is left as an exercise to the reader, but this is the algorithmic route I'd pursue if you're timing out on very large n values. (Note that this is not an easy coding problem, and is probably not suitable if you're just starting out!)

CodePudding user response：

You can use map(), should be more efficient. Look here as a ref.:

https://python-reference.readthedocs.io/en/latest/docs/functions/map.html