CODEWITHSUNDEEP
arraysalgorithm
Rahul Rathore
Rahul Rathore

Reputation: 49

Find all contiguous subarrays of array in O(n) complexity

I am stuck on finding a solution for finding all the contiguous subarrays of a given array in minimum time complexity O(n).

For example:

[1,2,3,4]

Subarrays are:

[1][2][3][4][1,2][2,3][3,4][1,2,3][2,3,4][1,2,3,4]

I have done it with time complexity O(n^2) but for the large inputs taking lot of time and memory.

Are there any specific algorithms for this problem?

Upvotes: 2

Views: 4884

Answers (1)

user1196549
user1196549

Reputation:

There are exactly n(n+1)/2 subarrays, which can be written as A[i..j] for all i and and all j≥i. The algorithm to generate all pairs is immediate (double loop) and cannot be improved.

If you just need to output the pairs (i, j), space O(1) suffices. If you need to store all pairs, O(n²). And if you need to store all subarrays in full, O(n³); in this case, the time also unavoidably grows to O(n³) and there is another nested loop.

Update:

This answer does not take int account the constraint "the sum of those individual subarray results in perfect square root" in the comments, which was added after the fact and cannot be considered part of the question.

Upvotes: 4

Related Questions