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!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics











JavaScript is the cornerstone of modern web development, and its main functions include event-driven programming, dynamic content generation and asynchronous programming. 1) Event-driven programming allows web pages to change dynamically according to user operations. 2) Dynamic content generation allows page content to be adjusted according to conditions. 3) Asynchronous programming ensures that the user interface is not blocked. JavaScript is widely used in web interaction, single-page application and server-side development, greatly improving the flexibility of user experience and cross-platform development.

The latest trends in JavaScript include the rise of TypeScript, the popularity of modern frameworks and libraries, and the application of WebAssembly. Future prospects cover more powerful type systems, the development of server-side JavaScript, the expansion of artificial intelligence and machine learning, and the potential of IoT and edge computing.

Different JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.

Python is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.

JavaScript is the core language of modern web development and is widely used for its diversity and flexibility. 1) Front-end development: build dynamic web pages and single-page applications through DOM operations and modern frameworks (such as React, Vue.js, Angular). 2) Server-side development: Node.js uses a non-blocking I/O model to handle high concurrency and real-time applications. 3) Mobile and desktop application development: cross-platform development is realized through ReactNative and Electron to improve development efficiency.

This article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base

I built a functional multi-tenant SaaS application (an EdTech app) with your everyday tech tool and you can do the same. First, what’s a multi-tenant SaaS application? Multi-tenant SaaS applications let you serve multiple customers from a sing

The shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.
