Sliding Window Algorithm

  • Keep computing result window by window.
  • Need something to compare with like for finding largest sum of sub array problem, first consider the sum of k elements to start comparing with.
  • The second pointer in this problem is starting from k in the first loop itself. In case there are constraints like the matching sub string needs to be at-least 3 char long that can be used as initial value of k
	// Javascript code for
	// O(n) solution for finding
	// maximum sum of a subarray
	// of size k
	function maxSum(arr, n, k) {
		let max = 0;
		let sum = 0;
		// find initial sum of first k elements
		for (let i = 0; i < k; i++) {
			sum += arr[i];
			max = sum;
		}
		// iterate the array once
		// and increment the right edge
		for (let i = k; i < n; i++) {
			sum += arr[i] - arr[i - k];
			
			// compare if sum is more than max,
			// if yes then replace
			// max with new sum value
			if (sum > max) {
				max = sum;
			}
		}
		return max;
	}
 
// Driver code
let arr = [1, 4, 2, 10, 2, 3, 1, 0, 20];
let k = 4;
let n = arr.length;
console.log(maxSum(arr, n, k));