Beginner LevelData Structures & Algorithms
What is the Sliding Window Technique?
ā Interview Prompt: Explain the Sliding Window pattern, fixed vs variable window, and solve the Maximum Sum Subarray of size K problem.
The Sliding Window technique maintains a window (contiguous sub-array/sub-string) and slides it across the input, avoiding redundant recomputation.
Fixed Window (size K):
Slide the window by adding the next element and removing the oldest one.
ā¢
Time: $O(N)$, Space: $O(1)$.
Variable Window:
Expand the right pointer; shrink the left pointer when a constraint is violated.
ā¢
Used for: Longest substring without repeating characters, smallest subarray with sum ā„ target.
Code Implementation Example
typescript
// Max sum subarray of size K ā O(N)
function maxSumSubarray(arr: number[], k: number): number {
let windowSum = 0, maxSum = -Infinity;
for (let i = 0; i < arr.length; i++) {
windowSum += arr[i];
if (i >= k - 1) {
maxSum = Math.max(maxSum, windowSum);
windowSum -= arr[i - (k - 1)]; // slide: remove leftmost
}
}
return maxSum;
}
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)š”Fixed sliding window computing maximum subarray sum in O(N).
šÆ Interview Key Takeaway
Sliding Window converts O(NĀ²) brute-force subarray problems into O(N) by maintaining a running computation as the window moves.
#DSA#Sliding Window#Patterns#Subarray#Beginner
Back to all Data Structures & Algorithms Questionsā