Sliding Window vs. Two Pointers Engine

Build a Swift pattern classifier that decides between sliding window and two pointers.

Introduction

30 Second Summary

You know that moment in a coding interview when you see an array problem and freeze because it could be sliding window OR two pointers? You are not alone. Most candidates guess based on pattern-matching to problems they have memorized, and when the problem is even slightly novel, they pick wrong.

In this project, you will build a decision engine in a Swift Playground that classifies array and string problems into the correct pattern based on concrete signals. Then you will prove it works by solving problems that trick most candidates into choosing wrong.

What You'll Build

You will run your classifier on a new problem's characteristics, watch it output the correct pattern with a one-sentence explanation, then validate the answer by running a template solution that passes.

By the end of this project, you'll have:

  • A PatternClassifier you can feed any problem's signals into and get back the correct pattern (sliding window fixed, sliding window variable, two pointers opposite, two pointers same-direction, or prefix sum escape hatch) with a confidence explanation.
  • Four gray-zone solutions to problems that genuinely look like either pattern, proving your classifier works against the exact ambiguity that trips candidates up.
  • A monotonic deque implementation for Sliding Window Maximum that demonstrates senior-level data structure selection on top of pattern recognition.
  • Secret Mission: Implement Trapping Rain Water and articulate why it is two pointers despite looking like a window problem.

Are there any prerequisites?

You should be comfortable with Swift syntax and basic array manipulation. You should have seen sliding window and two pointer problems before but struggle with choosing between them. If those terms are brand new, start with an introductory algorithms project first.

Before We Start

Before we dive in, let's lock in what you're about to build and why it matters for your interviews.

Set Up Your Swift Playground

Algorithm practice is most effective when you can write, run, and tweak code in a tight feedback loop. A full Xcode project adds compilation overhead that slows down iteration on small functions.

The #Playground macro gives you inline execution with results displayed right next to your code. In this step, you'll create a Playground file that will house your entire pattern decision engine.

In this step, get ready to:
  • Create a Swift Playground file in Xcode.
  • Add the Playground macro for inline execution.
  • Verify output appears in the canvas.
Create a new Playground file

You need a standalone Swift file with Playground support. Xcode's File menu offers a Playground starting point that scaffolds this for you.

  • Press Cmd+Space to open Spotlight Search.
  • Type Xcode and press Enter to open it.
  • In the menu bar, click File.
  • Select New, then choose the Playground starting point.
  • Name the file PatternDecisionEngine and save it to your Desktop.

You should see an empty Swift file open in the Xcode editor with the #Playground macro already scaffolded.

What is the Playground macro?

The #Playground macro was introduced in Xcode 26. It lets you wrap code in a #Playground { } block inside any Swift file, and Xcode runs it immediately with results shown in the canvas.

This is different from legacy .playground bundles. You get a normal .swift file with full autocomplete and the ability to run snippets inline.

Add imports and the Playground block

The scaffolded file may already have some boilerplate. Replace everything in the file with the following code so you start clean.

  • Select all text in the file and replace it with the following code:
import Foundation
import Playgrounds

#Playground {
    print("Pattern Engine ready")
}

What does this code do?

import Foundation gives you access to Swift's core library (arrays, strings, dictionaries) that you'll use for algorithm implementations.

import Playgrounds enables the #Playground macro so Xcode knows to execute the block and display results in the canvas.

The print("Pattern Engine ready") line is a quick sanity check to confirm execution works before you build anything real.

Verify output in the canvas

The canvas is where Xcode displays your Playground results. Opening it and clicking Resume triggers execution of your #Playground block.

  • In the menu bar, click Editor.
  • Select Canvas to open the canvas panel on the right side.
  • Click the Resume button in the canvas to execute your Playground.

Before you look at the canvas output, what do you expect to see?

You should see Pattern Engine ready printed in the canvas. This confirms Xcode is executing your code and displaying results correctly.

Canvas not showing any output?

Make sure you clicked Resume in the canvas panel. The Playground does not auto-execute until you trigger it.

Check that import Playgrounds is present at the top of your file. Without it, the #Playground macro is not recognized.

If you see a build error, confirm your code matches the snippet above exactly. A missing brace or typo in the import will prevent execution. Help me fix a Playground macro that won't execute in Xcode.

✔️ Awesome, I've got everything!

Great. Double check you've saved the file before moving on.

ⓧ I'd like to double check the full code

Your PatternDecisionEngine.swift should look exactly like this:

import Foundation
import Playgrounds

#Playground {
    print("Pattern Engine ready")
}

Your environment is ready. Next up, you'll build the pattern classifier that codifies the decision rules separating sliding window from two pointers.

Build the Pattern Classifier

Your Playground is running and ready for code. Now comes the core intellectual work of this project: codifying the decision framework that separates sliding window from two pointers.

Writing classification rules forces you to articulate exactly what distinguishes these patterns. That articulation is the skill interviewers test. By the end of this step, you will have a working decision engine that takes problem characteristics as input and outputs the correct pattern.

In this step, get ready to:
  • Define a Pattern enum encoding the five pattern categories with descriptions and invariants.
  • Build a PatternClassifier struct with a decision-tree classify method.
  • Validate the classifier against 5 known problems and confirm correct output.
Define the Pattern enum

The first thing your decision engine needs is a vocabulary. Each pattern category gets a case in a Swift enum, along with two properties: a human-readable description and the invariant that defines it.

  • In PatternDecisionEngine.swift, add the following code between import Playgrounds and the existing #Playground block:
// MARK: - Pattern Classification Engine

enum Pattern: CustomStringConvertible {
    case slidingWindowFixed
    case slidingWindowVariable
    case twoPointersOpposite
    case twoPointersSameDirection
    case prefixSumHash

    var description: String {
        switch self {
        case .slidingWindowFixed: return "Sliding Window (Fixed)"
        case .slidingWindowVariable: return "Sliding Window (Variable)"
        case .twoPointersOpposite: return "Two Pointers (Opposite Ends)"
        case .twoPointersSameDirection: return "Two Pointers (Same Direction)"
        case .prefixSumHash: return "Prefix Sum + Hash Map"
        }
    }
}

What does this code do?

The five cases represent the pattern categories your engine can output. slidingWindowFixed and slidingWindowVariable cover window problems with known vs unknown sizes. twoPointersOpposite and twoPointersSameDirection cover converging vs co-advancing pointers.

The prefixSumHash case is the escape hatch for when neither sliding window nor two pointers applies (negative numbers break both).

  • Click Resume in the canvas. You should still see "Pattern Engine ready" printed, confirming the enum compiles without errors.

Each pattern also needs its invariant stated. The invariant is the one-sentence rule you hold in your head while coding the solution.

  • Add the invariant property inside the Pattern enum, directly below the closing brace of the description property:
    var invariant: String {
        switch self {
        case .slidingWindowFixed:
            return "Maintain a contiguous window of exactly size k, updating state in O(1) per slide."
        case .slidingWindowVariable:
            return "Maintain a contiguous [l..r] window, expand right to find validity, shrink left to optimize."
        case .twoPointersOpposite:
            return "Converge from both ends, moving the pointer that can improve the objective."
        case .twoPointersSameDirection:
            return "Both pointers move forward; one reads, one writes or lags behind."
        case .prefixSumHash:
            return "Precompute cumulative sums, use hash map to find complement for target sum."
        }
    }

Why invariants matter in interviews

An invariant is what stays true on every iteration of your loop. When you can state the invariant, you can prove your solution is correct without tracing every case. Interviewers listen for this.

For example, the variable sliding window invariant tells you the entire algorithm: expand right to find validity, shrink left to optimize. If you can recite that, the code writes itself.

  • Click Resume in the canvas. Confirm you still see "Pattern Engine ready" with no compilation errors.

Seeing a compiler error?

Make sure the invariant property is inside the Pattern enum's closing brace, not outside it. The enum should have one opening { and one closing } with both properties nested inside.

Check that every case in the switch matches the enum cases exactly. help me fix this Pattern enum compiler error

Build the PatternClassifier struct

The classifier takes a set of boolean signals about a problem and runs them through a decision tree. The signals capture what you notice in the first 2 minutes of reading a problem statement.

  • Below the closing } of the Pattern enum (still above the #Playground block), add the PatternClassifier struct with its input type:
struct PatternClassifier {
    struct ProblemSignals {
        let contiguous: Bool
        let windowStateMatters: Bool
        let sorted: Bool
        let optimizingRegion: Bool
        let fixedWindowSize: Bool
        let negativesPresent: Bool
        let pairOrEndpoints: Bool
    }
}

What are these signals?

Each boolean maps to a question you ask when reading a problem:

  • contiguous: Does the answer require a contiguous subarray or substring?
  • windowStateMatters: Do you need to track what is inside the window (frequencies, sums, counts)?
  • sorted: Is the input sorted or does sorting help?
  • pairOrEndpoints: Does the answer depend only on boundary values, not the interior?

Now for the decision tree itself. This is the core logic that maps signals to patterns.

  • Add the classify method inside the PatternClassifier struct, below the closing brace of ProblemSignals:
    static func classify(_ signals: ProblemSignals) -> (pattern: Pattern, reasoning: String) {
        // Escape hatch: negatives break sliding window
        if signals.contiguous && signals.negativesPresent && signals.optimizingRegion {
            return (.prefixSumHash,
                    "Negatives break the monotonic shrink assumption. Use prefix sums + hash map.")
        }
        // Sliding window: contiguous + window state + optimizing
        if signals.contiguous && signals.windowStateMatters && signals.optimizingRegion {
            if signals.fixedWindowSize {
                return (.slidingWindowFixed,
                        "Fixed-size contiguous window with state tracking. Slide and update in O(1).")
            } else {
                return (.slidingWindowVariable,
                        "Variable-size contiguous window. Expand right, shrink left, track best.")
            }
        }
        // Two pointers: pair/endpoint based, no window state
        if signals.pairOrEndpoints && !signals.windowStateMatters {
            if signals.sorted {
                return (.twoPointersOpposite,
                        "Sorted input with pair/endpoint logic. Converge from both ends.")
            } else {
                return (.twoPointersOpposite,
                        "Pair-based objective using boundary values. Converge inward.")
            }
        }
        // Same-direction: in-place modification
        if !signals.contiguous && !signals.optimizingRegion {
            return (.twoPointersSameDirection,
                    "In-place modification or partitioning. One pointer reads, one writes.")
        }
        // Fallback for contiguous optimization
        if signals.contiguous && signals.optimizingRegion {
            return (.slidingWindowVariable,
                    "Contiguous optimization. Default to variable window, verify invariant.")
        }
        return (.twoPointersOpposite,
                "Could not strongly classify. Try two pointers and verify.")
    }

How the decision tree works

The order of checks matters. The negatives escape hatch fires first because it overrides what would otherwise look like a valid sliding window problem. Without this guard, you would apply sliding window to a problem with negative numbers and get a subtle bug.

The core litmus test is: does the data between the pointers matter? If yes (window state matters), it is sliding window. If only the boundary values matter (pair/endpoints), it is two pointers.

  • Click Resume in the canvas. Confirm you still see "Pattern Engine ready" with no errors.

Seeing 'expected declaration' or similar?

Make sure classify is inside the PatternClassifier struct's braces, not outside them. The struct should contain both ProblemSignals and classify.

Also verify the return type uses a tuple: (pattern: Pattern, reasoning: String). help me debug this classify method

Test the classifier against known problems

The decision tree is built. Now you need to prove it works by feeding it signals from 5 well-known problems and checking it returns the correct pattern for each.

  • Find the existing #Playground block at the bottom of your file:
#Playground {
    print("Pattern Engine ready")
}
  • Replace that entire block with the following test cases for the first three problems:
#Playground {
    print("=== Pattern Classifier Tests ===")

    // Test 1: Longest Substring Without Repeating Characters
    let test1 = PatternClassifier.classify(PatternClassifier.ProblemSignals(
        contiguous: true, windowStateMatters: true, sorted: false,
        optimizingRegion: true, fixedWindowSize: false,
        negativesPresent: false, pairOrEndpoints: false))
    print("Longest Substring: \(test1.pattern) - \(test1.reasoning)")

    // Test 2: Two Sum II (Sorted)
    let test2 = PatternClassifier.classify(PatternClassifier.ProblemSignals(
        contiguous: false, windowStateMatters: false, sorted: true,
        optimizingRegion: false, fixedWindowSize: false,
        negativesPresent: false, pairOrEndpoints: true))
    print("Two Sum II: \(test2.pattern) - \(test2.reasoning)")

    // Test 3: Container With Most Water
    let test3 = PatternClassifier.classify(PatternClassifier.ProblemSignals(
        contiguous: false, windowStateMatters: false, sorted: false,
        optimizingRegion: false, fixedWindowSize: false,
        negativesPresent: false, pairOrEndpoints: true))
    print("Container: \(test3.pattern) - \(test3.reasoning)")
}

What signals did we choose for each?

  • Longest Substring Without Repeating Characters: contiguous substring, must track character frequencies (window state), optimizing for longest region. Result: Sliding Window (Variable).
  • Two Sum II: not contiguous (just a pair), sorted input, pair/endpoint logic. Result: Two Pointers (Opposite Ends).
  • Container With Most Water: not contiguous (just two bars), boundary values only. Result: Two Pointers (Opposite Ends).
  • Click Resume in the canvas. You should see the three classifications printed:

"Longest Substring: Sliding Window (Variable)", "Two Sum II: Two Pointers (Opposite Ends)", and "Container: Two Pointers (Opposite Ends)."

  • Now add the final two test cases inside the #Playground block, below the test3 print statement and above the closing }:
    // Test 4: Maximum Average Subarray (Fixed Window)
    let test4 = PatternClassifier.classify(PatternClassifier.ProblemSignals(
        contiguous: true, windowStateMatters: true, sorted: false,
        optimizingRegion: true, fixedWindowSize: true,
        negativesPresent: false, pairOrEndpoints: false))
    print("Max Average: \(test4.pattern) - \(test4.reasoning)")

    // Test 5: Subarray Sum Equals K (with negatives)
    let test5 = PatternClassifier.classify(PatternClassifier.ProblemSignals(
        contiguous: true, windowStateMatters: true, sorted: false,
        optimizingRegion: true, fixedWindowSize: false,
        negativesPresent: true, pairOrEndpoints: false))
    print("Sum = K (negatives): \(test5.pattern) - \(test5.reasoning)")

Why these last two tests matter

Test 4 (Maximum Average Subarray) has fixedWindowSize: true. The problem gives you k upfront, so it is a fixed-size sliding window. This tests a different branch than test 1.

Test 5 (Subarray Sum Equals K with negatives) looks like sliding window (contiguous, optimizing), but the negativesPresent flag triggers the escape hatch. This is the classifier catching a trap that costs candidates their interviews.

Before you click Resume, predict: what pattern will test 5 return? Will it be Sliding Window or something else?

  • Click Resume in the canvas.

You should see all 5 classifications. Test 5 prints "Sum = K (negatives): Prefix Sum + Hash Map" because negatives break the monotonic shrink assumption that sliding window depends on.

Not seeing all 5 results?

Make sure tests 4 and 5 are inside the #Playground { } braces, not after the closing brace. All test code must be inside the macro block to execute.

If you see a compiler error mentioning ProblemSignals, check that all 7 boolean fields are provided in every call. Missing a field causes a compile error. help me fix my classifier test cases

✔️ Awesome, I've got everything!

Great. Double check you have saved your file.

ⓧ I'd like to double check the full code

Scroll through your file and confirm the following sections are present in this order:

  • import Foundation and import Playgrounds at the top.
  • The // MARK: - Pattern Classification Engine comment.
  • The Pattern enum with 5 cases, a description property, and an invariant property.
  • The PatternClassifier struct containing ProblemSignals (7 Bool fields) and the static classify method.
  • The #Playground block with 5 test cases (test1 through test5) and their print statements.

Your decision engine is live and classifying problems correctly. Next up, you will implement the actual template solutions for each pattern and hit a wall that proves why the classifier's escape hatch exists.

Implement the Templates and Hit the Wall

Your classifier can name the right pattern for a given problem. Now you need to prove you can actually implement those patterns.

Templates are table stakes for senior interviews. The real test is whether your implementation handles edge cases that break naive approaches. In this step, you'll implement variable sliding window and opposite-ends two pointers, then deliberately run your sliding window on a problem with negative numbers and watch it produce garbage. That failure is why the classifier has an escape hatch.

In this step, get ready to:
  • Implement a variable sliding window solution for Minimum Size Subarray Sum.
  • Implement an opposite-ends two pointers solution for Two Sum II.
  • Run the sliding window on negative numbers and observe it fail, proving why the escape hatch exists.
Implement the variable sliding window template

The variable sliding window maintains a contiguous subarray [left..right]. It expands right to grow the window until a constraint is met, then shrinks left to optimize the result. You'll use it to solve Minimum Size Subarray Sum: find the shortest subarray whose sum is at least the target.

  • In PatternDecisionEngine.swift, find the closing brace of the PatternClassifier struct (the } just above #Playground).
  • Add the following function between the struct's closing brace and the #Playground block:
// MARK: - Template Implementations

func minSubarrayLen(_ target: Int, _ nums: [Int]) -> Int {
    var left = 0
    var currentSum = 0
    var minLength = Int.max

    for right in 0..<nums.count {
        currentSum += nums[right]
        while currentSum >= target {
            minLength = min(minLength, right - left + 1)
            currentSum -= nums[left]
            left += 1
        }
    }

    return minLength == Int.max ? 0 : minLength
}

What does this code do?

  • left and the loop variable right define the window boundaries. right always advances, expanding the window.
  • The while currentSum >= target loop shrinks from the left once the window satisfies the constraint. This finds the minimum valid window at each position.
  • The shrink-from-left step relies on a critical assumption: removing elements from the left will always decrease the sum. This is the monotonic assumption that makes the algorithm O(n).

Now test it. The function needs a call inside your #Playground block to execute.

  • Inside the #Playground block, find the last print statement (the one for test5). Add the following below it:
    print("\n=== Template Solutions ===")

    let minLen = minSubarrayLen(7, [2, 3, 1, 2, 4, 3])
    print("Min subarray length (target 7): \(minLen)")
  • Click Resume in the canvas to run your playground.

You should see Min subarray length (target 7): 2 in the output. The shortest subarray of [2, 3, 1, 2, 4, 3] that sums to at least 7 is [4, 3], which has length 2.

Not seeing the output?

  • Make sure the new code is placed between the PatternClassifier closing brace and the #Playground block. Functions defined inside #Playground cannot be referenced at the top level.
  • Check that the test call is inside the #Playground { } braces. Code outside the block does not execute in the canvas.

Why isn't my Playground producing output?

Implement the opposite-ends two pointers template

Opposite-ends two pointers starts with one pointer at each end of a sorted array and converges inward. On each step, you compare the result at the two positions and move the pointer that can improve the objective.

  • Add the following function directly below minSubarrayLen (still above the #Playground block):
func twoSumSorted(_ numbers: [Int], _ target: Int) -> [Int] {
    var left = 0
    var right = numbers.count - 1

    while left < right {
        let sum = numbers[left] + numbers[right]
        if sum == target {
            return [left + 1, right + 1]
        } else if sum < target {
            left += 1
        } else {
            right -= 1
        }
    }

    return []
}

What does this code do?

  • left starts at index 0, right starts at the last index. The array must be sorted for this to work.
  • If the sum is too small, move left right (increasing the smaller value). If too large, move right left (decreasing the larger value).
  • The return values are 1-indexed (left + 1, right + 1) to match the standard LeetCode Two Sum II problem format.
  • Add the test call inside your #Playground block, below the minLen print statement:
    let twoSum = twoSumSorted([2, 7, 11, 15], 9)
    print("Two Sum II (target 9): \(twoSum)")
  • Click Resume in the canvas.

You should see Two Sum II (target 9): [1, 2]. In the sorted array [2, 7, 11, 15], positions 1 and 2 (values 2 and 7) sum to 9.

Seeing an empty array instead?

  • An empty result means the while loop exited without finding a match. Check that you passed [2, 7, 11, 15] (sorted) and target 9.
  • Verify the while left < right condition uses < not <=. Using <= would allow the same element to be used twice.

Help me debug my twoSumSorted function

Run the sliding window on negatives and hit the wall

Both templates work on their intended problem types. But what happens when you hand the sliding window a problem it was not designed for?

Before you run the next test, think about this: if the array is [1, -1, 5, -2, 3] and the target sum is 3, what do you think minSubarrayLen will return? The correct shortest subarray is [5, -2, 3] (length 3, sum 6 >= 3) or even [5] (length 1, sum 5 >= 3). Will the sliding window find it?

  • Add this test call at the end of your #Playground block, below the Two Sum II print:
    let badResult = minSubarrayLen(3, [1, -1, 5, -2, 3])
    print("Sliding window with negatives (target 3): \(badResult) (UNRELIABLE)")
  • Click Resume in the canvas.

The output is not 1 (the correct answer, since [5] alone sums to 5 >= 3). The sliding window misses it or returns a wrong length. This is not a bug in your code. It is a fundamental breakdown of the algorithm.

Why do negatives break variable sliding window?

The while currentSum >= target shrink loop relies on a monotonic assumption: removing an element from the left always decreases the sum. With all-positive numbers, this is guaranteed.

With negative numbers, removing a negative value from the left actually increases the sum. The window might shrink past a valid answer, or fail to shrink when it should. The sum is no longer monotone in window length, so the greedy expand/shrink strategy breaks down completely.

This is exactly why your classifier routes negativesPresent: true problems to .prefixSumHash. That escape hatch is not a "nice to have." It is the difference between a correct senior-level answer and a subtle bug that passes most test cases but fails on edge inputs.

✔️ Awesome, I've got everything!

Double check you've saved your file. Your canvas output should show the classifier tests, then Min subarray length (target 7): 2, Two Sum II (target 9): [1, 2], and the unreliable negatives result.

ⓧ I'd like to double check the full code

Your file should have these sections in order. Scroll through and confirm each is present:

  • import Foundation and import Playgrounds at the top.
  • The Pattern enum with description and invariant properties.
  • The PatternClassifier struct with ProblemSignals and classify.
  • // MARK: - Template Implementations followed by minSubarrayLen and twoSumSorted.
  • The #Playground block with 5 classifier tests, the minLen call, twoSum call, and badResult call.

You now have two working templates and hard proof of where one of them breaks. Next up, you'll tackle the gray zone problems that trick senior candidates into picking the wrong pattern.

Solve the Gray Zone Problems

Your classifier can categorize clean-cut problems. But senior interviews rarely give you clean-cut problems.

The problems that trick candidates sit in a "gray zone" where the signals point both ways. In this step, you will solve two of those problems and prove your decision engine handles them correctly.

In this step, get ready to:
  • Implement Container With Most Water using opposite-ends two pointers.
  • Implement Minimum Window Substring using variable sliding window.
  • Articulate the one-sentence decision that locks in each pattern choice.
Implement Container With Most Water

Container With Most Water looks like it might need a window across the array. You are optimizing a region between two bars. But ask the litmus test: does the data between the pointers matter?

The answer is no. The area depends only on height[left] and height[right]. That makes it two pointers.

  • In PatternDecisionEngine.swift, scroll down to below the twoSumSorted function.
  • Add the containerWithMostWater function by copying this code below twoSumSorted:
// MARK: - Gray Zone Problem 1: Container With Most Water (Two Pointers)

func containerWithMostWater(_ height: [Int]) -> Int {
    var left = 0
    var right = height.count - 1
    var maxArea = 0

    while left < right {
        let width = right - left
        let currentHeight = min(height[left], height[right])
        maxArea = max(maxArea, width * currentHeight)

        if height[left] < height[right] {
            left += 1
        } else {
            right -= 1
        }
    }

    return maxArea
}
// Decision: Two Pointers. Data between indices is irrelevant.
// We only evaluate height[left] and height[right].

What does this code do?

The two pointers start at opposite ends of the array. On each iteration they compute the area between them.

  • width is the distance between the pointers. currentHeight is bounded by the shorter bar.
  • Moving the shorter side inward is safe because the taller side can never improve the area. Width is shrinking, and height is capped by the shorter bar.
  • The decision comment at the bottom is the one-sentence proof: "Data between indices is irrelevant."
  • Now add a test for this function inside the #Playground block. Find the closing brace of the Playground and add these lines just before it:
    print("\n=== Gray Zone Problems ===")

    let water = containerWithMostWater([1, 8, 6, 2, 5, 4, 8, 3, 7])
    print("Container With Most Water: \(water)")
  • Click Resume in the canvas.

You should see Container With Most Water: 49 in the output. The maximum area is formed by the bars at indices 1 and 8 (heights 8 and 7, width 7).

Seeing 0 or a wrong number?

  • Check that the if height[left] < height[right] comparison uses < not >. Moving the taller side would skip potential improvements.
  • Make sure maxArea starts at 0 and uses max(maxArea, width * currentHeight) to accumulate.

Why is my Container With Most Water returning a wrong value?

Implement Minimum Window Substring

Minimum Window Substring looks like it could be two pointers. You have a left and a right that move forward. But ask the litmus test again: does the data between the pointers matter?

Yes. You must track every character's frequency inside the window to know whether the window is valid. That window state is the defining signal for sliding window.

  • Below the containerWithMostWater decision comment, start the minWindow function with its setup code:
// MARK: - Gray Zone Problem 2: Minimum Window Substring (Sliding Window)

func minWindow(_ s: String, _ t: String) -> String {
    guard !t.isEmpty else { return "" }

    var need: [Character: Int] = [:]
    for char in t {
        need[char, default: 0] += 1
    }

    let sArray = Array(s)
    var have: [Character: Int] = [:]
    var formed = 0
    let required = need.count

    var left = 0
    var bestRange: (Int, Int)? = nil
    var bestLength = Int.max

What does this setup code do?

  • need counts how many of each character the target string t requires. This is the "validity condition" for the window.
  • have tracks character counts inside the current window. formed counts how many distinct characters have met their required count.
  • bestRange and bestLength remember the smallest valid window found so far.
  • Now add the main sliding window loop and the closing brace directly below the setup code you just added:
    for right in 0..<sArray.count {
        let char = sArray[right]
        have[char, default: 0] += 1

        if let neededCount = need[char], have[char]! == neededCount {
            formed += 1
        }

        // Shrink from left while window is valid
        while formed == required {
            let windowLength = right - left + 1
            if windowLength < bestLength {
                bestLength = windowLength
                bestRange = (left, right)
            }

            let leftChar = sArray[left]
            have[leftChar]! -= 1
            if let neededCount = need[leftChar], have[leftChar]! < neededCount {
                formed -= 1
            }
            left += 1
        }
    }

    guard let range = bestRange else { return "" }
    return String(sArray[range.0...range.1])
}
// Decision: Sliding Window. We track character frequencies across
// the entire window [left..right] to determine validity.

What does this loop do?

  • The outer for right loop expands the window one character at a time. Each new character is added to have.
  • When formed == required, the window contains all needed characters. The inner while loop shrinks from the left to find the smallest valid window.
  • This is the classic variable sliding window invariant: expand right to find validity, shrink left to optimize.
  • Add the test call for minWindow inside the #Playground block, just below the Container With Most Water print line:
    let window = minWindow("ADOBECODEBANC", "ABC")
    print("Minimum Window Substring: \(window)")
  • Click Resume in the canvas to run the Playground.

You should see Minimum Window Substring: BANC in the output. The substring "BANC" (starting at index 9) is the shortest window in "ADOBECODEBANC" that contains all characters from "ABC".

Getting an empty string or a wrong substring?

  • Make sure formed increments only when have[char]! == neededCount (exactly meets the requirement, not exceeds it).
  • Check that required is set to need.count (the number of distinct characters needed), not the total character count.
  • Verify you decrement formed in the shrink loop when have[leftChar]! < neededCount (window just became invalid).

Help me debug my minWindow function.

Verify both solutions and confirm the pattern decisions

Both functions now have decision comments that capture the one-sentence reasoning. Before you move on, think about what your classifier would output for each problem.

Before you click Resume one more time, predict: will the classifier's test3 output ("Container") match the pattern you just implemented? What about test1 ("Longest Substring")?

  • Click Resume and scroll up to the classifier output in the canvas.

You should see Container: Two Pointers (Opposite Ends) from the classifier. And your containerWithMostWater returns 49 while minWindow returns "BANC". The classifier agrees with your implementations.

Why these two problems are the perfect pair

Container With Most Water and Minimum Window Substring both have a left pointer and a right pointer. Both optimize something across a range. A candidate who has memorized templates might reach for sliding window on both.

The difference is one question: does the data between the pointers determine your answer? For Container, no. For Minimum Window, yes. That single question resolves the pattern every time.

✔️ Awesome, I've got everything!

Great. Double check you have saved your file.

ⓧ I'd like to double check the full code

Scroll through your file and confirm each of these sections is present, in order:

  • import Foundation and import Playgrounds at the top.
  • The Pattern enum with 5 cases and the PatternClassifier struct.
  • The minSubarrayLen and twoSumSorted template functions.
  • containerWithMostWater with the Two Pointers decision comment.
  • minWindow with the Sliding Window decision comment.
  • The #Playground block with classifier tests, template tests, and the Gray Zone Problems section printing 49 and "BANC".

Your decision engine now handles the hardest gray zone problems interviewers throw at candidates. Next up, you will tackle the senior-level escalation: Sliding Window Maximum with a monotonic deque.

Sliding Window Maximum with Monotonic Deque

Your classifier correctly separates gray zone problems, and your template solutions prove you can implement each pattern. Pattern recognition is step one. The next question an interviewer asks is: can you choose the right supporting data structure when the basic template is not fast enough?

Sliding Window Maximum is the senior-level escalation of the fixed sliding window pattern. It combines a window of size k with a monotonic deque to maintain the window maximum in O(1) amortized time per element. In this step, you will implement it and prove that data structure selection is the skill that separates senior from mid-level answers.

In this step, get ready to:
  • Understand why the naive O(n*k) scanning approach fails senior-level expectations.
  • Implement maxSlidingWindow using a monotonic deque for O(n) time.
  • Verify the solution produces the correct maximum for every window position.
Understand why naive scanning falls short

The problem: given an array and a window size k, return the maximum value in every contiguous window of size k as it slides across the array.

The naive approach scans all k elements at every window position to find the max. That is O(n*k) total work. For a senior interview, you need O(n).

Why is a plain sliding window not enough?

A basic sliding window can maintain a running sum in O(1) because adding and removing one element from a sum is trivial. But maintaining a running maximum is harder. When you remove the left element and it happens to be the current max, you have no O(1) way to know the new max without rescanning.

A monotonic deque solves this. It stores indices in decreasing order of their values, so the front always holds the index of the current window maximum. Elements that can never be the max for any future window are discarded immediately.

Implement the monotonic deque solution
  • In PatternDecisionEngine.swift, find the comment that says // Decision: Sliding Window. We track character frequencies across (below the minWindow function).
  • Below that comment block, add the following maxSlidingWindow function:
// MARK: - Sliding Window Maximum with Monotonic Deque

func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
    guard !nums.isEmpty && k > 0 else { return [] }

    var result: [Int] = []
    var deque: [Int] = []

    for i in 0..<nums.count {
        while let first = deque.first, first <= i - k {
            deque.removeFirst()
        }

        while let last = deque.last, nums[last] <= nums[i] {
            deque.removeLast()
        }

        deque.append(i)

        if i >= k - 1 {
            result.append(nums[deque.first!])
        }
    }

    return result
}
// Invariant: deque.first is always the index of the maximum element
// in the current window. Elements leave the back when a larger element
// arrives because they can never be the answer for any future window.

What does this code do?

The deque stores indices (not values) in decreasing order of their corresponding array values. On each iteration, three maintenance steps keep the invariant:

  • Remove from the front: any index that has slid out of the current window (first <= i - k).
  • Remove from the back: any index whose value is less than or equal to the current element. Those indices can never be the maximum for this or any future window.
  • Append the current index. Then, once the window is fully formed (i >= k - 1), read the maximum from deque.first!.

💡 Why use an Array as a deque?

Swift's standard library does not include a dedicated Deque type. The swift-collections package provides one, but adding a package dependency would complicate setup without teaching the algorithmic concept.

Using a plain Array with removeFirst(), removeLast(), and append() is the standard interview approach and what interviewers expect to see.

Run the solution and verify
  • Inside the #Playground { } block, find the last line that says print("Minimum Window Substring: \(window)").
  • Below it, add the following test code:
    print("\n=== Sliding Window Maximum (Monotonic Deque) ===")

    let maxWindow = maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)
    print("Max Sliding Window: \(maxWindow)")

What does this test?

The input [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 slides a window of size 3 across 8 elements, producing 6 maximum values. Each window and its max: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5, [-3,5,3]=5, [5,3,6]=6, [3,6,7]=7.

Before you run this, what do you expect the output array to be? Think through the windows manually.

  • Click Resume in the canvas to execute.

You should see Max Sliding Window: [3, 3, 5, 5, 6, 7] printed in the canvas output.

Not seeing the expected output?

  • Confirm the function is placed above the #Playground { } block, not inside it. Functions must be defined at the top level.
  • Check that the deque comparisons use <= not <. Using strict less-than leaves duplicates in the deque and produces wrong results.
  • Verify the window-start condition is i >= k - 1 not i >= k. Off-by-one here skips the first window.

Why is my maxSlidingWindow returning the wrong values?

✔️ Awesome, I've got everything!

Great. Double check you have saved PatternDecisionEngine.swift.

ⓧ I'd like to double check the full code

Your file is now too long to display in one block. Scroll through and confirm these sections appear in order:

  • import Foundation and import Playgrounds at the top.
  • // MARK: - Pattern Classification Engine with the Pattern enum and PatternClassifier struct.
  • // MARK: - Template Implementations with minSubarrayLen and twoSumSorted.
  • // MARK: - Gray Zone Problem 1 with containerWithMostWater.
  • // MARK: - Gray Zone Problem 2 with minWindow.
  • // MARK: - Sliding Window Maximum with Monotonic Deque with maxSlidingWindow and the invariant comment.
  • #Playground { } block calling all tests, ending with maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3) printing [3, 3, 5, 5, 6, 7].

Secret mission

Trapping Rain Water - The Ultimate Gray Zone Problem

Trapping Rain Water looks like a sliding window problem. You are computing water across a contiguous range. But it is actually two pointers. Can you implement it and articulate exactly why?

Clean Up Your Resources

Clean Up Your Resources

Decide whether to keep your resources running, pause them to come back later, or delete them entirely. This project runs entirely locally in Xcode, so there are no ongoing costs.

Resources you used:

  • PatternDecisionEngine.swift Playground file in Xcode.

Keep everything running

No action needed. Choose this if you are still actively building or want to keep the file as an interview prep reference.

  • Your PatternDecisionEngine.swift file stays in Xcode exactly where it is.
  • Revisit it before interviews to refresh your pattern recognition decision tree.
  • No costs accumulate from keeping local files.

Pause - I'll come back to this later

Since this is a local file with no running processes, there is nothing to pause. Your Playground does not consume resources when Xcode is closed.

  • Close the PatternDecisionEngine.swift file in Xcode to free up the editor tab.
  • Quit Xcode if you want to reclaim memory.
  • The file remains on disk and you can reopen it any time.

Delete - I don't want to use this again

Remove the Playground file entirely and start fresh if you ever return to this topic.

  • In Xcode, close the PatternDecisionEngine.swift file.
  • Open Finder and navigate to the location where you saved the file.
  • Drag PatternDecisionEngine.swift to the Trash, then empty the Trash.
  • Alternatively, open Terminal and run the removal command below:
rm ~/Desktop/PatternDecisionEngine.swift

Not sure where you saved it?

Use Spotlight (Cmd+Space) and search for PatternDecisionEngine to locate the file on your Mac.

That's a Wrap!

That's a Wrap!

Nice work. You have built a complete pattern decision engine that transforms the vague "which technique do I use?" question into a systematic, signal-driven classification you can run in your head during any interview.

You've learned how to:

  • Build a PatternClassifier that evaluates problem signals (contiguity, window state, sorting, negatives) and outputs the correct pattern with invariant-driven reasoning.
  • Solve gray-zone problems (Container With Most Water, Minimum Window Substring, Sliding Window Maximum) and articulate the one-sentence decision for why each uses its pattern.
  • Prove why negative numbers break sliding window by experiencing the failure firsthand, then select the correct escape hatch (prefix sum + hash map) using your classifier.
  • Secret Mission: Conquered Trapping Rain Water and explained why it is two pointers despite the window-like appearance.

Ready to quiz yourself?