Algorithmic Problem-Solving Strategies

Hello! Welcome to the first lesson in our module on mixed-pattern interview practice.

In previous modules, you've built a solid foundation by learning individual algorithmic patterns like hashing, two pointers, prefix sums, and sliding windows. Now, we shift our focus from learning the "what" to mastering the "when" and "why." The goal of this lesson is to equip you with a systematic approach to analyze an unfamiliar array or string problem and confidently select the most appropriate and efficient pattern to solve it—a crucial skill for any technical interview. We'll move beyond recognizing a pattern when you're told it's a "sliding window problem" and instead learn to deduce it from the problem statement itself.

Deconstructing the Problem: Your First Look

Before writing any code, the most effective strategy is to deconstruct the problem statement to gather clues. This structured approach helps manage the initial uncertainty—the "algo phobia" you've mentioned—by turning a blank slate into a checklist of observations. A great way to frame this is by looking at three key areas: constraints, input/output formats, and keywords.

The video below offers a fantastic overview of this diagnostic process. As you watch, pay close attention to how each piece of information can help you rule out entire categories of solutions before you even start thinking about the implementation.

This process of elimination is your first line of defense. If an array has 100,000 elements, any brute-force approach that uses nested loops to check all pairs or subarrays ($O(N^2)$) will be too slow. This immediately forces you to consider linear time ($O(N)$) or near-linear time ($O(N\log N)$) solutions, which is precisely where patterns like two pointers, sliding window, and prefix sums operate.

A Decision Framework for Array Problems

Once you've gathered your initial clues, you can use a more targeted decision-making process to choose between the primary array patterns. Think of it as a mental flowchart.

Let's break down the logic behind this flowchart.

1. Contiguous Subarray/Substring?
This is the most important branching question.

• Yes: The problem is about a sequence of elements that are next to each other. This is the prime territory for Sliding Window and Prefix Sums.
• No: The elements can be anywhere in the array. Sliding Window and Prefix Sums are generally not applicable. Your attention should shift to patterns like Two Pointers (if the array is sorted) or general Hashing.

2. If Contiguous, What's the Core Task?

• Longest/Shortest/Minimum/Maximum Window with a Property: If the problem asks for the "longest substring with no repeating characters" or the "smallest subarray with a sum $\ge$ k," you are looking for an optimal window. This is the classic use case for a Sliding Window. The window expands and shrinks to maintain the desired property.
• Counting Subarrays with an Exact Sum: If the problem asks to "count all subarrays that sum to k," the most robust pattern is Prefix Sum + Hash Map. It elegantly handles this requirement in a single pass.

3. What if it's Not Contiguous?

• Sorted Array + Pair/Triplet Finding: If the input array is sorted (or can be sorted without losing necessary information) and you need to find elements that satisfy a sum condition (e.g., a + b = target), Two Pointers converging from opposite ends is an extremely efficient ($O(N)$ time, $O(1)$ space) pattern.
• Frequency/Duplicate Checks: If the problem is about finding duplicates, checking for anagrams, or looking up complements (like in the original Two Sum problem), a Hash Map or Set is your go-to tool for its $O(1)$ average time lookups.

To solidify this framework, the following article provides an excellent "Pattern Selection Guide" and a quick reference list that maps problem descriptions to patterns.

A Critical Distinction: The Role of Negative Numbers

One of the most important "gotchas" that separates these patterns is how they handle negative numbers in sum-based problems.

A dynamic sliding window often relies on a monotonic property: when you shrink the window from the left by removing an element, the sum should predictably decrease (assuming positive numbers). If the array contains negative numbers, removing a negative number from the window increases the sum. This breaks the logic of shrinking to satisfy a constraint, making the sliding window pattern unreliable.

The Prefix Sum + Hash Map pattern, however, works perfectly with negative numbers because it relies on pure arithmetic, not on window-shrinking logic.

Worked Example: Putting It All Together

Let's apply this framework to a classic LeetCode Medium problem: Subarray Sum Equals K (LeetCode 560).

Problem: Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals k.

Step 1: Deconstruct the Problem

• Constraints: The array length can be up to 20,000. Values can be negative. This means an $O(N^2)$ brute-force solution (checking the sum of all $\sim N^2/2$ subarrays) will be too slow. We need an $O(N)$ or $O(N\log N)$ approach.
• Input/Output: Input is an array nums and an integer k. The output is a single integer (the count).
• Keywords: "continuous subarrays," "sum equals k."

Step 2: Apply the Decision Framework

1. Contiguous subarray? Yes, the problem explicitly says "continuous subarrays." This points us toward Sliding Window or Prefix Sums.
2. What's the goal? We need to count subarrays with an exact sum of k.
3. Evaluate the options:
   • Sliding Window? The keywords seem to fit. However, the constraints mention that array values can be negative. As we just learned, this is a major red flag for using a sliding window for a sum-based problem. The logic of shrinking the window breaks. So, we should be very cautious here.
   • Prefix Sum + Hash Map? The keywords "count subarrays with sum = k" are a textbook trigger for this pattern. It works by tracking the cumulative sum as we iterate through the array and using a hash map to see how many times we've previously seen a current_sum - k. This pattern handles negative numbers flawlessly.

Conclusion: The Prefix Sum + Hash Map pattern is the correct and robust choice.

The image below illustrates exactly how this works. As we iterate, we calculate the sum. For each sum, we look for a rem (remainder), where rem = sum - k. The number of times this rem has appeared as a previous prefix sum corresponds to the number of valid subarrays ending at the current position.

Key Takeaways

You've now moved from simply executing a known pattern to strategically selecting one. This is the essence of algorithmic problem-solving in an interview setting.

• Deconstruct First: Always start by analyzing constraints, I/O, and keywords. This initial diagnosis narrows the field of possibilities significantly.
• Use a Decision Framework: Ask systematic questions. Does the problem require contiguous elements? Is the array sorted? Is the goal to find an optimal window or count exact sums?
• Know the Edge Cases: Be aware of limitations, especially the failure of sliding window for sum-based problems with negative numbers. This is what distinguishes an expert from a novice.

In our next lesson, we will continue this practice by applying a similar decision-making framework to a different set of common patterns involving ordered data, intervals, and greedy approaches.