Day 12 – Sliding Window

Master fixed and variable window techniques with real interview problems.
Learn to efficiently solve array and string problems with optimal time complexity.

Fixed Window Variable Window At Most K Distinct Frequency Map Expand/Contract

Instructions for Candidates

Read Specifications Carefully: Pay attention to Input/Output formats and Constraints
Submit Function Only: Implement the required function, not a full program
Complexity Expectations: Most problems expect O(n) time complexity
Common Pitfalls: Watch for off-by-one errors when shrinking windows, remember to clear zero-count keys from frequency maps
Testing: Examples are illustrative; hidden test cases exist with edge cases
Window Patterns: Fixed window (maintain size), Variable window (expand/contract based on condition)

1. Max Sum Subarray of Size K

Easy

Fixed Array Sum

▼

Problem Statement

Given an array of integers and an integer k, return the maximum sum of any contiguous subarray of size k.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def max_sum_subarray(nums, k):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function maxSumSubarray(nums, k) {
    // TODO
}
export { maxSumSubarray };

Input/Output Format

Input: Array nums of integers, integer k

Output: Integer representing the maximum sum

Constraints

1 ≤ k ≤ n ≤ 200,000
-10,000 ≤ nums[i] ≤ 10,000

Examples

Example 1:
Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Window [5, 1, 3] has maximum sum of 9

Example 2:
Input: nums = [2, 3, 4, 1, 5], k = 2
Output: 7
Explanation: Window [3, 4] has maximum sum of 7

Edge Cases

All negative numbers
k equals array length
Single element array

💡 Hints ▼

Hint 1: Use sliding window technique - calculate sum of first k elements, then slide the window.

Hint 2: When sliding, subtract the element going out and add the element coming in.

Hint 3: Keep track of maximum sum seen so far.

Sample Tests

Case	Input	Expected	Notes
1	[1,2,3,4], k=2	7	Basic case
2	[-1,-2,-3], k=2	-3	All negative
3	[5], k=1	5	Single element

Acceptance Criteria

Time complexity: O(n)
Space complexity: O(1)
Handles all edge cases correctly

2. First Negative Number in Every Window of Size K

Easy

Fixed Queue Array

▼

Problem Statement

Given an array of integers, for each window of size k, output the first negative number in that window. If there are no negative numbers, output 0.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def first_negative_in_window(nums, k):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function firstNegativeInWindow(nums, k) {
    // TODO
}
export { firstNegativeInWindow };

Input/Output Format

Input: Array nums of integers, integer k

Output: Array of first negative numbers in each window

Constraints

1 ≤ k ≤ n ≤ 100,000
-1000 ≤ nums[i] ≤ 1000

Examples

Example 1:
Input: nums = [12, -1, -7, 8, -15, 30, 16, 28], k = 3
Output: [-1, -1, -7, -15, -15, 0]

Example 2:
Input: nums = [1, 2, 3, 4], k = 2
Output: [0, 0, 0]

💡 Hints ▼

Hint 1: Use a deque to store indices of negative numbers in current window.

Hint 2: Remove indices that are out of current window from front of deque.

Hint 3: The front of deque gives the first negative number in current window.

3. Longest Substring Without Repeating Characters

Medium

Variable String Set

▼

Problem Statement

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

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def length_of_longest_substring(s):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function lengthOfLongestSubstring(s) {
    // TODO
}
export { lengthOfLongestSubstring };

Input/Output Format

Input: String s

Output: Integer representing the length

Constraints

0 ≤ s.length ≤ 50,000
s consists of English letters, digits, symbols and spaces

Examples

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest substring without repeating characters

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: "b" is the longest substring

💡 Hints ▼

Hint 1: Use two pointers and a set to track characters in current window.

Hint 2: When duplicate found, shrink window from left until duplicate is removed.

Hint 3: Keep track of maximum window size seen so far.

4. Minimum Window Substring

Hard

Variable Frequency Map String

▼

Problem Statement

Given strings s and t, return the minimum window substring in s that contains all characters of t (including duplicates). Return empty string if no such window exists.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def min_window(s, t):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function minWindow(s, t) {
    // TODO
}
export { minWindow };

Examples

Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Example 2:
Input: s = "a", t = "aa"
Output: ""

💡 Hints ▼

Hint 1: Use frequency maps for both target string and current window.

Hint 2: Keep track of how many characters from target are satisfied in current window.

Hint 3: When all characters are satisfied, try to shrink window from left.

5. Fruit Into Baskets (≤ 2 Distinct)

Medium

Variable At Most K Array

▼

Problem Statement

You have two baskets, each capable of holding any quantity of fruit. Given an array of fruit types, find the maximum number of fruits you can collect in a contiguous subarray with at most 2 distinct types.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def total_fruit(fruits):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function totalFruit(fruits) {
    // TODO
}
export { totalFruit };

Examples

Example 1:
Input: fruits = [1,2,1]
Output: 3
Explanation: We can collect all 3 fruits

Example 2:
Input: fruits = [0,1,2,2]
Output: 3
Explanation: Subarray [1,2,2] has 2 types and length 3

💡 Hints ▼

Hint 1: This is "longest subarray with at most 2 distinct elements".

Hint 2: Use frequency map to track types in current window.

Hint 3: When more than 2 types, shrink from left until exactly 2 types remain.

6. Longest Ones After K Flips

Medium

Variable Budget Binary Array

▼

Problem Statement

Given a binary array nums and an integer k, return the maximum number of consecutive 1s in the array after flipping at most k zeros.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def longest_ones(nums, k):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function longestOnes(nums, k) {
    // TODO
}
export { longestOnes };

Examples

Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: Flip the two zeros to get [1,1,1,0,0,1,1,1,1,1,1], then subarray [1,1,1,1,1,1] has length 6

💡 Hints ▼

Hint 1: Keep track of zeros in current window - this is your "budget".

Hint 2: When zero count exceeds k, shrink window from left.

Hint 3: Window size gives the length of consecutive 1s possible.

7. Subarray Product Less Than K

Medium

Variable Product Count

▼

Problem Statement

Given an array of positive integers and a positive integer k, return the number of contiguous subarrays where the product of all elements is strictly less than k.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def num_subarray_product_less_than_k(nums, k):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function numSubarrayProductLessThanK(nums, k) {
    // TODO
}
export { numSubarrayProductLessThanK };

Constraints

1 ≤ nums.length ≤ 30,000
1 ≤ nums[i] ≤ 1000
0 ≤ k ≤ 10^6

Examples

Example 1:
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: Subarrays are [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]

💡 Hints ▼

Hint 1: Use sliding window with product tracking.

Hint 2: When product ≥ k, shrink from left by dividing out elements.

Hint 3: For each valid window ending at right, add (right - left + 1) subarrays.

8. Smallest Subarray With Sum ≥ S

Medium

Variable Sum Minimum Length

▼

Problem Statement

Given an array of positive integers and a positive integer target, return the minimal length of a contiguous subarray whose sum is greater than or equal to target. Return 0 if no such subarray exists.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def min_subarray_len(target, nums):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function minSubArrayLen(target, nums) {
    // TODO
}
export { minSubArrayLen };

Examples

Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: Subarray [4,3] has minimal length

💡 Hints ▼

Hint 1: Expand window until sum ≥ target, then try to shrink.

Hint 2: Keep track of minimum window size seen.

Hint 3: Shrink from left while sum remains ≥ target.

9. Longest Subarray With Sum = Target

Medium

Variable Sum Exact Match

▼

Problem Statement

Given an array of positive integers and a target sum, return the length of the longest contiguous subarray with sum equal to target. Return 0 if no such subarray exists.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def longest_subarray_sum(nums, target):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function longestSubarraySum(nums, target) {
    // TODO
}
export { longestSubarraySum };

Examples

Example 1:
Input: nums = [1,2,1,0,1], target = 4
Output: 4
Explanation: Subarray [1,2,1,0] has sum 4 and length 4

💡 Hints ▼

Hint 1: Only works with positive integers (sliding window property).

Hint 2: Expand until sum ≥ target, shrink until sum < target.

Hint 3: Record length when sum exactly equals target.

10. Count Substrings With At Most K Distinct Characters

Medium

Variable At Most K String

▼

Problem Statement

Given a string s and an integer k, return the number of substrings that contain at most k distinct characters.

Function Signature

# Day 12 – Sliding Window
# Complete the function as per the problem statement.
def at_most_k_distinct(s, k):
    pass

// Day 12 – Sliding Window
// Complete the function as per the problem statement.
function atMostKDistinct(s, k) {
    // TODO
}
export { atMostKDistinct };

Examples

Example 1:
Input: s = "pqpqs", k = 2
Output: 12
Explanation: Substrings with at most 2 distinct chars

Important Note

To find exactly K distinct characters: exactlyK(s, k) = atMostK(s, k) - atMostK(s, k-1)

💡 Hints ▼

Hint 1: For each valid window, add (right - left + 1) substrings ending at right.

Hint 2: Use frequency map to track distinct characters.

Hint 3: Shrink when distinct count > k.

11. Number of Nice Subarrays (Exactly K Odds)

Medium

Variable