Data Structures and Algorithms(DSA) Concept- Subarrays — Part 2.

Topics : Contribution technique, Sliding window approach.

Contribution technique :

This technique can be used to find the sum of all the possible subarrays with a Time complexity of TC : O(N).

Consider an array A =[ 1, 2, 3, 4].

The total sum of all the subarrays is equal to 

1 + (1+2) + (1+2+3) + (1+2+3+4) + 2 + (2+3) + (2+3+4) + 3 + (3+4) + 4



We can see that 1 contributes 4 times to the sum.
2 contributes 6 times to the sum.
3 contributes 6 times to the sum.
4 contributes 4 times to the sum.

Calculating Contribution.

The number of subarrays that include A[i] and start before or at A[i]
A[i] is (𝑖+1).

The number of subarrays that include A[i] and end after or at A[i] is (N−i),
where N is the length of the array.


The total number of subarrays that include 
A[i] is the product of the two counts above: 

(i+1)×(n−i).



for i =0 , the contibution of 1 is (i+1)x(N-i)= 4

for  i= 1 , the contribution of 2 is (i+1)x(N-i)=6
  
for  i= 2, the contribution of 3 is (i+1)x(N-i)=6

for  i= 3, the contribution of 4 is (i+1)x(N-i)=4

W can use this to calculate the total sum of all the subarrays.

public void totalSumOfSubarrays(Int []A){

  int sum =0;
  int N = A.length;

  for (int i =0; i<N; i++){
     int contribution = (i+1)*(N-i);
     sum=sum+(contribution* A[i]);
   }
  
System.out.print(sum);


}

As we can see the complexity is reduced.

TC : O(N)

SC : O(1)

Sliding Window Approach :

Q. Given an array ‘A’ of size ‘N’ . return the max subarray sum of length ‘k’.

public long maxSum(int[] A,int k){

  // first we create the sum of subarray starting at array index 0 and
  // of length k ie till array index k-1
  int N=A.length;
  int window=0;

  for( int i=0; i<k; i++){
    window=window+A[i];
  }

 // Now we can slide the window by removing the element at the start of
 // the window and adding the element which comes after the current window
  int maxSum=window;
  int start=0;
  int end =k;
  
  while(end<N){
    window= window-A[start]+A[end];
    maxSum=Math.max(window,maxSum);
    start++;
    end++;
  }

  return maxSum;
}

Q . Given an array ‘A’ of size ‘N’ and a number ‘B’ Return the minimum number of swaps required to bring all the elements less than or equal to B together.

Eg: 
A =[ 1, 10, 12, 14, 3, 5, 10]
B=8

number of minimum swap is 1, ie A[0] to A[3]

public int minSwap(int[] A,int B){
  
  int N = A.length;
  
  // lets first find the number of elements which are less than or equal to B
  // This will be the window size 
  int slideSize=0;
  for(int i=0;i<N;i++){
    if(A[i]<=B){
      slideSize++;
    }
  }
  // now lets check how many elements inside the window is less or equal to B
  int minSwap= Integer.MAX_VALUE;
  int swap=0;
  for( int i =0;i<slideSize;i++)
  {
    if(A[i]>B){
      swap++;
     }
  }
  minSwap=Math.min(minSwap,swap);
  // Now lets traverse the window and add and remove the swap

  int start= 0;
  int end=slideSize;
  while(end<N){
    
    if(A[start]<=B && A[end]>B){
       swap++;
      }
    else if(A[start]>B && A[end]<=B){
        swap--;
      }
    start++;
    end++;
    minSwap=Math.min(minSwap,swap);

  }


  return minSwap;
}

TC : O(N)

SC : O(1)

In part 3 we will explore more questions based on subarrays and kadane’s algorithm.

Data Structures and Algorithms(DSA) Concept- Subarrays — Part 3.