System Design & DSA Masterclass Advanced +300 XP

DSA 20 Interview Patterns

Mastering DSA: 20 Crucial Interview Patterns

Rather than memorizing thousands of LeetCode problems, master **20 foundational patterns**. Understanding these patterns unlocks solutions to 95% of interview questions:

1. Arrays & Two Pointers: Move Zeroes, Product of Array Except Self, Container with Most Water, 3Sum, Valid Palindrome.
2. Sliding Window: Longest Substring Without Repeating Characters (LC 3), Minimum Window Substring (LC 76).
3. Prefix Sum: Subarray Sum Equals K, Range Sum Query.
4. Fast & Slow Pointers: Linked List Cycle I & II, Find Duplicate Number (Floyd's Cycle).
5. Binary Search: Search in Rotated Sorted Array, Find Peak Element, Median of Sorted Arrays.
6. Monotonic Stack: Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram.
7. Heaps & Top K: Top K Frequent Elements, Merge K Sorted Lists, Median from Data Stream.
8. Dynamic Programming: House Robber, LIS, Coin Change, Edit Distance, climbing stairs.

Deep Dive: Sliding Window Pattern

The **Sliding Window** pattern is used to perform operations on a contiguous subarray or substring, optimizing brute-force $O(N^2)$ solutions down to $O(N)$ linear time:

Core Template

int left = 0, right = 0;
while (right < array.length) {
    window.add(array[right]);
    while (window.invalid()) {
        window.remove(array[left]);
        left++;
    }
    maxLength = Math.max(maxLength, right - left + 1);
    right++;
}

Perfect for questions like **Minimum Window Substring** or finding all anagrams within massive input strings.

Deep Dive: Monotonic Stack Pattern

A **Monotonic Stack** maintains its elements in a strict sorted order (strictly increasing or strictly decreasing) as new elements are added:

  • Monotonic Increasing: Stack is sorted ascending. Evict larger elements from the top before pushing the new element. Used to find the **next smaller** element.
  • Monotonic Decreasing: Stack is sorted descending. Evict smaller elements from the top before pushing the new element. Used to find the **next greater** element (e.g. 'Daily Temperatures').