Challenge - 5 Problems
Sliding Window Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of sliding window maximum
What is the output of the following TypeScript code that finds the maximum in each sliding window of size 3?
DSA Typescript
function maxSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
for (let i = 0; i <= nums.length - k; i++) {
let max = nums[i];
for (let j = i + 1; j < i + k; j++) {
if (nums[j] > max) max = nums[j];
}
result.push(max);
}
return result;
}
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));Attempts:
2 left
💡 Hint
Think about the maximum value in each group of 3 consecutive numbers.
✗ Incorrect
The function slides a window of size 3 over the array and finds the maximum in each window. For example, the first window is [1,3,-1], max is 3; second window [3,-1,-3], max is 3; and so on.
🧠 Conceptual
intermediate1:00remaining
Sliding window sum count
Given an array of integers and a window size k, how many sliding windows of size k are there in the array?
Attempts:
2 left
💡 Hint
Think about how many times you can move a window of size k inside the array without going out of bounds.
✗ Incorrect
For an array of length n, the number of windows of size k is n - k + 1 because the window starts at index 0 up to index n-k.
🔧 Debug
advanced2:00remaining
Find the bug in sliding window average calculation
What error does this TypeScript code produce when calculating the average of each sliding window of size 3?
DSA Typescript
function slidingWindowAverage(nums: number[], k: number): number[] {
const result: number[] = [];
let windowSum = 0;
for (let i = 0; i < nums.length; i++) {
windowSum += nums[i];
if (i >= k) {
windowSum -= nums[i - k];
}
if (i >= k - 1) {
result.push(windowSum / k);
}
}
return result;
}
console.log(slidingWindowAverage([1, 2, 3, 4, 5], 3));Attempts:
2 left
💡 Hint
Check how the window sum is updated and when averages are pushed.
✗ Incorrect
The code correctly sums the first 3 elements, then subtracts the element leaving the window and adds the new one. The averages are pushed starting from index 2 (k-1). The output is [2, 3, 4].
❓ Predict Output
advanced2:00remaining
Output of sliding window minimum with deque
What is the output of this TypeScript code that finds the minimum in each sliding window of size 2 using a deque?
DSA Typescript
function minSlidingWindow(nums: number[], k: number): number[] {
const result: number[] = [];
const deque: number[] = [];
for (let i = 0; i < nums.length; i++) {
while (deque.length && nums[deque[deque.length - 1]] > nums[i]) {
deque.pop();
}
deque.push(i);
if (deque[0] === i - k) {
deque.shift();
}
if (i >= k - 1) {
result.push(nums[deque[0]]);
}
}
return result;
}
console.log(minSlidingWindow([4, 2, 12, 3, 5, 1, 7], 2));Attempts:
2 left
💡 Hint
The deque keeps indexes of minimum values in the current window.
✗ Incorrect
The code maintains a deque of indexes for minimum values. For each window of size 2, it outputs the minimum. The output is [2, 2, 3, 3, 1, 1].
🚀 Application
expert3:00remaining
Longest substring with at most K distinct characters
What is the length of the longest substring with at most 2 distinct characters in the string 'eceba'?
DSA Typescript
function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
let left = 0;
let right = 0;
const map = new Map<string, number>();
let maxLen = 0;
while (right < s.length) {
const char = s[right];
map.set(char, (map.get(char) ?? 0) + 1);
while (map.size > k) {
const leftChar = s[left];
map.set(leftChar, map.get(leftChar)! - 1);
if (map.get(leftChar) === 0) {
map.delete(leftChar);
}
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
console.log(lengthOfLongestSubstringKDistinct('eceba', 2));Attempts:
2 left
💡 Hint
Use a sliding window to keep track of characters and their counts.
✗ Incorrect
The longest substring with at most 2 distinct characters is 'ece' with length 3.