Print all subarrays of an array in linear time, ie. O(n) in java

In this blog, I am going to write a code which will print all the sub-arrays of an array in linear time, i.e O(n).

First, we should to try to understand the problem we are trying to solve here.

We have an array of integers. {1, 2, 3, 4, 5}

and we need to print the elements of this array in a fashion, which looks something like this.

1
1, 2
1, 2, 3
1, 2, 3, 4
1, 2, 3, 4, 5

2,
2, 3
2, 3, 4
2, 3, 4, 5

As, per the output printed above, we can say that we need to decrease the size of the array, after the array has been printed till the last element of the array.
Or, in other way we can say that we will shift the startIndex of array towards the endIndex of the array.

So, we will have a startIndex, to keep track of start current iteration of the array.

As, we keep changing the last index of the array, that we are printing. So, we need to have one variable to keep track of the end of the array in each iteration.
So, we will have currentIterationEndIndex.

We need to keep track of number of times the loop is going to run. In an array of 5 elements it will run (5 + 4 + 3 + 2 + 1 = 16) times.
We will store that value in totalLoopCount.

And, we will have one variable to iterate over the array elements.
The currentIndex  will work as a variable which is used in printing the element in the array. It is like i or j variables used in any loop for iteration. This is the exact purpose of this array.

My first function, that I am going to write will provide total number of loops.

static int loopCount(int intValue){
    int sum = 0;

    while(intValue > 0) sum += intValue--;

    return sum;
}

Now, I am going to declare the variables that we are going to use.

final int arrLength = intArray.length;

int startIndex   = 0;
int currentIndex     = startIndex;

int currentIterationEndIndex = startIndex;
int totalLoopCount = loopCount(arrLength);

Now, I am writing the loop, which prints the sub-arrays.

while(totalLoopCount > 0){

    System.out.printf("%d ", intArray[currentIndex]);

    if(currentIndex == currentIterationEndIndex){

        ++currentIterationEndIndex;

        if(currentIterationEndIndex == arrLength){
            ++startIndex;
            currentIterationEndIndex = startIndex;
        }

        currentIndex = startIndex;
        --totalLoopCount;

        System.out.println();
    } else {
        ++currentIndex;
    }
}

while(totalLoopCount > 0)  is the code, which runs the code inside the loop totalLoopCount number of times.

In the if-block, I am checking for the end of current iteration. Have we reached the end of current iteration, yet??
If we have then it is time to increase the value of currentIterationEndIndex, we move the end index to the next index. As, in the next loop we have to cover one more element.

Then there is another if-block inside it, to check if we have reached the end of the current array.
If we have reached the end of current array then we need to shift the start index of the array for next iteration, we do it be incrementing the value of startIndex.

The else-block, executes when we have not reached the end of the array.

Time Complexity :

What is the time complexity of this solution?

let us calculate how many times an integer is printed or used or accessed in entire process.

Let us suppose n = 5

1 : 5 times

2 : 8 times

3 : 9 times

4 : 8 times

5 : 5 times

to calculate the number of times one element is printed, we can say that we multiply the position x of an element in the array, where position starts from 1, by the number of elements in the array starting from that position.

So, in the case of position 1, the number of elements are 1 * 5 = 5                           i.e (1 * n)
for position 2, the number of elements are                        2 * 4  = 8                         i.e  (2 * (n – 1))
for position 3, the number of elements are                        3 * 3 = 9                          i.e   (3 (n – 2))

and like that we can calculate the count for every position.

So, we can see that number of times each element has been accessed is equivalent to a constant value multiplied by a value, and that value depends on n.
We have to keep in the mind that it does not depend on square of n.

So, the time complexity of this solution is O(n).

Complete  Source Code

public class PrintSubArrays {

    static int loopCount(int intValue){
        int sum = 0;

        while(intValue > 0) sum += intValue--;

        return sum;
    }
    
    static void print(final int[] intArray){

        final int arrLength = intArray.length;

        int startIndex   = 0;
        int currentIndex     = startIndex;

        int currentIterationEndIndex = startIndex;
        int totalLoopCount = loopCount(arrLength);

        while(totalLoopCount > 0){

            System.out.printf("%d ", intArray[currentIndex]);

            if(currentIndex == currentIterationEndIndex){

                ++currentIterationEndIndex;

                if(currentIterationEndIndex == arrLength){
                    ++startIndex;
                    currentIterationEndIndex = startIndex;
                }

                currentIndex = startIndex;
                --totalLoopCount;

                System.out.println();
            } else {
                ++currentIndex;
            }
        }
    }

    public static void main(String[] args) {
        final int[] arr = {1, 2, 3, 4, 5};
        print(arr);
    }
}