Interview Kit: Arrays - Sliding window.

It's All About Patterns!

Once you learn the patterns, everything starts to feel a bit easier! If you're like me, you probably don't like tech interviews, and I don't blame you—they can be tough.

Array problems are some of the most common ones you’ll encounter in interviews. These problems often involve working with natural arrays:

const arr = [1, 2, 3, 4, 5];

And string problems, which are essentially arrays of characters:

"mylongstring".split(""); // ['m', 'y', 'l', 'o','n', 'g', 's','t','r','i', 'n', 'g']

One of the most common patterns for solving array problems is the sliding window.

Sliding Window Pattern

The sliding window pattern involves two pointers that move in the same direction—like a window sliding across the array.

When to Use It

Use the sliding window pattern when you need to find a sub-array or sub-string that satisfies a certain condition, such as being the minimum, maximum, longest, or shortest.

Rule 1: If you need to find a sub-array or sub-string and the data structure is an array or string, consider using the sliding window pattern.

Simple Example

Here’s a basic example to introduce the concept of pointers in a sliding window:

function SlidingWindow(arr) {
    let l = 0;  // Left pointer
    let r = l + 1;  // Right pointer

    while (r < arr.length) {
        console.log("left", arr[l]);
        console.log("right", arr[r]);
        l++;
        r++;
    }
}

SlidingWindow([1, 2, 3, 4, 5, 6, 7, 8]);

Note that the left (L) and right (R) pointers don’t have to move at the same time, but they must move in the same direction.

The right pointer will never be lower than the left pointer.

Let’s explore this concept with a real interview problem.

Real-World Problem: Longest Substring Without Repeating Characters

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

Keywords: sub-string, longest (maximum)

function longestSubstr(str) {
    let longest = 0;
    let left = 0;
    let hash = {};

    for (let right = 0; right < str.length; right++) {
        if (hash[str[right]] !== undefined && hash[str[right]] >= left) {
            left = hash[str[right]] + 1;
        }

        hash[str[right]] = right;
        longest = Math.max(longest, right - left + 1);
    }

    return longest;
}

Don’t worry if this looks complicated—we’ll go through it bit by bit.

let str = "helloworld";
console.log(longestSubstr(str));  // Output: 5

The core of this problem is finding the longest sub-string without repeating characters.

Initial Window: Size 0

At the start, both the left (L) and right (R) pointers are at the same place:

let left = 0;

for (let right = 0; right < str.length; right++) {  // RIGHT POINTER

h e l l o w o r l d 
^
^
L
R

And we have an empty hash (object):

let hash = {};

What’s great about objects? They store unique keys, which is exactly what we need to solve this problem. We’ll use hash to track all the characters we’ve visited and check if we’ve seen the current character before (to detect duplicates).

By looking at the string, we can visually tell that world is the longest substring without repeating characters:

h e l l o w o r l d 
          ^        ^   
          L        R

This has a length of 5. So, how do we get there?

Let’s break it down step by step:

Initial State

hash = {}

h e l l o w o r l d 
^
^
L
R

Iteration 1:

On each iteration, we add the character under the R pointer to the hash map and increment:

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

Currently, there are no repeating characters in our window (h and e):

hash = {h: 0}
h e l l o w o r l d 
^ ^
L R

Iteration 2:

hash = {h: 0, e: 1}
h e l l o w o r l d 
^   ^
L   R

Now, we have a new window: hel.

Iteration 3:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
^     ^
L     R

Here’s where it gets interesting: we already have l in our hash, and R is pointing to another l in the string. This is where our if statement comes in:

if (hash[str[right]] !== undefined)

If our hash contains the letter R is pointing to, we’ve found a duplicate! The previous window (hel) is our longest so far.

So, what do we do next? We shrink the window from the left by moving the L pointer up since we’ve already processed the left substring. But how far do we move L?

left = hash[str[right]] + 1;

We move L to just after the duplicate:

hash = {h: 0, e: 1, l: 2}
h e l l o w o r l d 
      ^
      ^
      L
      R

We still add our duplicate to the hash, so L will now have an index of 3.

hash[str[right]] = right;
longest = Math.max(longest, right - left + 1);

New State: Iteration 4

hash = {h: 0, e: 1, l: 3}
h e l l o w o r l d 
      ^ ^
      L R

Iterations 4 to 6

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
      ^     ^
      L     R

When R points to another duplicate (o), we move L to just after the first o:

hash = {h: 0, e: 1, l: 3, o: 4, w: 5}
h e l l o w o r l d 
          ^ ^
          L R

We continue until we encounter another duplicate l:

hash = {h: 0, e: 1, l: 3, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^     ^
          L     R

But notice it's outside the current window! starting from w,

Rule 3: Ignore Processed sub-x

Anything outside the current window is irrelevant—we’ve already processed it. The key code to manage this is:

if (hash[str[right]] !== undefined && hash[str[right]] >= left)

This condition ensures we only care about characters within the current window, filtering out any noise.

hash[str[right]] >= left

We focus on anything bigger or equal to the left pointer

Final Iteration:

hash = {h: 0, e: 1, l: 8, o: 4, w: 5, o: 6, r: 7}
h e l l o w o r l d 
          ^       ^
          L       R

I know this was detailed, but breaking problems down into smaller patterns or rules is the easiest way to master them.

In Summary:

• Rule 1: Keywords in the problem (e.g., maximum, minimum) are clues. This problem is about finding the longest sub-string without repeating characters.
• Rule 2: If you need to find unique or non-repeating elements, think hash maps.
• Rule 3: Focus on the current window—anything outside of it is irrelevant.

Bonus Tips:

• Break down the problem and make it verbose using a small subset.
• When maximizing the current window, think about how to make it as long as possible. Conversely, when minimizing, think about how to make it as small as possible.

To wrap things up, here's a little challenge for you to try out! I’ll post my solution in the comments—it’s a great way to practice.

Problem 2: Sum Greater Than or Equal to Target

Given an array, find the smallest subarray with a sum equal to or greater than the target(my solution will be the first comment).

/**
 * 
 * @param {Array<number>} arr 
 * @param {number} target 
 * @returns {number} - length of the smallest subarray
 */
function greaterThanOrEqualSum(arr, target){
   let minimum = Infinity;
   let left = 0;
   let sum = 0;

   // Your sliding window logic here!
}

Remember, like anything in programming, repetition is key! Sliding window problems pop up all the time, so don’t hesitate to Google more examples and keep practicing.

I’m keeping this one short, but stay tuned—the next article will dive into the two-pointer pattern and recursion (prepping for tree problems). It’s going to be a bit more challenging!

If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!

Resources:

Tech interview Handbook

leet code arrays 101

The above is the detailed content of Interview Kit: Arrays - Sliding window.. For more information, please follow other related articles on the PHP Chinese website!