In many problems dealing with an array (or a LinkedList), we are asked to find or calculate something among all the contiguous subarrays (or sublists) of a given size. For example, take a look at this problem:
Given an array, find the average of all contiguous subarrays of size βKβ in it.
Letβs understand this problem with a real input: Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5 Here, we are asked to find the average of all contiguous subarrays of size β5β in the given array. Letβs solve this:
For the first 5 numbers (subarray from index 0-4), the average is: (1+3+2+6-1)/5 => 2.2(1+3+2+6β1)/5=>2.2The average of next 5 numbers (subarray from index 1-5) is: (3+2+6-1+4)/5 => 2.8(3+2+6β1+4)/5=>2.8For the next 5 numbers (subarray from index 2-6), the average is: (2+6-1+4+1)/5 => 2.4(2+6β1+4+1)/5=>2.4
Here is the final output containing the averages of all contiguous subarrays of size 5: Output: [2.2, 2.8, 2.4, 3.6, 2.8]
A brute-force algorithm will calculate the sum of every 5-element contiguous subarray of the given array and divide the sum by β5β to find the average. This is what the algorithm will look like:
importjava.util.Arrays;classAverageOfSubarrayOfSizeK {publicstaticdouble[] findAverages(int K,int[] arr) {double[] result =newdouble[arr.length- K +1];for (int i =0; i <=arr.length- K; i++) {// find sum of next 'K' elementsdouble sum =0;for (int j = i; j < i + K; j++) sum += arr[j]; result[i] = sum / K; // calculate average }return result; }publicstaticvoidmain(String[] args) {double[] result =AverageOfSubarrayOfSizeK.findAverages(5,newint[] { 1,3,2,6,-1,4,1,8,2 });System.out.println("Averages of subarrays of size K: "+Arrays.toString(result)); }}
Time complexity: Since for every element of the input array, we are calculating the sum of its next βKβ elements, the time complexity of the above algorithm will be O(N*K) where βNβ is the number of elements in the input array.
Can we find a better solution? Do you see any inefficiency in the above approach?
The inefficiency is that for any two consecutive subarrays of size β5β, the overlapping part (which will contain four elements) will be evaluated twice. For example, take the above-mentioned input:
As you can see, there are four overlapping elements between the subarray (indexed from 0-4) and the subarray (indexed from 1-5). Can we somehow reuse the sum we have calculated for the overlapping elements?
The efficient way to solve this problem would be to visualize each contiguous subarray as a sliding window of β5β elements. This means that we will slide the window by one element when we move on to the next subarray. To reuse the sum from the previous subarray, we will subtract the element going out of the window and add the element now being included in the sliding window. This will save us from going through the whole subarray to find the sum and, as a result, the algorithm complexity will reduce to O(N).
Here is the algorithm for the Sliding Window approach:
importjava.util.Arrays;classAverageOfSubarrayOfSizeK {publicstaticdouble[] findAverages(int K,int[] arr) {double[] result =newdouble[arr.length- K +1];double windowSum =0;int windowStart =0;for (int windowEnd =0; windowEnd <arr.length; windowEnd++) { windowSum += arr[windowEnd]; // add the next element// slide the window, we don't need to slide if we've not hit the required window size of 'k'if (windowEnd >= K -1) { result[windowStart] = windowSum / K; // calculate the average windowSum -= arr[windowStart]; // subtract the element going out windowStart++; // slide the window ahead } }return result; }publicstaticvoidmain(String[] args) {double[] result =AverageOfSubarrayOfSizeK.findAverages(5,newint[] { 1,3,2,6,-1,4,1,8,2 });System.out.println("Averages of subarrays of size K: "+Arrays.toString(result)); }}
Template to solve some sliding window problem:
publicclassSolution {publicList<Integer> slidingWindowTemplateByHarryChaoyangHe(String s,String t) {//init a collection or int value to save the result according the question.List<Integer> result =newLinkedList<>();if(t.length()>s.length()) return result;//create a hashmap to save the Characters of the target substring.//(K, V) = (Character, Frequence of the Characters)Map<Character,Integer> map =newHashMap<>();for(char c :t.toCharArray()){map.put(c,map.getOrDefault(c,0) +1); }//maintain a counter to check whether match the target string.int counter =map.size();//must be the map size, NOT the string size because the char may be duplicate.//Two Pointers: begin - left pointer of the window; end - right pointer of the windowint begin =0, end =0;//the length of the substring which match the target string.int len =Integer.MAX_VALUE; //loop at the begining of the source stringwhile(end <s.length()){char c =s.charAt(end);//get a characterif( map.containsKey(c) ){map.put(c,map.get(c)-1);// plus or minus oneif(map.get(c) ==0) counter--;//modify the counter according the requirement(different condition). } end++;//increase begin pointer to make it invalid/valid againwhile(counter ==0/* counter condition. different question may have different condition */){char tempc =s.charAt(begin);//***be careful here: choose the char at begin pointer, NOT the end pointerif(map.containsKey(tempc)){map.put(tempc,map.get(tempc) +1);//plus or minus oneif(map.get(tempc) >0) counter++;//modify the counter according the requirement(different condition). }/* save / update(min/max) the result if find a target*/// result collections or result int value begin++; } }return result; }}