Click here to Skip to main content
15,794,593 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
I need an efficient algorithm for printing all sub-arrays of an array.
By sub-arrays I mean contiguous subsequences of an array.

What I have tried:

The algorithm available on the web uses three nested for loops with
time complexity O(n^3), which is not at all efficient. Is there a better algorithm which can print all sub-arrays in quadratic or linear time? I l know that time complexity is not determined by the number of loops.
Updated 15-Jun-22 3:07am
Richard Deeming 15-Jun-22 7:44am    
For a single-dimensional array, why would you need more than two loops? (One for the start index, and one for the length.)
Vaibhav Vishal Singh 15-Jun-22 7:50am    
I need all sub-arrays (1<=length of sub-array<=length of array)
CPallini 15-Jun-22 8:01am    
You forgot the loop needed to print the sequence.

1 solution

This implements the algorithm suggested by Richard.
Still, it is O(N^3).
void show_subarrays( int a[], int N)
  for (int l=1; l<=N; ++l)
    int k = 0;
    while ( (k+l) <= N)
      for (int j=0; j<l; ++j)
        cout << a[k+j] << " ";
      cout << "\n";
Share this answer
merano99 15-Jun-22 12:00pm    
Isnt this a for loop?
int k = 0;
while ( (k+l) <= N) { ... k++;}

for(k=0; (k+l) <= N; k++){..}
CPallini 16-Jun-22 2:52am    
Yes, it is.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900