Modify group of values between a range

user_11870626 0
Viewed 51

I have a list of index ranges structured as [(2, 4), (6, 7)]. I also have an array with 10 elements with all False values:

[False, False, False, False, False, False, False, False, False, False]

What I wanna do is modify the values between these ranges and make them True. So the final list would be:

[False, True, True, True, False, True, True, False, False, False]

NB: the indexes of the list doesn't start from zero.

I was thinking of a solution based on two for's, but it has a N^2 complexity:

for i in range(len(list_ranges)):
    for j in range(len(my_list)):
        if (j >= list_ranges[i][0] or j <= list_ranges[i][1]):
            my_list[j] = True

How can I improve the complexity of the algorithm?

time-complexity list python performance
1 Answers

You could update only the corresponding slice of list(modifies list in-place, which you're already doing with my_list). List set-slice is an O(K) operation if the count of items being set are equal.

>>> list_ranges = [(2, 4), (6, 7)]
>>> my_list = [False, False, False, False, False, False, False, False, False, False]
>>> list_ranges = [(2, 4), (6, 7)]
>>> for start, end in list_ranges:
...     my_list[start-1:end] = [True] * (end - start + 1)
...
>>> my_list
[False, True, True, True, False, True, True, False, False, False]

Note that this will start intermediate lists in memory and then assign those to the corresponding indices in the original list.

Secondly, if the ranges list is comparatively small, then we could check if the index lies within any of the ranges given.

>>> def solve(indices, my_list):
...     return [any(start <= index <= end for start, end in indices) for index, item in enumerate(my_list, start=1)]
...
>>> my_list = [False, False, False, False, False, False, False, False, False, False]
>>> solve(ranges, my_list)
[False, True, True, True, False, True, True, False, False, False]
user_8468920
Related