Sliding Window & Two Pointer

Sliding Window maintains a window over data and slides it to find optimal subarrays/substrings. Two types: fixed-size (window always size K) and variable-size (expand/shrink based on condition). Two Pointer uses two indices moving towards each other or in the same direction. Both avoid nested loops, reducing O(n²) to O(n).

Key Concepts

Deep Dive: Fixed-Size Sliding Window

Maximum sum subarray of size K:

public int maxSumSubarray(int[] nums, int k) {
    int windowSum = 0, maxSum = 0;
    for (int i = 0; i < nums.length; i++) {
        windowSum += nums[i];
        if (i >= k) windowSum -= nums[i - k];  // Shrink from left
        if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Deep Dive: Variable-Size Sliding Window

Longest substring without repeating characters:

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int maxLen = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c)) {
            left = Math.max(left, lastSeen.get(c) + 1);
        }
        lastSeen.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Minimum window substring:

public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    int left = 0, minStart = 0, minLen = Integer.MAX_VALUE, matched = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            need.merge(c, -1, Integer::sum);
            if (need.get(c) >= 0) matched++;
        }
        while (matched == t.length()) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            char leftChar = s.charAt(left++);
            if (need.containsKey(leftChar)) {
                need.merge(leftChar, 1, Integer::sum);
                if (need.get(leftChar) > 0) matched--;
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

Deep Dive: Two Pointer Patterns

Container With Most Water:

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1, max = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        max = Math.max(max, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return max;
}

3Sum:

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;  // Skip duplicates
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(List.of(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left+1]) left++;
                while (left < right && nums[right] == nums[right-1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return result;
}

Common Interview Questions

• Longest Substring Without Repeating Characters
• Minimum Window Substring
• Sliding Window Maximum
• Maximum Sum Subarray of Size K
• Container With Most Water
• 3Sum
• Trapping Rain Water
• Longest Repeating Character Replacement
• Permutation in String
• Fruit Into Baskets