CODEWITHSUNDEEP
pythonpython-3.x
Mahir Islam
Mahir Islam

Reputation: 1972

How to find sub-arrays of a list in a more faster way in Python3?

This is my code:

A = list(map(int, input().rstrip().split()))
sub = [A[i:i+j] for i in range(0,len(A)) for j in range(1,len(A)-i+1)]
print(sub)

I would like to know if there is a way of finding sub-arrays faster than mine. The number of inputs in the list, 'A', can be from 1 to 10**5, while the values that are inputted can be from 1 to 10**9

EDIT:

A few samples of input data:

[1,0,3,0,4]

[1,10,10]

[2,6,13,4,3,2]

Note:This are just small samples, not really big ones

Upvotes: 4

Views: 111

Answers (1)

Blckknght
Blckknght

Reputation: 104722

If you don't need to have all the results exist at once (e.g. you just need to print each one, then you can forget about it), you can speed your code up from O(N**3) to O(N**2), simply by reusing the same lists, rather than slicing them anew on each iteration:

def print_subsequences(A):
    for i in range(len(A)):
        result = []
        for j in range(i,len(A)):
            result.append(A[j]
            print(result)

Example output:

>>> print_subsequences([1,2,3,4])
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[2]
[2, 3]
[2, 3, 4]
[3]
[3, 4]
[4]

You could also make the function a generator, yielding results instead of printing them. But that is a little perilous, as the lists that would be yielded are not all independent of each other. If the consumer tried to save the [2] list from the example output, they'd find that it got changed after the next iteration to contain [2,3], and further changed to [2,3,4] after the iteration after that. That could be a rather unpleasant surprise if they still needed the bare [2] list. You'd want to document the generator very clearly if you were going that route.

Upvotes: 1

Related Questions