Sliding Window & Two Pointers

1. The Sliding Window Technique

The Sliding Window technique is used for problems that involve finding a subarray or substring that satisfies a certain condition. Instead of re-calculating from scratch for every possible subarray, we cleverly slide a "window" over the data, adding an element at one end and removing an element at the other.

public class MaxSumSubarray {
    public static int findMaxSumSubarray(int[] arr, int k) {
        if (arr.length < k) { return -1; }
        int maxSum = 0, windowSum = 0, windowStart = 0;
        for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            windowSum += arr[windowEnd];
            if (windowEnd >= k - 1) {
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= arr[windowStart];
                windowStart++;
            }
        }
        return maxSum;
    }
}
            

public class MinSwaps {
    public static int minSwaps(int[] arr, int k) {
        int windowSize = 0;
        for (int val : arr) { if (val <= k) windowSize++; }
        int badCount = 0;
        for (int i = 0; i < windowSize; i++) { if (arr[i] > k) badCount++; }
        int minSwaps = badCount;
        for (int i = windowSize; i < arr.length; i++) {
            if (arr[i - windowSize] > k) badCount--;
            if (arr[i] > k) badCount++;
            minSwaps = Math.min(minSwaps, badCount);
        }
        return minSwaps;
    }
}
            

public class LongestSubarrayWithSumK {
    public static int findLength(int[] arr, int k) {
        int windowStart = 0, windowSum = 0, maxLength = 0;
        for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            windowSum += arr[windowEnd];
            while (windowSum > k) {
                windowSum -= arr[windowStart];
                windowStart++;
            }
            if (windowSum == k) {
                maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
            }
        }
        return maxLength;
    }
}
            

2. The Two Pointer Technique

The Two Pointer technique is related to the Sliding Window. It involves using two pointers to iterate through a data structure. The pointers can move in different ways, such as from opposite ends towards each other or in the same direction at different speeds.

public class PairWithTargetSum {
    public static boolean hasPair(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int currentSum = arr[left] + arr[right];
            if (currentSum == target) return true;
            else if (currentSum < target) left++;
            else right--;
        }
        return false;
    }
}
            

public class RemoveDuplicates {
    public static int remove(int[] arr) {
        if (arr.length == 0) return 0;
        int nextNonDuplicate = 1; // Slow pointer
        for (int i = 1; i < arr.length; i++) { // Fast pointer
            if (arr[nextNonDuplicate - 1] != arr[i]) {
                arr[nextNonDuplicate] = arr[i];
                nextNonDuplicate++;
            }
        }
        return nextNonDuplicate;
    }
}