Topics : Subarrays, Brute Force approach in subarrays, prefix sum approach in subarrays and carry forward approach in subarrays.
What is a subarray ?
A subarray is a contiguous part of array, i.e., Subarray is an array that is inside another array.
- An single element is also a Subarray.
- Complete array is also a Subarray.
- Order of elements have to be the same as the original array.
Example :
A=[4, 1, 2, 3, -1, 6, 9, 8, 12]
IN THE ARRAY A :
4,6 not a subarray
1,2 is a subarray
4,1,2,3,6. not a subarray
1,4. not a subarray
4 is a subarray
3,2,-1 not a subarray
How to count the number of subarrays in a array of size N ?
The count of subarrays are calculated by changing the start value and
counting the number of subarrays possible.
s=0 s=1 s=2.............. s=N-1
N N-1 N-2 1 subarray
subarray
Total subarrays : N+ (N+1) + (N+2) +....+3+2+1
: N(N+1)/2
Given an array A of size N . Print all subarrays ( every subarray in a new line).
public void printAllSubarrays(int[] A){
// s=> start
// e=> end
int N = A.length;
for( int s=0; s<N,s++){
for ( int e=s;e<N;e++){
for(int i=s;i<=e;i++){
System.out.print(A[i]);
System.out.println();
}
}
}
// TC : O(N^3)
}Given an array A of size N. find sum of all the subarrays (Print sum of every subarray in a new line.)
We will approach this question using three methods and understand how each method impacts the time and space complexity.
- Brute Force method.
public void printSum(int[] A){
for( int s=0; s<N,s++){
for ( int e=s;e<N;e++){
int sum=0;
for(int i=s;i<=e;i++){
sum=sum+A[i];
System.out.print(sum);
}
System.out.println();
}
}
}In the brute force method the time complexity(TC) is 0(N³) and has a space complexity of 0(1).
lets try the to bring the time complexity down.
2. Prefix Sum method.
public void printSum(int[] A){
// Build a prefix sum;
int N = A.length;
long PS[]= new long[N];
PS[0]= A[0];
for(int i=1;i<N;i++){
PS[i]=A[i]+PS[i-1];
}
// Get the sum of subarrays
for( int s=0;s<N;s++){
for(int e=s;e<N;e++){
if(s==0){
System.out.print(PS[e]);
}else{
System.out.print(PS[e]-PS[s-1]);
}
System.out.println();
}
}
}In the prefix sum approach we have reduced the time complexity to
TC: O (N²), but the space complexity has increased to SC : O(N).
3. Carry Forward approach.
public void printAllSubSum(int A[]){
int N=A.length;
for (int s=0;s<N;s++){
int sum=0;
for(int i=s;i<N;i++){
sum=sum+A[i];
System.out.print(sum);
System.out.print.ln();
}
}
}Here We are able to bring down the space complexity too.
TC : O(N²),
SC :O(N³)
In part 2 We will explore contribution technique and sliding window technique in subarrays .
