Skip to main content

Chapter 5: Core DSA: Arrays, Strings, Hashing, Two Pointers, Sliding Window

By the end of this chapter, you will have a mental framework for solving any array, string, or hashing problem in under twenty minutes. Not "maybe." Not "if the problem is easy." Any problem built on these five patterns. You will walk into the interview, read the question, and within sixty seconds know which pattern to deploy. The rest is typing speed.

That is not a motivational poster. It is a claim I can back with code, pattern recognition, and the same system that took engineers from "I grinded 300 LeetCode problems and still blank out" to "I solved a hard in 12 minutes and got the offer."

Here is what most engineers get wrong about DSA interviews: they treat every problem as a unique puzzle. They collect solutions like Pokemon cards. Three months of LeetCode, 200 problems solved, and they still freeze when the interviewer tweaks one constraint. Because they never learned the patterns. They learned the answers.

This chapter fixes that. We are going to dissect five topics that appear in roughly 70% of all DSA interview questions at Indian product companies and FAANG offices in Bangalore, Hyderabad, and Gurgaon. Not 70% of easy questions. 70% of all questions — including the hards that separate the ₹60 LPA offers from the ₹30 LPA ones.

You will learn the concept, the complexity, the code, and — most importantly — "The Trick." The one insight that unlocks each pattern. The thing you need to see in the problem statement to know, instantly, which tool to reach for.

Let us begin.

The Five Patterns That Matter​

Before we write a single line of code, let us name the enemy. DSA interviews at the ₹60L-1Cr level are not testing whether you memorized quicksort. They are testing whether you can map a real-world problem to a computational pattern, then execute that pattern under pressure.

Here are the five patterns that show up again and again:

  1. Arrays — prefix sums, Kadane's algorithm, rotation tricks
  2. Strings — anagrams, palindromes, pattern matching
  3. Hashing — collision resolution, custom hash maps, frequency counting
  4. Two Pointers — fast-slow, left-right, three-pointer variations
  5. Sliding Window — fixed window, variable window, window with hash map

If you master these five, you can walk into any interview and solve the first two rounds cold. The system design round is a different beast — we cover that in Part III. But for the DSA gate? These five patterns are your key.

Arrays: The Foundation Everything Sits On​

Arrays are not "the easy topic." They are the topic where interviewers hide complexity in plain sight. An array problem looks simple — "find the maximum subarray sum" — and then the constraints hit: O(n) time, O(1) space, and by the way, the array has 10^5 elements.

Three array techniques show up more than any others in Indian product company interviews: prefix sum, Kadane's algorithm, and array rotation. Let us take them one at a time.

Prefix Sum: Precompute Once, Query Forever​

The Concept

You have an array. Someone asks you: "What is the sum of elements from index i to j?" You could loop from i to j every time. That is O(n) per query. For m queries, O(n*m). If n = 10^5 and m = 10^5, you are looking at 10^10 operations. Your interviewer is already reaching for the rejection email.

Prefix sum says: compute the cumulative sum once. Store it. Then any range sum query becomes O(1).

The math is embarrassingly simple:

prefix[i] = arr[0] + arr[1] + ... + arr[i]
sum(i, j) = prefix[j] - prefix[i-1]   // if i > 0
sum(0, j) = prefix[j]                  // if i == 0

The Trick: Whenever you see "range sum," "subarray sum," or "sum between indices" — especially with multiple queries — your first thought should be prefix sum. Do not pass Go. Do not write a loop.

Code: Range Sum Query

class RangeSumQuery {
  constructor(arr) {
    this.prefix = new Array(arr.length);
    this.prefix[0] = arr[0];
    for (let i = 1; i < arr.length; i++) {
      this.prefix[i] = this.prefix[i - 1] + arr[i];
    }
  }

  // Returns sum of arr[left...right] inclusive, O(1)
  sumRange(left, right) {
    if (left === 0) return this.prefix[right];
    return this.prefix[right] - this.prefix[left - 1];
  }
}

// Usage
const rsq = new RangeSumQuery([3, 1, 4, 1, 5, 9, 2, 6]);
console.log(rsq.sumRange(2, 5)); // 4 + 1 + 5 + 9 = 19

Time to build: O(n). Each query: O(1). Space: O(n) for the prefix array. This is the pattern. Simple, but interviewers will dress it up in a story about "analyzing user engagement metrics over date ranges" or "computing revenue between quarters." Same math underneath.

The Extension They Do Not Teach on YouTube

Most tutorials stop at 1D prefix sums. The interview that gets you to ₹80 LPA will ask about 2D prefix sums. You have a matrix. You need the sum of a sub-rectangle in O(1). Same idea, one more dimension:

class RangeSumQuery2D {
  constructor(matrix) {
    const rows = matrix.length, cols = matrix[0].length;
    // prefix[i][j] = sum of rectangle from (0,0) to (i-1, j-1)
    this.prefix = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));

    for (let i = 1; i <= rows; i++) {
      for (let j = 1; j <= cols; j++) {
        this.prefix[i][j] =
          matrix[i - 1][j - 1] +
          this.prefix[i - 1][j] +
          this.prefix[i][j - 1] -
          this.prefix[i - 1][j - 1];
      }
    }
  }

  // Sum of rectangle from (r1,c1) to (r2,c2) inclusive, 0-indexed
  sumRegion(r1, c1, r2, c2) {
    return (
      this.prefix[r2 + 1][c2 + 1] -
      this.prefix[r1][c2 + 1] -
      this.prefix[r2 + 1][c1] +
      this.prefix[r1][c1]
    );
  }
}

The inclusion-exclusion principle at work: add the big rectangle, subtract the top strip, subtract the left strip, add back the double-counted corner. If you can explain why that formula works during the interview, you have just signaled that you are not a memorizer. You understand the geometry.

Indian Context: A friend of mine got this exact question at a fintech unicorn in Bangalore. The problem was framed as "compute the total transaction volume for any date range and merchant category." He built the 2D prefix sum in eight minutes, explained the inclusion-exclusion logic, and moved to the next round. The candidate before him wrote nested loops and got O(n*m) per query. Same problem. Different pattern recognition. Different outcome.

Kadane's Algorithm: Maximum Subarray, Maximum Impact​

The Concept

Find the contiguous subarray with the largest sum. The brute force checks every subarray: O(n^2). Kadane's algorithm does it in O(n) with O(1) space. It is the poster child for dynamic programming disguised as an array problem.

The insight: at each position i, you have a choice. Either extend the previous subarray (if it helps) or start fresh from i. That is it. One decision per element.

maxEndingHere = max(arr[i], maxEndingHere + arr[i])
maxSoFar = max(maxSoFar, maxEndingHere)

The Trick: The moment you see "maximum subarray" or "maximum sum contiguous" — Kadane. But the deeper trick is recognizing when a problem reduces to Kadane. Maximum product subarray. Maximum sum circular subarray. Maximum difference subarray. All Kadane variants wearing different masks.

Code: Classic Kadane

function maxSubarraySum(arr) {
  let maxEndingHere = arr[0];
  let maxSoFar = arr[0];

  for (let i = 1; i < arr.length; i++) {
    maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }

  return maxSoFar;
}

console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 → [4, -1, 2, 1]

Code: Kadane with Subarray Tracking

Interviewers love asking for the actual subarray, not just the sum. Here is the version that returns both:

function maxSubarrayWithIndices(arr) {
  let maxEndingHere = arr[0], maxSoFar = arr[0];
  let start = 0, end = 0, tempStart = 0;

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > maxEndingHere + arr[i]) {
      maxEndingHere = arr[i];
      tempStart = i;
    } else {
      maxEndingHere += arr[i];
    }

    if (maxEndingHere > maxSoFar) {
      maxSoFar = maxEndingHere;
      start = tempStart;
      end = i;
    }
  }

  return { sum: maxSoFar, subarray: arr.slice(start, end + 1), start, end };
}

The Circular Variant — This One Separates ₹30 LPA from ₹60 LPA

What if the array is circular? The maximum subarray might wrap around the end. The trick: compute both the maximum subarray (Kadane) and the minimum subarray (inverted Kadane). The circular maximum is either the straight maximum or the total sum minus the minimum subarray.

function maxCircularSubarraySum(arr) {
  const n = arr.length;

  // Case 1: max subarray is not circular (standard Kadane)
  let maxEnding = arr[0], maxStraight = arr[0];
  for (let i = 1; i < n; i++) {
    maxEnding = Math.max(arr[i], maxEnding + arr[i]);
    maxStraight = Math.max(maxStraight, maxEnding);
  }

  // Case 2: max subarray wraps around
  // totalSum - minSubarraySum
  const totalSum = arr.reduce((a, b) => a + b, 0);
  let minEnding = arr[0], minStraight = arr[0];
  for (let i = 1; i < n; i++) {
    minEnding = Math.min(arr[i], minEnding + arr[i]);
    minStraight = Math.min(minStraight, minEnding);
  }

  // Edge case: all elements are negative
  if (totalSum === minStraight) return maxStraight;

  return Math.max(maxStraight, totalSum - minStraight);
}

The edge case matters. If every element is negative, totalSum - minStraight gives zero — which is wrong because an empty subarray is not allowed. Handling that edge case in the interview without being prompted? That is the difference between "he knows the algorithm" and "he understands the algorithm."

Maximum Product Subarray: When Negatives Flip the Game​

The Concept

Find the contiguous subarray with the largest product. Your first instinct will be: "Just use Kadane with multiplication." That instinct is wrong, and here is why.

In Kadane's algorithm for sums, a negative number always makes the sum smaller. You either extend the previous subarray or start fresh — the decision is binary. But with products, a negative number does something sneaky: it flips the sign. A very negative product (minimum) multiplied by another negative number becomes a very positive product (maximum). The minimum and maximum swap roles.

This means you cannot track just the maximum product ending at each position. You must track both the maximum and the minimum, because the minimum today might become the maximum tomorrow when multiplied by a negative.

The Trick: Maintain two values at each step: maxEndingHere and minEndingHere. When you encounter a negative number, swap them before multiplying. This swap captures the sign-flip dynamic that makes product subarrays fundamentally different from sum subarrays.

Walk through the array [2, 3, -2, 4] step by step:

  • i=0, val=2: maxEnding=2, minEnding=2, result=2
  • i=1, val=3: maxEnding=max(3, 23)=6, minEnding=min(3, 23)=3, result=6
  • i=2, val=-2: Negative! Swap first. maxEnding=3, minEnding=6. Now compute: maxEnding=max(-2, 3*(-2))=-2, minEnding=min(-2, 6*(-2))=-12, result=6
  • i=3, val=4: maxEnding=max(4, -24)=4, minEnding=min(4, -124)=-48, result=6

The answer is 6, from the subarray [2, 3]. Notice how at i=2, the negative number turned our minimum (-12) into a candidate — if the next number were also negative, that -12 would have become a large positive. The swap is what makes this work.

Code: Maximum Product Subarray

function maxProductSubarray(arr) {
  if (arr.length === 0) return 0;

  let maxEndingHere = arr[0];
  let minEndingHere = arr[0];
  let maxSoFar = arr[0];

  for (let i = 1; i < arr.length; i++) {
    const num = arr[i];

    // When num is negative, max and min swap roles
    if (num < 0) {
      [maxEndingHere, minEndingHere] = [minEndingHere, maxEndingHere];
    }

    maxEndingHere = Math.max(num, maxEndingHere * num);
    minEndingHere = Math.min(num, minEndingHere * num);

    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }

  return maxSoFar;
}

console.log(maxProductSubarray([2, 3, -2, 4]));   // 6 → [2, 3]
console.log(maxProductSubarray([-2, 0, -1]));      // 0 → [0]
console.log(maxProductSubarray([-2, 3, -4]));      // 24 → entire array

Complexity: O(n) time, O(1) space. Same asymptotic complexity as Kadane, but the logic is richer. This problem appears at Google and Uber specifically because it tests whether you understand why Kadane works, not just that you memorized the two-line recurrence.

The Deeper Lesson: When a problem asks for "maximum subarray" but the operation is not addition, do not blindly copy Kadane. Ask yourself: does the operation have the same monotonic property as addition? If multiplying by a negative can flip the sign, the answer is no — and you need to track both extremes.

Array Rotation: The Reversal Trick​

The Concept

Rotate an array k positions to the right. The naive approach: shift one element at a time, k times. O(n*k). The clever approach: use extra space. O(n) time, O(k) space. The interview approach: the three-reversal trick. O(n) time, O(1) space.

The Trick: To rotate [1,2,3,4,5,6,7] by k=3 to the right:

  1. Reverse the whole array: [7,6,5,4,3,2,1]
  2. Reverse the first k elements: [5,6,7,4,3,2,1]
  3. Reverse the remaining n-k elements: [5,6,7,1,2,3,4]

Done. Three reverses. No extra array. The interviewer will ask you to derive this. Here is the derivation: rotating right by k means the last k elements move to the front. Reversing the whole array puts them at the front, but in reverse order. Reversing just that segment fixes their order. The remaining segment also needs a reverse to restore its original relative order.

Code:

function rotate(arr, k) {
  const n = arr.length;
  k = k % n; // k can be larger than n
  if (k === 0) return arr;

  function reverse(start, end) {
    while (start < end) {
      [arr[start], arr[end]] = [arr[end], arr[start]];
      start++;
      end--;
    }
  }

  reverse(0, n - 1);       // Step 1: full reverse
  reverse(0, k - 1);       // Step 2: reverse first k
  reverse(k, n - 1);       // Step 3: reverse rest

  return arr;
}

The k = k % n line is not optional. I have seen candidates fail because they did not handle k > n. The array [1,2,3] rotated by 4 positions is the same as rotating by 1. If you skip the modulo, your indices go out of bounds. If you mention the modulo before the interviewer points it out, you look like someone who tests their own edge cases.

Trapping Rain Water: The Two-Pointer Classic Disguised as an Array Problem​

The Concept

Given an array of non-negative integers representing an elevation map where each bar has width 1, compute how much water can be trapped between the bars after raining.

Visualize it. The array [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] looks like this:

      |
|     | |   |
| |   | | | |
| | | | | | |

The water pools in the dips between taller bars. The total trapped water is 6 units.

The brute force: for each position, find the tallest bar to its left and the tallest bar to its right. The water at that position is min(leftMax, rightMax) - height[i]. This is O(n^2) because you scan left and right for every index.

The optimization: precompute leftMax and rightMax arrays in O(n), then compute water in one more pass. O(n) time, O(n) space. Good, but the interviewer will ask: "Can you do O(1) space?"

Yes. Two pointers.

The Trick: Place one pointer at the left end and one at the right end. Maintain leftMax (the tallest bar seen from the left) and rightMax (the tallest bar seen from the right). At each step, process the side with the smaller maximum. Why? Because the water level at any position is determined by the shorter of the two boundaries. If leftMax < rightMax, the left pointer's water is trapped by leftMax regardless of what lies further right — because rightMax is already taller, and anything between can only be taller still. So you can safely compute water at the left pointer and move it inward. Same logic applies when rightMax is smaller.

Step-by-step walkthrough for [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]:

  • left=0 (height 0), right=11 (height 1). leftMax=0, rightMax=1. leftMax <= rightMax, so process left. Water at index 0 = max(0, 0-0) = 0. leftMax stays 0. left moves to 1.
  • left=1 (height 1), right=11 (height 1). leftMax=0, rightMax=1. leftMax <= rightMax. Water at index 1: height 1 > leftMax 0, so update leftMax=1, water=0. left moves to 2.
  • left=2 (height 0), right=11 (height 1). leftMax=1, rightMax=1. leftMax <= rightMax. Water at index 2 = 1-0 = 1. left moves to 3.
  • left=3 (height 2), right=11 (height 1). leftMax=1, rightMax=1. Now rightMax < leftMax, so process right. Water at index 11 = max(0, 1-1) = 0. rightMax stays 1. right moves to 10.
  • Continue this dance. Each step processes one bar, and the water is computed in O(1) because you already know the limiting boundary.

Code: Trapping Rain Water — Two Pointers, O(1) Space

function trap(height) {
  if (height.length === 0) return 0;

  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      // Left side is the bottleneck
      if (height[left] >= leftMax) {
        leftMax = height[left]; // new taller bar, no water trapped
      } else {
        water += leftMax - height[left]; // water trapped above this bar
      }
      left++;
    } else {
      // Right side is the bottleneck
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }

  return water;
}

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6
console.log(trap([4, 2, 0, 3, 2, 5])); // 9

Complexity: O(n) time, O(1) space. The two-pointer approach processes each element exactly once. The leftMax and rightMax variables replace the O(n) auxiliary arrays.

Why This Problem Matters: Trapping Rain Water is asked at Google, Amazon, Microsoft, and every Indian unicorn that pays above ₹50 LPA. It tests three things at once: (1) can you visualize a problem geometrically, (2) can you derive the two-pointer condition from first principles, and (3) can you handle edge cases (empty array, flat terrain, single peak). If you can solve this on a whiteboard in under 15 minutes while explaining your reasoning, you have just signaled senior-level problem-solving ability.

Where the Real Learning Happens​

At this point, you have three array techniques. But here is what separates the engineers who get offers from those who do not: they do not stop at "I understand the code." They ask: what problem traits tell me which technique to use?

Let us build that mapping:

Problem TraitTechniqueSignal Words
Range sum queries, subarray sum equals kPrefix Sum"sum between," "range," "subarray sum"
Maximum/minimum contiguous subarrayKadane"maximum subarray," "contiguous," "largest sum"
Rotate/shift array in-placeReversal"rotate," "shift," "in-place," "O(1) space"

Print this table. Tape it to your wall. When you practice, force yourself to identify the trait before you write code. The goal is to make this mapping automatic — so automatic that you do not have to think about it during the interview.

Strings: Where Arrays Meet Characters​

Strings are arrays of characters. But they bring their own bag of tricks because the operations we care about — comparison, searching, rearrangement — have properties that generic arrays do not.

Three string patterns dominate interviews: anagrams, palindromes, and pattern matching.

Anagrams: Counting, Not Sorting​

The Concept

Two strings are anagrams if they contain the same characters with the same frequencies. "listen" and "silent." "a gentleman" and "elegant man" (ignoring spaces).

The naive approach: sort both strings and compare. O(n log n). Works. But the interviewer will ask: "Can you do better?"

Yes. Count characters. O(n) time, O(1) space (the alphabet is fixed — 26 letters, or 128 ASCII, or whatever your character set is).

The Trick: Anagrams are fundamentally a frequency problem, not an ordering problem. The moment you reach for .sort(), ask yourself: can I count instead?

Code: Basic Anagram Check

function isAnagram(s1, s2) {
  if (s1.length !== s2.length) return false;

  const count = new Array(26).fill(0);

  for (let i = 0; i < s1.length; i++) {
    count[s1.charCodeAt(i) - 97]++;
    count[s2.charCodeAt(i) - 97]--;
  }

  return count.every(c => c === 0);
}

Code: Group Anagrams — The Interview Favorite

Given an array of strings, group the anagrams together. This question appears at Amazon, Google, Microsoft, and every Indian unicorn you can name.

The key insight: instead of sorting each string (O(m log m) per string), build a frequency signature in O(m). Think of it as creating a "fingerprint" for each string — a representation that is identical for all anagrams but different for non-anagrams. The character-count-as-key pattern works like this: for each string, count how many times each of the 26 letters appears, then join those counts into a string key. All anagrams produce the same key because they have the same letter frequencies.

For example, "eat", "tea", and "ate" all produce the key "1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0" (1 each of a, e, t). "bat" produces a different key. The hash map groups strings by this key.

function groupAnagrams(strs) {
  const map = new Map();

  for (const str of strs) {
    // Create a frequency key: "a1b0c2..." for 26 letters
    const count = new Array(26).fill(0);
    for (const ch of str) {
      count[ch.charCodeAt(0) - 97]++;
    }
    const key = count.join('#');

    if (!map.has(key)) map.set(key, []);
    map.get(key).push(str);
  }

  return Array.from(map.values());
}

// Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
// Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

The join('#') separator is critical — without it, "a1b10" and "a11b0" would collide. This is the kind of detail that separates a working solution from a correct one.

Complexity: O(n * m) time where n is the number of strings and m is the average string length. O(n * m) space for storing all strings in the map. Compare this to the sort-based approach: O(n * m log m) time. For long strings, the frequency-key approach is significantly faster.

Indian Context: A candidate I mentored got the "group anagrams" question at a well-known food delivery company in Bangalore. He wrote the frequency-key solution in under five minutes. The interviewer then asked: "What if the strings contain Unicode characters, not just a-z?" He pivoted instantly — use a Map for the character count instead of a fixed array, and serialize the sorted entries as the key. He got the offer. The candidate in the next room used .sort() on every string, got O(n * m log m), and was asked to optimize. He could not. Same problem. Different depth of understanding.

Palindromes: Symmetry Is the Shortcut​

The Concept

A palindrome reads the same forward and backward. "racecar." "A man, a plan, a canal: Panama." The brute force is to reverse the string and compare. O(n) time, O(n) space. The two-pointer approach does it in O(n) time, O(1) space.

The Trick: Palindromes are about symmetry. Compare from both ends, moving inward. The moment you find a mismatch, you are done.

Code: Valid Palindrome with Edge Cases

function isPalindrome(s) {
  let left = 0, right = s.length - 1;

  while (left < right) {
    // Skip non-alphanumeric characters
    while (left < right && !isAlphanumeric(s[left])) left++;
    while (left < right && !isAlphanumeric(s[right])) right--;

    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
    left++;
    right--;
  }

  return true;
}

function isAlphanumeric(ch) {
  const code = ch.charCodeAt(0);
  return (
    (code >= 48 && code <= 57) ||  // 0-9
    (code >= 65 && code <= 90) ||  // A-Z
    (code >= 97 && code <= 122)    // a-z
  );
}

Longest Palindromic Substring: Expand Around Center​

The Concept

Find the longest substring that is a palindrome. Brute force: check every substring. O(n^3) — for each of O(n^2) substrings, spend O(n) checking if it is a palindrome. Dynamic programming: O(n^2) time, O(n^2) space. The expand-around-center approach: O(n^2) time, O(1) space.

The Trick: A palindrome expands outward from its center. Think of it like dropping a stone in water — the ripples spread symmetrically. There are 2n-1 possible centers (each character, and each gap between characters). For each center, expand outward while the characters on both sides match. The longest palindrome is the largest expansion you find.

Why 2n-1 centers? Because palindromes can be odd-length (center is a character, like "racecar" centered at 'e') or even-length (center is between two characters, like "abba" centered between the two 'b's). For a string of length n, there are n single-character centers and n-1 between-character centers, totaling 2n-1.

Walk through "babad" step by step:

  • Center at index 0 ('b'): expand → "b" (length 1)
  • Center between 0 and 1: 'b' != 'a' → no palindrome
  • Center at index 1 ('a'): expand → "bab" (length 3) — 'b' at 0 matches 'b' at 2
  • Center between 1 and 2: 'a' != 'b' → no palindrome
  • Center at index 2 ('b'): expand → "aba" (length 3) — 'a' at 1 matches 'a' at 3
  • Center between 2 and 3: 'b' != 'a' → no palindrome
  • Center at index 3 ('a'): expand → "a" (length 1)
  • Center between 3 and 4: 'a' != 'd' → no palindrome
  • Center at index 4 ('d'): expand → "d" (length 1)

Longest: "bab" (or "aba", both length 3).

Code: Longest Palindromic Substring

function longestPalindrome(s) {
  if (!s || s.length < 1) return "";

  let start = 0, maxLen = 0;

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    // When the loop breaks, left and right are one step past the valid palindrome
    const len = right - left - 1;
    if (len > maxLen) {
      maxLen = len;
      start = left + 1;
    }
  }

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);     // odd-length palindrome
    expandAroundCenter(i, i + 1); // even-length palindrome
  }

  return s.substring(start, start + maxLen);
}

console.log(longestPalindrome("babad")); // "bab" or "aba"
console.log(longestPalindrome("cbbd"));  // "bb"

Complexity: O(n^2) time — for each of the 2n-1 centers, we expand up to n/2 times. O(1) space — we only store a few variables. This is the optimal solution for the general case. (Manacher's algorithm achieves O(n) but is never expected in an interview — mentioning it shows you have gone deep, but implementing expand-around-center correctly is what gets you the offer.)

The expand-around-center pattern is worth internalizing. It shows up in "palindromic substrings count," "longest palindromic subsequence," and a dozen variations. The core idea — expand outward while the property holds — is the same every time.

Pattern Matching: KMP and Why You Need to Know It​

The Concept

Find all occurrences of a pattern string inside a text string. The naive approach slides the pattern across the text, comparing character by character. O(n*m) in the worst case. KMP (Knuth-Morris-Pratt) does it in O(n+m) by preprocessing the pattern into a "failure function" — also called the LPS (Longest Proper Prefix which is also Suffix) array.

The Trick: When a mismatch occurs, the LPS array tells you how far to shift the pattern without re-comparing characters you already know match. You never move the text pointer backward.

This is the algorithm that most engineers skip because "it is too hard" or "nobody asks it." They are wrong. I have seen KMP asked at Google Bangalore, Uber Hyderabad, and at least three Series-C Indian startups. Not because they expect you to regurgitate the code from memory, but because they want to see if you understand why the LPS array works.

Code: Building the LPS Array

function buildLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0; // length of previous longest prefix-suffix
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1]; // fall back — the clever part
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

The line len = lps[len - 1] is where most people get lost. Here is what it means: when you have a mismatch while building the LPS, you do not reset to zero. You fall back to the longest prefix-suffix of the prefix you have matched so far. It is recursion on the pattern itself. If you can explain this line in an interview, you have demonstrated algorithm-level understanding, not memorization.

Code: KMP Search

function kmpSearch(text, pattern) {
  if (pattern.length === 0) return 0;
  const lps = buildLPS(pattern);
  const result = [];
  let i = 0; // index for text
  let j = 0; // index for pattern

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
    }

    if (j === pattern.length) {
      result.push(i - j); // match found at this index
      j = lps[j - 1];
    } else if (i < text.length && text[i] !== pattern[j]) {
      if (j !== 0) {
        j = lps[j - 1]; // use LPS to skip ahead
      } else {
        i++;
      }
    }
  }

  return result;
}

Hashing: The O(1) Superpower​

Hashing is not a data structure. It is a design philosophy: trade space for time. Store computed results so you never compute them twice. The hash map (or object, in JavaScript) is the most frequently used data structure in DSA interviews, and for good reason — it turns O(n) lookups into O(1).

How Hashing Works Under the Hood​

You call map.set(key, value). What actually happens?

  1. A hash function converts your key into an integer.
  2. That integer is mapped to an index in an underlying array using modulo: index = hash(key) % capacity.
  3. The value is stored at that index.

The magic — and the problem — is step 2. Two different keys can produce the same index. This is a hash collision.

Collision Resolution: Chaining vs. Open Addressing​

JavaScript's Map uses chaining under the hood (in V8, it is actually more sophisticated, but chaining is the mental model you need). When two keys hash to the same bucket, they form a linked list. Lookup traverses the list.

The worst case: all keys collide. O(n) per operation. But with a good hash function and a low load factor (ratio of entries to capacity), collisions are rare, and the average case is O(1).

The Trick: Hash maps give you O(1) average-case lookup. The interviewer wants to see that you know when to use them (anytime you need fast lookups) and when not to (when keys are sequential integers — use an array; when you need ordering — use a tree).

Building a Hash Map from Scratch​

This is a question that appears in senior-level interviews. Not because you will ever write your own hash map in production, but because building one proves you understand the trade-offs.

class MyHashMap {
  constructor(capacity = 1000) {
    this.capacity = capacity;
    this.size = 0;
    this.buckets = new Array(capacity).fill(null).map(() => []);
  }

  _hash(key) {
    if (typeof key === 'string') {
      let hash = 0;
      for (let i = 0; i < key.length; i++) {
        hash = (hash * 31 + key.charCodeAt(i)) % this.capacity;
      }
      return hash;
    }
    return key % this.capacity;
  }

  set(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    for (const entry of bucket) {
      if (entry[0] === key) {
        entry[1] = value; // update existing
        return;
      }
    }

    bucket.push([key, value]);
    this.size++;
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    for (const entry of bucket) {
      if (entry[0] === key) return entry[1];
    }

    return -1; // or undefined
  }

  remove(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        this.size--;
        return;
      }
    }
  }
}

The hash function uses 31 as the multiplier — a small prime that produces good distribution for string keys. This is not arbitrary. Java's String.hashCode() uses 31 for the same reason. Knowing why 31 (it is prime, it is small enough that overflow is manageable, and 31 * x = (x << 5) - x which the compiler optimizes to a shift and subtract) signals depth.

The Two-Sum Problem: Hashing's Greatest Hit​

No DSA chapter is complete without two-sum. Not because it is hard — it is not — but because it is the cleanest demonstration of the hash map's power.

Problem: Given an array and a target, return indices of two numbers that sum to the target.

Brute force: Nested loops, O(n^2). Hash map: Single pass, O(n).

function twoSum(nums, target) {
  const seen = new Map();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    seen.set(nums[i], i);
  }

  return []; // no solution
}

The insight: instead of asking "which two numbers sum to target?" ask "for each number, does its complement already exist in the map?" This inversion — from "find a pair" to "check if complement exists" — is the hash map pattern in a nutshell.

The Extension: Three-Sum and Beyond

Two-sum is the warm-up. Three-sum is the real test. The hash map approach for three-sum is O(n^2) — for each element, run two-sum on the rest. But the more elegant solution uses sorting and two pointers (which we cover next). The interviewer wants to see you recognize that hashing is not always the answer — sometimes the constraints push you toward a different pattern.

LRU Cache: The FAANG Favorite That Tests Everything​

The Concept

Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. It must support two operations:

  • get(key): Return the value if the key exists, otherwise return -1. Accessing a key marks it as "recently used."
  • put(key, value): Insert or update the key-value pair. If the cache exceeds its capacity, evict the least recently used key.

Both operations must run in O(1) time.

This is the single most-asked hashing design problem at FAANG companies. It appears at Google, Amazon, Meta, and every Indian startup that models its interview process after FAANG. Why? Because it tests three things at once: (1) do you understand hash maps, (2) do you understand linked lists, and (3) can you combine two data structures to achieve a specific performance guarantee?

The Trick: A hash map alone gives you O(1) get and O(1) put, but it does not track ordering — you cannot identify the least recently used key in O(1). A linked list alone tracks ordering (move-to-front is O(1) if you have the node reference, and evict-from-tail is O(1) for a doubly linked list), but lookup is O(n). The solution: combine them. The hash map stores key-to-node references for O(1) lookup. The doubly linked list maintains usage order — most recently used at the head, least recently used at the tail.

JavaScript's Map gives us a shortcut. In ES6+, Map iterates its entries in insertion order. When you map.delete(key) and map.set(key, value), that key moves to the end of the iteration order — exactly the "mark as recently used" behavior we need. The oldest entry (least recently used) is always map.keys().next().value. This lets us implement an LRU cache in about 20 lines of code with no custom linked list.

Code: LRU Cache Using JavaScript Map

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    // Mark as recently used: delete and re-insert
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    // If key exists, delete it first (we'll re-insert to mark as recent)
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }

    // If at capacity, evict the least recently used (first item in Map)
    if (this.cache.size === this.capacity) {
      const lruKey = this.cache.keys().next().value;
      this.cache.delete(lruKey);
    }

    this.cache.set(key, value);
  }
}

// Usage
const lru = new LRUCache(2);
lru.put(1, 1);       // cache: {1=1}
lru.put(2, 2);       // cache: {1=1, 2=2}
console.log(lru.get(1)); // 1 — marks 1 as recently used. cache: {2=2, 1=1}
lru.put(3, 3);       // evicts key 2 (LRU). cache: {1=1, 3=3}
console.log(lru.get(2)); // -1 (evicted)
lru.put(4, 4);       // evicts key 1. cache: {3=3, 4=4}
console.log(lru.get(1)); // -1 (evicted)
console.log(lru.get(3)); // 3
console.log(lru.get(4)); // 4

Complexity: O(1) for both get and put. The Map.delete() and Map.set() operations are O(1) amortized. map.keys().next().value is O(1). This is the optimal solution.

What the Interviewer Is Looking For: If you use JavaScript's Map with the insertion-order trick, the interviewer will ask: "How would you implement this without relying on Map's insertion-order guarantee?" This is your cue to describe the doubly-linked-list-plus-hash-map approach. The hash map maps keys to linked list nodes. Each node has key, value, prev, and next pointers. On get, you remove the node from its current position and append it to the head. On put, you do the same, and if the cache is full, you remove the tail node and delete its key from the hash map. Mentioning both approaches — the pragmatic Map-based one and the from-scratch doubly-linked-list one — shows you understand the trade-off between leveraging language features and building the underlying data structure yourself.

Indian Context: This problem was asked at a Bengaluru office of a US-based ride-hailing company for a senior frontend role. The candidate wrote the Map-based solution in 10 minutes, then spent the next 10 minutes whiteboarding the doubly-linked-list version when the interviewer asked the follow-up. He got the offer at ₹72 LPA. The candidate in the parallel track tried to use a plain object and an array (splicing on every access — O(n) per operation). He did not make it past the round.

Two Pointers: The Art of Converging​

Two pointers is not a data structure. It is a strategy — use two indices to traverse a data structure, moving them according to some rule, to achieve O(n) time where brute force would be O(n^2).

There are three variants you must know cold.

Left-Right Pointers​

Two pointers start at opposite ends and move toward each other. Used for: sorted array problems, palindrome checking, container with most water, two-sum on sorted arrays.

The Trick: The array must be sorted (or the problem must have a property that lets you decide which pointer to move). The decision rule — "move left if X, move right if Y" — is the entire algorithm.

Code: Two-Sum on Sorted Array

function twoSumSorted(arr, target) {
  let left = 0, right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }

  return [];
}

Why does this work? Because the array is sorted. If arr[left] + arr[right] is too small, increasing left increases the sum. If it is too large, decreasing right decreases the sum. Each step eliminates one possibility. O(n) total.

Container With Most Water: Why Moving the Shorter Line Always Works​

The Concept

Given an array of heights representing vertical lines, find two lines that together with the x-axis form a container that holds the most water. The container's area is width * min(height[left], height[right]).

The brute force checks every pair: O(n^2). The two-pointer approach: O(n).

The Trick: The area is limited by the shorter of the two lines. The width is right - left. When you move a pointer inward, the width always decreases. So the only way to potentially find a larger area is to increase the height — and the only way to increase the height is to move the shorter line inward, hoping to find a taller one.

Here is why moving the taller line can never help. Suppose height[left] = 3 and height[right] = 7. The area is width * 3 (capped by the shorter left line). If you move the right pointer inward, the new height is still capped at 3 (or lower), and the width is smaller. The area can only decrease. But if you move the left pointer inward, you might find a line taller than 3 — say, height 8. Now the area is (width-1) * min(8, 7) = (width-1) * 7, which could be larger than the original width * 3. The greedy choice — always move the shorter line — is provably optimal.

Walk through [1, 8, 6, 2, 5, 4, 8, 3, 7]:

  • left=0 (h=1), right=8 (h=7): area = 8 * min(1,7) = 8. Move left (shorter).
  • left=1 (h=8), right=8 (h=7): area = 7 * min(8,7) = 49. Move right (shorter).
  • left=1 (h=8), right=7 (h=3): area = 6 * min(8,3) = 18. Move right.
  • left=1 (h=8), right=6 (h=8): area = 5 * min(8,8) = 40. Move either (both equal). Move right.
  • left=1 (h=8), right=5 (h=4): area = 4 * min(8,4) = 16. Move right.
  • left=1 (h=8), right=4 (h=5): area = 3 * min(8,5) = 15. Move right.
  • left=1 (h=8), right=3 (h=2): area = 2 * min(8,2) = 4. Move right.
  • left=1 (h=8), right=2 (h=6): area = 1 * min(8,6) = 6. Pointers meet. Max area = 49.

Code: Container With Most Water

function maxArea(height) {
  let left = 0, right = height.length - 1;
  let maxWater = 0;

  while (left < right) {
    const h = Math.min(height[left], height[right]);
    const w = right - left;
    maxWater = Math.max(maxWater, h * w);

    // Move the shorter line inward — the taller one might still be useful
    if (height[left] < height[right]) left++;
    else right--;
  }

  return maxWater;
}

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

Complexity: O(n) time, O(1) space. Each pointer moves at most n steps. The greedy insight — always move the shorter line — is what collapses O(n^2) to O(n). This is the kind of insight interviewers want you to derive, not memorize. If you can explain why moving the shorter line is always correct, you have demonstrated the reasoning ability they are paying for.

Fast-Slow Pointers​

Two pointers move at different speeds through the same structure. Used for: cycle detection in linked lists, finding the middle of a linked list, detecting happy numbers.

The Trick: If the fast pointer moves twice as fast as the slow pointer, they will meet inside any cycle. This is Floyd's cycle detection algorithm — also called the "tortoise and hare."

Code: Find Middle of Linked List

function findMiddle(head) {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow; // when fast reaches the end, slow is at the middle
}

For an even-length list, this returns the second middle node. If you need the first middle, initialize fast = head.next instead.

Code: Detect Cycle in Linked List

function hasCycle(head) {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // they met — cycle exists
  }

  return false; // fast reached null — no cycle
}

Code: Find Cycle Start Node

This is the follow-up that separates the memorizers from the understanders:

function detectCycleStart(head) {
  let slow = head, fast = head;

  // Phase 1: find meeting point
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  if (!fast || !fast.next) return null; // no cycle

  // Phase 2: find cycle start
  // The math: distance from head to cycle start == distance from meeting point to cycle start
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow;
}

The math behind Phase 2: let the distance from head to cycle start be a, the distance from cycle start to meeting point be b, and the cycle length be L. The fast pointer travels a + b + n*L (where n is some number of full cycles). The slow pointer travels a + b. Since fast moves twice as fast: 2(a + b) = a + b + n*L, which simplifies to a + b = n*L, so a = n*L - b. This means the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (going forward). If you can sketch this derivation on the whiteboard, you have just won the round.

Three Pointers​

Sometimes two is not enough. Three pointers handle problems like "sort an array of 0s, 1s, and 2s" (the Dutch National Flag problem) or "three-sum."

Code: Dutch National Flag (Sort Colors)

function sortColors(arr) {
  let low = 0, mid = 0, high = arr.length - 1;

  while (mid <= high) {
    if (arr[mid] === 0) {
      [arr[low], arr[mid]] = [arr[mid], arr[low]];
      low++;
      mid++;
    } else if (arr[mid] === 1) {
      mid++;
    } else { // arr[mid] === 2
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
      // Note: do NOT increment mid here — the swapped element needs checking
    }
  }

  return arr;
}

The invariant: everything before low is 0, everything after high is 2, and everything between low and mid is 1. The mid pointer scans the unknown region. When you swap with high, you do not increment mid because the element that came from high has not been examined yet. Missing this detail is the most common bug in this algorithm.

3Sum: Sort, Fix, Two-Pointer, Deduplicate​

The Concept

Given an array of integers, find all unique triplets that sum to zero. The brute force is three nested loops: O(n^3). The optimized approach: sort the array, fix one element, then use two pointers on the remaining subarray to find pairs that sum to the negative of the fixed element. O(n^2) time.

The Trick: Sorting transforms the problem from "find three numbers" to "for each number, find two numbers that sum to its complement." The two-pointer technique from two-sum-on-sorted-array handles the inner loop in O(n). The outer loop runs n times, giving O(n^2) total.

But the real challenge is deduplication. The problem asks for unique triplets. If the array is [-1, -1, 0, 0, 1, 1], you must return [[-1, 0, 1]] — not six copies of the same triplet. Deduplication happens at three levels:

  1. Outer loop: Skip duplicate values for the fixed element. If nums[i] === nums[i-1], skip — you have already found all triplets starting with this value.
  2. Inner loop after finding a match: After recording a triplet, skip duplicate values for both left and right. Keep advancing left while nums[left] === nums[left+1], and similarly for right.
  3. Early termination: If the fixed element is positive, break — no three positive numbers can sum to zero.

Walk through [-1, 0, 1, 2, -1, -4] after sorting: [-4, -1, -1, 0, 1, 2]:

  • i=0, fixed=-4: need two numbers summing to 4. left=1 (-1), right=5 (2). Sum=-1+2=1 < 4, move left. left=2 (-1), right=5 (2). Sum=1 < 4, move left. left=3 (0), right=5 (2). Sum=2 < 4, move left. left=4 (1), right=5 (2). Sum=3 < 4, move left. left=5, left >= right, stop. No triplet for -4.
  • i=1, fixed=-1: need two numbers summing to 1. left=2 (-1), right=5 (2). Sum=1. Found [-1, -1, 2]. Skip duplicates: left moves past -1 to 0, right moves past 2 to 1. left=3 (0), right=4 (1). Sum=1. Found [-1, 0, 1]. Skip duplicates. left=4, right=3, left >= right, stop.
  • i=2, fixed=-1: same as i=1, skip (nums[2] === nums[1]).
  • i=3, fixed=0: positive, break.

Result: [[-1, -1, 2], [-1, 0, 1]].

Code: 3Sum with Full Deduplication

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];

  for (let i = 0; i < nums.length - 2; i++) {
    // Early termination: if the smallest number is positive, no triplet can sum to 0
    if (nums[i] > 0) break;

    // Skip duplicate values for the fixed element
    if (i > 0 && nums[i] === nums[i - 1]) continue;

    let left = i + 1;
    let right = nums.length - 1;
    const target = -nums[i];

    while (left < right) {
      const sum = nums[left] + nums[right];

      if (sum === target) {
        result.push([nums[i], nums[left], nums[right]]);

        // Skip duplicates for left
        while (left < right && nums[left] === nums[left + 1]) left++;
        // Skip duplicates for right
        while (left < right && nums[right] === nums[right - 1]) right--;

        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 1]]

Complexity: O(n^2) time — sorting is O(n log n), the outer loop runs n times, and the inner two-pointer scan is O(n) per iteration. O(1) space (not counting the output array). The deduplication logic is what makes this problem hard. Most candidates get the two-pointer part right. They fail on the duplicate-skipping, return results with repeated triplets, and lose the round. Practice the deduplication until it is automatic.

The Deeper Pattern: 3Sum is the template for all "k-sum" problems. 4Sum? Add another outer loop. 5Sum? Another loop. The core — sort, fix outer elements, two-pointer the innermost pair — scales to any k. Recognizing this family resemblance is what lets you solve a 4Sum problem you have never seen before in under 15 minutes.

Sliding Window: The O(n) Subarray Engine​

The sliding window is the most powerful pattern you will learn in this chapter. It turns problems that look like they need O(n^2) or O(n^3) into clean O(n) solutions. If you master only one pattern from this chapter, make it this one.

The Core Idea​

You maintain a "window" — a contiguous subarray defined by two pointers, left and right. As right expands, you add elements to the window. When the window violates a condition, you shrink from left until it is valid again. The answer is the best valid window you encounter.

Fixed-Size Window​

The window size is given. You slide it across the array, updating the result incrementally.

The Trick: Never recompute from scratch. When the window slides, subtract the element that leaves and add the element that enters.

Code: Maximum Sum Subarray of Size K

function maxSumSubarray(arr, k) {
  let windowSum = 0, maxSum = -Infinity;

  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];

    // Once we have k elements, start sliding
    if (i >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= arr[i - k + 1]; // remove the element leaving the window
    }
  }

  return maxSum;
}

Code: Find All Anagrams in a String (Fixed Window with Frequency Map)

This is the problem that combines sliding window with hashing. Given a string s and a pattern p, find all start indices of p's anagrams in s.

function findAnagrams(s, p) {
  const result = [];
  if (p.length > s.length) return result;

  const pCount = new Array(26).fill(0);
  const windowCount = new Array(26).fill(0);

  // Build frequency map for pattern
  for (const ch of p) {
    pCount[ch.charCodeAt(0) - 97]++;
  }

  for (let i = 0; i < s.length; i++) {
    // Add current character to window
    windowCount[s.charCodeAt(i) - 97]++;

    // Remove character that left the window
    if (i >= p.length) {
      windowCount[s.charCodeAt(i - p.length) - 97]--;
    }

    // Compare window with pattern
    if (i >= p.length - 1) {
      if (arraysEqual(windowCount, pCount)) {
        result.push(i - p.length + 1);
      }
    }
  }

  return result;
}

function arraysEqual(a, b) {
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) return false;
  }
  return true;
}

The arraysEqual check is O(26) = O(1). The overall algorithm is O(n). Compare this to the brute force — checking every substring of length p.length — which would be O(n * m). The sliding window eliminates the redundant work.

Variable-Size Window​

The window size is not fixed. You expand until a condition is met, then shrink to optimize.

The Trick: The right pointer expands the window. The left pointer shrinks it. The condition that triggers shrinking is the key to the algorithm.

Code: Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
  const charIndex = new Map();
  let left = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];

    // If we have seen this character and it is inside the current window
    if (charIndex.has(ch) && charIndex.get(ch) >= left) {
      left = charIndex.get(ch) + 1; // jump left past the previous occurrence
    }

    charIndex.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }

  return maxLen;
}

The key line is left = charIndex.get(ch) + 1. When you encounter a duplicate, you do not just increment left by one — you jump it past the previous occurrence of that character. This is what makes the algorithm O(n) instead of O(2n). The window never shrinks one character at a time; it jumps.

Minimum Window Substring: The Hardest Sliding Window Problem​

The Concept

Given strings s and t, find the minimum window in s that contains all characters of t (including duplicates). Return the empty string if no such window exists.

This is the sliding window problem that appears in senior-level interviews. It combines variable-size window, hash maps, and a clever optimization for checking window validity — all in one problem. If you can solve this on a whiteboard, you have mastered sliding windows.

The Trick: The Expand-Contract Pattern with Two Hash Maps

The algorithm has two phases that alternate:

  1. Expand: Move right forward, adding characters to the window, until the window contains all required characters (it becomes "valid").
  2. Contract: Once valid, move left forward, removing characters, to find the smallest valid window. Stop contracting when the window becomes invalid again.
  3. Repeat until right reaches the end.

The key optimization: instead of comparing two full frequency maps on every iteration (which would be O(26) or O(unique chars) per step), maintain two counters: have (how many unique characters from t are fully satisfied in the current window) and need (how many unique characters t requires). A character is "satisfied" when its count in the window equals or exceeds its count in t. When have === need, the window is valid.

Step-by-step walkthrough for s = "ADOBECODEBANC", t = "ABC":

  • Build tFreq: {A:1, B:1, C:1}. need = 3.
  • right=0, ch='A': windowFreq={A:1}. 'A' count matches tFreq, so have=1.
  • right=1, ch='D': windowFreq={A:1, D:1}. D not in tFreq, have stays 1.
  • right=2, ch='O': windowFreq={A:1, D:1, O:1}. have stays 1.
  • right=3, ch='B': windowFreq={A:1, D:1, O:1, B:1}. 'B' matches, have=2.
  • right=4, ch='E': windowFreq adds E. have stays 2.
  • right=5, ch='C': windowFreq adds C. 'C' matches, have=3. Now have === need — window "ADOBEC" is valid (length 6). Record it.
  • Contract: left=0, remove 'A'. windowFreq={A:0, ...}. 'A' count drops below tFreq, have=2. Window invalid. left=1.
  • right=6, ch='O': have stays 2.
  • right=7, ch='D': have stays 2.
  • right=8, ch='E': have stays 2.
  • right=9, ch='B': windowFreq={B:2, ...}. 'B' already satisfied, have stays 2.
  • right=10, ch='A': windowFreq={A:1, ...}. 'A' matches tFreq again, have=3. Window "BECODEBA" valid (length 8). Not better than 6.
  • Contract: left=1, remove 'D'. have stays 3. Window "ECODEBA" (length 7). Better than 8 but not 6.
  • Contract: left=2, remove 'O'. have stays 3. Window "CODEBA" (length 6). Same as best.
  • Contract: left=3, remove 'B'. windowFreq={B:1}. 'B' still matches tFreq (1 >= 1), have stays 3. Window "ODEBA" (length 5). New best!
  • Contract: left=4, remove 'E'. have stays 3. Window "DEBA" (length 4). New best!
  • Contract: left=5, remove 'C'. windowFreq={C:0}. 'C' drops below tFreq, have=2. Invalid. left=6.
  • right=11, ch='N': have stays 2.
  • right=12, ch='C': windowFreq={C:1}. 'C' matches, have=3. Window "ODEBANC" valid (length 7). Not better than 4.
  • Contract: left=6, remove 'O'. have stays 3. Window "DEBANC" (length 6). Not better.
  • Contract: left=7, remove 'D'. have stays 3. Window "EBANC" (length 5). Not better.
  • Contract: left=8, remove 'E'. have stays 3. Window "BANC" (length 4). Same as best.
  • Contract: left=9, remove 'B'. 'B' drops below tFreq, have=2. Invalid.
  • right reaches end. Best window: "DEBA" or "BANC" (both length 4). Wait — "DEBA" contains D,E,B,A but t="ABC" needs C. Let me re-check... Actually, "DEBA" does not contain C. The correct answer is "BANC" (length 4). The step-by-step above has a subtle error at the contraction phase — when we removed 'C' at left=5, the window became invalid, and we never re-added 'C' until right=12. The correct minimum is "BANC" from indices 9-12. This is exactly why you need to be meticulous with this algorithm — off-by-one errors in the contraction phase are the most common bug.

Let me redo the contraction more carefully. After right=5, window="ADOBEC" (indices 0-5), valid, length 6.

  • Contract left=0: remove 'A'. 'A' count goes from 1 to 0, below required 1. have drops from 3 to 2. Invalid. left=1. Window="DOBEC".
  • Expand right=6 to 9: add O, D, E, B. Window="DOBECODEB". 'B' count goes to 2 (already satisfied). have stays 2.
  • right=10: add 'A'. 'A' count goes to 1, matches required. have=3. Valid. Window="DOBECODEBA" (indices 1-10), length 10. Not better.
  • Contract left=1: remove 'D'. Not in tFreq. have stays 3. Window="OBECODEBA", length 9.
  • Contract left=2: remove 'O'. have stays 3. Window="BECODEBA", length 8.
  • Contract left=3: remove 'B'. 'B' count goes from 2 to 1, still >= 1. have stays 3. Window="ECODEBA", length 7.
  • Contract left=4: remove 'E'. have stays 3. Window="CODEBA", length 6.
  • Contract left=5: remove 'C'. 'C' count goes from 1 to 0, below required 1. have=2. Invalid. left=6. Window="ODEBA".
  • right=11: add 'N'. have stays 2.
  • right=12: add 'C'. 'C' count goes to 1, matches. have=3. Valid. Window="ODEBANC" (indices 6-12), length 7. Not better than 6.
  • Contract left=6: remove 'O'. have stays 3. Window="DEBANC", length 6.
  • Contract left=7: remove 'D'. have stays 3. Window="EBANC", length 5.
  • Contract left=8: remove 'E'. have stays 3. Window="BANC", length 4. New best!
  • Contract left=9: remove 'B'. 'B' count goes from 1 to 0, below required 1. have=2. Invalid. left=10.
  • right reaches end. Best: "BANC" (length 4).

This walkthrough exposes every edge case: characters not in t, characters that appear multiple times, and the delicate have/need counter transitions. Study it until you can reproduce it without looking.

Code: Minimum Window Substring

function minWindow(s, t) {
  if (t.length > s.length) return "";

  const tFreq = new Map();
  for (const ch of t) {
    tFreq.set(ch, (tFreq.get(ch) || 0) + 1);
  }

  const windowFreq = new Map();
  let left = 0;
  let have = 0;        // how many characters we have satisfied
  const need = tFreq.size; // how many unique characters we need to satisfy
  let minLen = Infinity;
  let minStart = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    windowFreq.set(ch, (windowFreq.get(ch) || 0) + 1);

    // If this character is needed and we just hit the required count
    if (tFreq.has(ch) && windowFreq.get(ch) === tFreq.get(ch)) {
      have++;
    }

    // We have a valid window — try to shrink it
    while (have === need) {
      // Update result if this window is smaller
      const windowLen = right - left + 1;
      if (windowLen < minLen) {
        minLen = windowLen;
        minStart = left;
      }

      // Remove leftmost character
      const leftCh = s[left];
      windowFreq.set(leftCh, windowFreq.get(leftCh) - 1);

      if (tFreq.has(leftCh) && windowFreq.get(leftCh) < tFreq.get(leftCh)) {
        have--;
      }

      left++;
    }
  }

  return minLen === Infinity ? "" : s.substring(minStart, minStart + minLen);
}

console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindow("a", "a"));               // "a"
console.log(minWindow("a", "aa"));              // "" (impossible)

Complexity: O(n + m) time where n = s.length and m = t.length. Each character is added once by right and removed at most once by left. The have/need counter optimization avoids comparing full frequency maps. O(k) space where k is the number of unique characters (bounded by the alphabet size).

Why This Problem Is the Ultimate Sliding Window Test: It combines every sliding window concept into one problem — variable-size window, hash map for frequency tracking, a validity condition that is not binary (you need enough of each character, not just any), and the expand-contract rhythm. If you can solve Minimum Window Substring, every other sliding window problem is a special case of this template with a simpler validity condition.

Indian Context: A senior engineer I know got this exact problem at a Bengaluru office of a US-based SaaS company. He wrote the solution in 15 minutes, explained the have/need counter optimization, and handled the edge case where t is longer than s. The interviewer told him afterward that most candidates cannot finish this problem in 45 minutes. He got the offer at ₹85 LPA. The difference was not intelligence. It was pattern recognition — he had practiced the sliding window template until it was muscle memory.

The Universal Sliding Window Template​

Here is a template that works for most sliding window problems. Internalize it:

function slidingWindowTemplate(s) {
  let left = 0;
  let result = 0; // or -Infinity, or [], depending on the problem

  for (let right = 0; right < s.length; right++) {
    // 1. Add s[right] to the window state

    // 2. While the window is INVALID, shrink from the left
    while (/* window is invalid */) {
      // Remove s[left] from the window state
      left++;
    }

    // 3. Window is valid — update the result
    result = Math.max(result, right - left + 1); // or Math.min, or push to array
  }

  return result;
}

The three steps — expand, shrink until valid, update result — cover fixed windows, variable windows, and windows with auxiliary data structures. The only thing that changes is the validity condition and the result update.

The Pattern Recognition System​

You now have five patterns. But knowing them is not enough. You need to recognize which pattern a problem demands, fast. Here is the decision tree I teach every engineer I mentor:

  1. Does the problem ask about subarrays or substrings?

    • If the subarray size is fixed → Fixed Sliding Window
    • If you need the "longest/shortest" subarray satisfying a condition → Variable Sliding Window
    • If you need to count subarrays with a property → Prefix Sum + Hash Map

  2. Is the data sorted, or can you sort it?

    • If yes, and you need pairs → Two Pointers (left-right)
    • If yes, and you need triplets → Two Pointers + outer loop

  3. Do you need fast lookups, frequency counts, or duplicate detection?

    • Hash Map / Hash Set

  4. Does the problem involve a linked list with cycles or middle-finding?

    • Fast-Slow Pointers

  5. Does the problem ask for maximum/minimum contiguous subarray sum?

    • Kadane's Algorithm

  6. Does the problem involve string matching or searching?

    • KMP (if you need all occurrences efficiently)
    • Two Pointers (for palindrome checks)
    • Frequency counting (for anagrams)

Run this decision tree on every problem you practice. At first, it will feel mechanical. After 30-40 problems, it becomes instinct. You will read a problem statement and your brain will flag "sliding window" before you finish the second sentence.

Practice: The 20-Minute Challenge​

Here are five problems. One for each pattern. Set a timer for 20 minutes per problem. If you cannot solve it in 20 minutes, study the solution, then re-solve it from scratch the next day. Repeat until you can solve it in under 15 minutes.

  1. Arrays (Prefix Sum): Subarray Sum Equals K — Given an array of integers and an integer k, return the total number of continuous subarrays whose sum equals k. (LeetCode 560)

  2. Strings (Anagrams): Find All Anagrams in a String — Given two strings s and p, return an array of all the start indices of p's anagrams in s. (LeetCode 438)

  3. Hashing: Longest Consecutive Sequence — Given an unsorted array of integers, return the length of the longest consecutive elements sequence. Must run in O(n) time. (LeetCode 128)

  4. Two Pointers: 3Sum — Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. (LeetCode 15)

  5. Sliding Window: Longest Repeating Character Replacement — Given a string s and an integer k, you can replace at most k characters. Return the length of the longest substring containing the same letter. (LeetCode 424)

Do not just solve these. For each one, write down: (a) which pattern you used, (b) what signal in the problem statement told you to use it, and (c) the time and space complexity of your solution. This meta-analysis is what builds pattern recognition.

But what happens when the problem is not linear? When your data branches, recurses, and connects in ways arrays cannot capture? When the interviewer draws a tree on the whiteboard and asks you to traverse it without recursion, or a graph and asks you to find the shortest path? That is where we go next.