LeetCode Series: SlidingWindow (3/5)

Hi there! I've been busy learning new tech (and again: ended up in "tutorial-loop-hell").

Today, we will learn the sliding window technique — pretty useful and it covers a huge amount of problems on LeetCode.

Sliding Window

See the word substring in a problem? In about 80% of cases, that’s a hint to use a sliding window.

• Longest / Maximum / Minimum

• Substring / Subarray / Block

• ... of size k / length k

In some sense, it’s a kind of two-pointers pattern: whenever you deal with consecutive elements, that’s usually a sliding window.

The idea: use two pointers to track a range of elements — that’s your window. You can expand it, shrink it, whatever the problem needs. You only care about the elements inside the window; the rest of the array? You don’t care about it.

Two types of sliding window

• Fixed-size window → window size doesn’t change; move the two pointers along the array.
• Dynamic window → window can shrink or grow depending on the problem.

General Approach

1. Initialize leftPtr = 0, rightPtr = 0 (optionally track window length).
2. While rightPtr < arr.length: 2.1. Expand the window by moving rightPtr++ if your condition allows. 2.2 Shrink the window by moving leftPtr++ if needed.
3. Process whatever you need inside the window.

Here’s a code example:

Let’s try to solve a LeetCode problem.

643. Maximum Average Subarray I

In short:

• an integer array nums
• nums length n
• integer k
• find a subarray of length k with the max average and return it

Approach

A subarray.. of length k? → a sliding window. A fixed-size sliding window.
First, let’s find the subarray with the maximum sum. In the end, divide that sum by k to get the average."

Step 1: Compute the first window (minimum size should be k → it will be our first max).

Step 2: Slide the window — expand and shrink as needed in each iteration. Create a sum variable equal to our max. While sliding, update sum and compare it with max.

Step 3: In this problem, they ask us to return a double. Okay, return it and don’t forget to divide by k — they still ask us for the average.

Code

• Time: O(n) - no brute force with O(n^2)
• Space: O(1) - we don’t need any data structures

Summary - Key Points to Remember

• Sliding Window = a two-pointer technique for problems involving consecutive elements.

• Common keywords: longest, maximum, minimum, substring, subarray, block, “of size k”.

• Two types: Fixed-size and Dynamic window

• General approach:

• Start with left = 0, right = 0.

• Expand window by moving right.

• Shrink window by moving left if needed.

That's all for today!

In the next 2 sections, I’d like to explain two topics that are also a bit hard for me (they also require knowledge of trees and graphs). It will be challenging, but also pretty interesting! See you next time /smile/