Sliding Window Problems

Find Subarray with given sum

Problem Statement : Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

As it is said one picture is better than thousands words, so I tried to define sliding window algorithm by image instead of explaining in words.

In short,

1. We take a window of size 0 where window’s left point and window’s right point are both at 0. [l=0,r=0]
2. Initialize current sum by assign array 0th index (l=0 OR r =0)value [currentSum = arr[r]]
3. Start loop and compare the current sum and target sum.
4. If current sum is less than target sum, means we need to stretch window to right side, increment r [r++] and add value in current sum.
   [currentSum = currentSum + arr[r]]
5. If current sum is greater than target sum, mean we need to shrink the window from left side, so subtract the value of l index from current sum [currentSum = currentSum — arr[l]] and increment l [l++]
6. If current sum is equal to target sum, we got the sub array , print the l and r and break the loop.

public class SubArrayOfGivenSum {

   public static void main(String[] args) {
      int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
      int sum = 23;
      solve(arr,sum);
   }

   private static void solve(int[] arr, int targetSum) {
      int l = 0;
      int r = 0;
      int currentSum = arr[r];

      for(int i =0;i<arr.length;i++){
         if(currentSum < targetSum){
            r++;
            currentSum += arr[r];
         }else if(currentSum > targetSum){
            currentSum = currentSum - arr[l];
            l++;
         }else {
            System.out.println("Subarray found between : "+ l+" "+r);
            break;
         }
      }

   }
}

Thanks for reading. Keep reading and smiling.

Drop your comments if you have any questions. Your questions are my motivation.