02. Sliding Window Technique

Sliding Window Technique

The sliding window technique is an efficient way to solve problems involving subarrays or substrings of a given size within an array or string. It is particularly useful for problems that involve finding a subset of contiguous elements that meet a specific condition.

Key Concepts

1. Window: A subarray or substring that represents a portion of the original array or string.
2. Fixed or Variable Size: The window can be of a fixed size (static) or can change size dynamically (dynamic).
3. Sliding: The window slides over the array or string by moving its starting and ending indices to cover all possible positions.

Steps

1. Initialize: Start with a window at the beginning of the array or string.
2. Expand/Contract: Move the window by adjusting its starting and ending indices.
3. Update: Calculate the desired value or check conditions for the current window.
4. Slide: Move the window one step forward and repeat the process until the end of the array or string is reached.

Examples Covered:

By understanding and applying the sliding window technique, you can significantly improve the efficiency of algorithms for problems involving contiguous data segments.

Advantages of Sliding Window Technique

• Efficiency: Reduces the time complexity from (O(n^2)) to (O(n)) for many problems by avoiding unnecessary repeated calculations.
• Simplicity: Provides a straightforward approach to handle problems involving contiguous subarrays or substrings.
• Flexibility: Can be adapted to both fixed-size and variable-size window problems.

Applications

1. Fixed-Size Window:
   • Maximum sum of a subarray of size k.
   • Finding the average of each subarray of size k.
2. Variable-Size Window:
   • Longest substring with at most k distinct characters.
   • Smallest subarray with a sum greater than or equal to S.
3. Max Consecutive Ones III
   • Finding the longest subarray with at most k zeroes.
4. Longest Substring Without Repeating Characters
   • Finding the longest substring without repeating characters.
5. Find K Closest Elements
   • Finding the k closest elements to a given value in a sorted array.

Examples

Example 1: Maximum Sum of Subarray of Size K

Problem: Given an array of integers and a number k, find the maximum sum of a subarray of size k.

Code:

def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return -1

    max_sum = 0
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(n - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 3
print(max_sum_subarray(arr, k))  # Output: 27 (sum of subarray [8, 9, 10])

Explanation:

1. Initialize: Calculate the sum of the first window of size k.
2. Expand/Contract: Slide the window by removing the first element of the previous window and adding the next element in the array.
3. Update: Keep track of the maximum sum encountered.
4. Slide: Repeat the process until the end of the array is reached.

Example 2: Longest Substring with K Unique Characters

Problem: Given a string and an integer k, find the length of the longest substring that contains exactly k unique characters.

Code:

def longest_substring_k_unique(s, k):
    from collections import defaultdict

    n = len(s)
    if n == 0 or k == 0:
        return 0

    left = 0
    max_length = 0
    char_count = defaultdict(int)

    for right in range(n):
        char_count[s[right]] += 1

        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

        if len(char_count) == k:
            max_length = max(max_length, right - left + 1)

    return max_length

# Example usage:
s = "araaci"
k = 2
print(longest_substring_k_unique(s, k))  # Output: 4 ("araa")

Explanation:

1. Initialize: Use two pointers (left and right) to represent the window bounds and a dictionary to count character frequencies.
2. Expand/Contract: Expand the window by moving the right pointer and adding the new character to the count. Contract the window by moving the left pointer and updating the count when the number of unique characters exceeds k.
3. Update: Update the maximum length of the window that meets the condition.
4. Slide: Continue expanding and contracting the window until the end of the string is reached.

---

1004. Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/description/?envType=company&envId=facebook&favoriteSlug=facebook-three-months

Approach

The problem requires finding the maximum number of consecutive 1s when flipping at most one 0 in the binary array. This can be solved using the sliding window (two-pointer) approach.

Key Steps:

1. Initialize:
   • Maintain two pointers, left and right, representing the sliding window.
   • Keep a count of the number of zeros in the current window (zero_count), since you can flip only one 0.
   • Initialize max_len to store the maximum length of consecutive 1s after flipping at most one 0.
2. Expand Window:
   • Traverse the array using the right pointer.
   • Every time you encounter a 0, increment the zero_count because you can flip only one 0.
3. Shrink Window:
   • If the zero_count exceeds 1 (meaning you have encountered more than one 0), move the left pointer forward until zero_count is reduced to 1 again. This maintains the validity of having at most one 0 in the current window.
4. Continue & Update:
   • At each step, update max_len with the length of the current window (calculated as right - left + 1) if the zero_count is within the limit of one flip.

Python Code:

def findMaxConsecutiveOnes(nums):
    left = 0
    zero_count = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        # If there are more than one 0, shrink the window from the left
        while zero_count > 1:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        # Update the maximum length of the window
        max_len = max(max_len, right - left + 1)

    return max_len

Explanation:

1. Initialize:
   • left = 0: Marks the beginning of the window.
   • zero_count = 0: Counts the number of zeros in the current window.
   • max_len = 0: Stores the maximum consecutive 1s after flipping one 0.
2. Expand Window:
   • Traverse the array with right pointer. If the current element is 0, increment zero_count.
3. Shrink Window:
   • If zero_count > 1, increment the left pointer to shrink the window from the left, ensuring at most one 0 remains in the window.
4. Continue & Update:
   • For each valid window (with at most one 0), calculate the length (right - left + 1) and update max_len.

Test Cases:

1. Example 1:
   • Input: nums = [1, 0, 1, 1, 0]
   • Output: 4
   • Explanation: Flipping the first 0 results in [1, 1, 1, 1, 0], which gives 4 consecutive ones.
2. Example 2:
   • Input: nums = [1, 0, 1, 1, 0, 1]
   • Output: 4
   • Explanation: Flipping either 0 results in a maximum of 4 consecutive ones.
3. Edge Case:
   • Input: nums = [1, 1, 1, 1]
   • Output: 4
   • Explanation: No flip is needed, as there are already 4 consecutive ones.
4. Edge Case 2:
   • Input: nums = [0, 0, 0]
   • Output: 1
   • Explanation: The maximum number of consecutive ones after flipping one 0 is just 1.

This sliding window approach ensures an optimal solution with a time complexity of O(n), where n is the length of the array, because each element is processed at most twice (once by right and once by left).

---

3. Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest substring without repeating characters.

Approach:

• Use a sliding window to maintain the longest substring without repeating characters.

Optimized Python Code:

def lengthOfLongestSubstring(s):
    char_map = {}
    left = 0
    max_len = 0

    for right, char in enumerate(s):
        if char in char_map:
            left = max(left, char_map[char] + 1)
        char_map[char] = right
        max_len = max(max_len, right - left + 1)

    return max_len

Explanation of the Optimized Approach:

1. Initialize:
   • char_map = {}: Stores the most recent index of each character.
   • left = 0: Points to the start of the current valid window.
   • max_len = 0: Tracks the length of the longest substring without repeating characters.
2. Expand Window:
   • The right pointer iterates through the string (for right, char in enumerate(s)).
   • For each character char, check if it has been seen before. If so, adjust left to the right of the previous occurrence (left = max(left, char_map[char] + 1)). This ensures that left only moves forward, preventing it from moving backward.
3. Update:
   • Store the current index of the character in char_map.
   • Calculate the length of the current window and update max_len if necessary.

Key Differences from Previous Code:

1. Simplified Condition: The check for updating the left pointer is done with max(left, char_map[char] + 1) to ensure it only moves forward.
2. Conciseness: The code is more compact by combining variable assignment and calculations in one step, using the enumerate() function for iteration.
3. Efficiency: Fewer condition checks and shorter logic, making the code both easy to understand and efficient.

Example:

• Input: s = "abcabcbb"
• Output: 3

Test Cases:

1. Example 1: s = "abcabcbb", Output: 3
2. Example 2: s = "bbbbb", Output: 1
3. Example 3: s = "pwwkew", Output: 3
4. Edge Case 1: s = "", Output: 0
5. Edge Case 2: s = "a", Output: 1

This solution runs in O(n) time complexity, where n is the length of the input string, and is more concise than the earlier version.

---

658. Find K Closest Elements

Problem: Given a sorted array arr, two integers k and x, find the k closest elements to x in the array.

Approach:

• Use a sliding window to find the closest k elements to x.

Approach

To solve the problem of finding the k closest elements to x in a sorted array arr, a common approach is to utilize binary search and the two-pointer technique. This ensures an optimal time complexity given that the array is already sorted.

Key Steps:

1. Binary Search for the Closest Element:
   • We use binary search to find the position in the array where the element is closest to x. This helps us narrow down the window of elements to explore.
2. Two-Pointer Technique:
   • Once we have a starting point, we can expand outwards using two pointers (left and right). These pointers will help us find the k closest elements to x by comparing differences |arr[left] - x| and |arr[right] - x|.
3. Sorting the Result:
   • After selecting the k closest elements, we return them in sorted order as required by the problem.

Optimized Python Code:

def findClosestElements(arr, k, x):
    left, right = 0, len(arr) - 1

    # Narrow the window to k elements
    while right - left >= k:
        if abs(arr[left] - x) > abs(arr[right] - x):
            left += 1
        else:
            right -= 1

    # Return the k closest elements sorted in ascending order
    return arr[left:left + k]

Explanation:

1. Binary Search-Like Narrowing:
   • Initially, left is set to the start of the array, and right is set to the end.
   • The while loop continues narrowing the window until only k elements remain. In each iteration, we compare the absolute difference between arr[left] and x with arr[right] and x. We discard the element that is farther from x by adjusting the left or right pointer.
2. Return the Result:
   • Once the loop finishes, the left pointer will point to the start of the k closest elements, so we return the subarray arr[left:left + k].

Example 1:

• Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
• Output: [1, 2, 3, 4]
  • Explanation: The 4 closest numbers to 3 are [1, 2, 3, 4].

Example 2:

• Input: arr = [1, 1, 2, 3, 4, 5], k = 4, x = -1
• Output: [1, 1, 2, 3]
  • Explanation: The 4 closest numbers to -1 are [1, 1, 2, 3].

Test Cases:

1. Example 1:
   • Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
   • Output: [1, 2, 3, 4]
2. Example 2:
   • Input: arr = [1, 1, 2, 3, 4, 5], k = 4, x = -1
   • Output: [1, 1, 2, 3]
3. Edge Case 1:
   • Input: arr = [1, 2, 3, 4], k = 2, x = 5
   • Output: [3, 4]
   • Explanation: Since x = 5, the closest numbers are the two largest numbers in the array, 3 and 4.
4. Edge Case 2:
   • Input: arr = [1], k = 1, x = 0
   • Output: [1]
   • Explanation: The array only contains one element.

Time Complexity:

• Time complexity: O(log(n) + k). The binary search-like narrowing runs in O(log(n)), and selecting the k closest elements runs in O(k).
• Space complexity: O(k) for the output result.