How can I get all subarrays of a given array faster than O(N^2)?-CodePudding

I'm trying to print all subarrays of given array like below.

given array : [5,3,2,4,1]
subarray : [
    [5],
    [5,3],
    [5,3,2],
    [5,3,2,4],
    [5,3,2,4,1],
    [3],
    [3,2],
    [3,2,4],
    [3,2,4,1],
    [2],
    [2,4],
    [2,4,1],
    [4],
    [4,1],
    [1]
]

I can print it with nested loops.

But I want to know how to implement it with O(N) or O(2^N).

CodePudding user response：

There are O(n^2) subarrays of an array in the first place.

Printing them -- no matter how you generate them -- will always take at least O(n^2); you're always printing at least O(n^2) lines, each of which will take at least O(1).

Finally, since anything O(n^2) is also O(2^n), you already have an algorithm that will work in O(2^n).

CodePudding user response：

It would not be possible to access each element in less than O(N^2) since you need to access each element in order to print it. You may consider flattening the array and then printing the array would only be O(N) because now it is just one array. However, this flattening would take greater than O(N).

Your best option is to use a double for-loop implementation

for(List<T> i : itemArray) {
    for(T j : i) {
       System.out.println(j);
    }
}

Something along these lines to print out your subarrays