CODEWITHSUNDEEP
javaalgorithm
Rurien
Rurien

Reputation: 369

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

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).

Upvotes: 0

Views: 1852

Answers (2)

Rhett Harrison
Rhett Harrison

Reputation: 432

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

Upvotes: 1

Louis Wasserman
Louis Wasserman

Reputation: 198053

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).

Upvotes: 4

Related Questions