[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":86,"_73":87,"_35":88},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",49,"title","Interview Patterns","slug","algorithms-part-22-interview-patterns","excerpt","Learn interview-focused patterns: two pointers, sliding window, monotonic stack, fast & slow pointers, prefix sums, and the 5-step interview framework.","# Part 22: Algorithm Design Patterns & Interview Prep - The Complete Toolkit\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 40 minutes |\n| Prerequisites | Parts 1-21 (Full series) |\n| Key Concepts | Two Pointers, Sliding Window, Monotonic Stack, Pattern Recognition |\n| Difficulty | ⭐⭐⭐ (Interview-Focused) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ INTERVIEW ALGORITHM PATTERNS │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ TWO POINTERS │ │ SLIDING WINDOW │ │\n│ │ ─────────────── │ │ ─────────────── │ │\n│ │ [→ ... ←] │ │ [═══════► ] │ │\n│ │ Start from ends │ │ Fixed/variable │ │\n│ │ or same side │ │ window size │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ FAST & SLOW │ │ MONOTONIC STACK │ │\n│ │ ─────────────── │ │ ─────────────── │ │\n│ │ 🐢───→ 🐇───→ │ │ [▁▂▃▄▅] always │ │\n│ │ Cycle detection │ │ increasing or │ │\n│ │ middle finding │ │ decreasing │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n│ ┌─────────────────┐ ┌─────────────────┐ │\n│ │ BINARY SEARCH │ │ PREFIX SUMS │ │\n│ │ ON ANSWER │ │ ─────────────── │ │\n│ │ ─────────────── │ │ [a,a+b,a+b+c] │ │\n│ │ If f(x) works, │ │ Range queries │ │\n│ │ does f(x+1)? │ │ in O(1) │ │\n│ └─────────────────┘ └─────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. **Recognize patterns**: Map problems to known techniques\n2. **Apply two pointers**: Solve array/string problems efficiently\n3. **Master sliding window**: Handle substring/subarray problems\n4. **Use monotonic structures**: Next greater/smaller element problems\n5. **Ace interviews**: Systematic problem-solving approach\n\n---\n\n## 🔥 The Interview Approach\n\n### The 5-Step Framework\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ INTERVIEW PROBLEM-SOLVING │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ 1. UNDERSTAND (2-3 min) │\n│ ┌─────────────────────────────────────────────────────┐ │\n│ │ • Restate the problem │ │\n│ │ • Ask clarifying questions │ │\n│ │ • Identify input/output format │ │\n│ │ • Work through example by hand │ │\n│ └─────────────────────────────────────────────────────┘ │\n│ │\n│ 2. MATCH (1-2 min) │\n│ ┌─────────────────────────────────────────────────────┐ │\n│ │ • What pattern does this look like? │ │\n│ │ • What data structures might help? │ │\n│ │ • Have I seen a similar problem? │ │\n│ └─────────────────────────────────────────────────────┘ │\n│ │\n│ 3. PLAN (3-5 min) │\n│ ┌─────────────────────────────────────────────────────┐ │\n│ │ • Describe approach in plain English │ │\n│ │ • Walk through example with approach │ │\n│ │ • Discuss time/space complexity │ │\n│ │ • Get buy-in before coding │ │\n│ └─────────────────────────────────────────────────────┘ │\n│ │\n│ 4. IMPLEMENT (15-20 min) │\n│ ┌─────────────────────────────────────────────────────┐ │\n│ │ • Write clean, readable code │ │\n│ │ • Use meaningful variable names │ │\n│ │ • Talk through your code │ │\n│ │ • Handle edge cases explicitly │ │\n│ └─────────────────────────────────────────────────────┘ │\n│ │\n│ 5. VERIFY (5 min) │\n│ ┌─────────────────────────────────────────────────────┐ │\n│ │ • Trace through with example │ │\n│ │ • Test edge cases │ │\n│ │ • Discuss optimizations │ │\n│ └─────────────────────────────────────────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: Two Pointers\n\n### Pattern 1: Opposite Direction\n\n```java\npublic class TwoPointersOpposite {\n // Two Sum (sorted array)\n public int[] twoSum(int[] nums, int target) {\n int left = 0, right = nums.length - 1;\n\n while (left < right) {\n int sum = nums[left] + nums[right];\n if (sum == target) {\n return new int[]{left, right};\n } else if (sum < target) {\n left++;\n } else {\n right--;\n }\n }\n\n return new int[]{-1, -1};\n }\n\n // Container With Most Water\n public int maxArea(int[] height) {\n int left = 0, right = height.length - 1;\n int maxWater = 0;\n\n while (left < right) {\n int width = right - left;\n int h = Math.min(height[left], height[right]);\n maxWater = Math.max(maxWater, width * h);\n\n // Move the shorter line (it's the bottleneck)\n if (height[left] < height[right]) {\n left++;\n } else {\n right--;\n }\n }\n\n return maxWater;\n }\n\n // Valid Palindrome\n public boolean isPalindrome(String s) {\n int left = 0, right = s.length() - 1;\n\n while (left < right) {\n while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {\n left++;\n }\n while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {\n right--;\n }\n\n if (Character.toLowerCase(s.charAt(left)) !=\n Character.toLowerCase(s.charAt(right))) {\n return false;\n }\n\n left++;\n right--;\n }\n\n return true;\n }\n\n // 3Sum\n public List> threeSum(int[] nums) {\n Arrays.sort(nums);\n List> result = new ArrayList<>();\n\n for (int i = 0; i < nums.length - 2; i++) {\n // Skip duplicates\n if (i > 0 && nums[i] == nums[i - 1]) continue;\n\n int target = -nums[i];\n int left = i + 1, right = nums.length - 1;\n\n while (left < right) {\n int sum = nums[left] + nums[right];\n if (sum == target) {\n result.add(Arrays.asList(nums[i], nums[left], nums[right]));\n\n // Skip duplicates\n while (left < right && nums[left] == nums[left + 1]) left++;\n while (left < right && nums[right] == nums[right - 1]) right--;\n\n left++;\n right--;\n } else if (sum < target) {\n left++;\n } else {\n right--;\n }\n }\n }\n\n return result;\n }\n}\n```\n\n### Pattern 2: Same Direction (Fast & Slow)\n\n```java\npublic class TwoPointersSameDirection {\n // Remove Duplicates from Sorted Array\n public int removeDuplicates(int[] nums) {\n if (nums.length == 0) return 0;\n\n int slow = 0;\n for (int fast = 1; fast < nums.length; fast++) {\n if (nums[fast] != nums[slow]) {\n slow++;\n nums[slow] = nums[fast];\n }\n }\n\n return slow + 1;\n }\n\n // Move Zeroes\n public void moveZeroes(int[] nums) {\n int slow = 0;\n for (int fast = 0; fast < nums.length; fast++) {\n if (nums[fast] != 0) {\n int temp = nums[slow];\n nums[slow] = nums[fast];\n nums[fast] = temp;\n slow++;\n }\n }\n }\n\n // Linked List Cycle Detection (Floyd's)\n public boolean hasCycle(ListNode head) {\n if (head == null) return false;\n\n ListNode slow = head, fast = head;\n\n while (fast != null && fast.next != null) {\n slow = slow.next;\n fast = fast.next.next;\n\n if (slow == fast) return true;\n }\n\n return false;\n }\n\n // Find Cycle Start\n public ListNode detectCycle(ListNode head) {\n ListNode slow = head, fast = head;\n\n // Find meeting point\n while (fast != null && fast.next != null) {\n slow = slow.next;\n fast = fast.next.next;\n if (slow == fast) break;\n }\n\n if (fast == null || fast.next == null) return null;\n\n // Reset one pointer to head\n slow = head;\n while (slow != fast) {\n slow = slow.next;\n fast = fast.next;\n }\n\n return slow;\n }\n\n // Find Middle of Linked List\n public ListNode middleNode(ListNode head) {\n ListNode slow = head, fast = head;\n\n while (fast != null && fast.next != null) {\n slow = slow.next;\n fast = fast.next.next;\n }\n\n return slow;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Sliding Window\n\n### Fixed Size Window\n\n```java\npublic class SlidingWindowFixed {\n // Maximum Sum Subarray of Size K\n public int maxSumSubarray(int[] nums, int k) {\n int windowSum = 0;\n int maxSum = Integer.MIN_VALUE;\n\n for (int i = 0; i < nums.length; i++) {\n windowSum += nums[i];\n\n if (i >= k - 1) {\n maxSum = Math.max(maxSum, windowSum);\n windowSum -= nums[i - k + 1];\n }\n }\n\n return maxSum;\n }\n\n // Find All Anagrams in a String\n public List findAnagrams(String s, String p) {\n List result = new ArrayList<>();\n if (s.length() < p.length()) return result;\n\n int[] pCount = new int[26];\n int[] sCount = new int[26];\n\n for (char c : p.toCharArray()) {\n pCount[c - 'a']++;\n }\n\n for (int i = 0; i < s.length(); i++) {\n sCount[s.charAt(i) - 'a']++;\n\n if (i >= p.length()) {\n sCount[s.charAt(i - p.length()) - 'a']--;\n }\n\n if (i >= p.length() - 1 && Arrays.equals(pCount, sCount)) {\n result.add(i - p.length() + 1);\n }\n }\n\n return result;\n }\n\n // Maximum of All Subarrays of Size K (with Deque)\n public int[] maxSlidingWindow(int[] nums, int k) {\n if (nums.length == 0) return new int[0];\n\n int[] result = new int[nums.length - k + 1];\n Deque deque = new ArrayDeque<>(); // Stores indices\n\n for (int i = 0; i < nums.length; i++) {\n // Remove elements outside window\n while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {\n deque.pollFirst();\n }\n\n // Remove smaller elements (they'll never be max)\n while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {\n deque.pollLast();\n }\n\n deque.offerLast(i);\n\n if (i >= k - 1) {\n result[i - k + 1] = nums[deque.peekFirst()];\n }\n }\n\n return result;\n }\n}\n```\n\n### Variable Size Window\n\n```java\npublic class SlidingWindowVariable {\n // Minimum Window Substring\n public String minWindow(String s, String t) {\n if (s.length() < t.length()) return \"\";\n\n Map need = new HashMap<>();\n Map have = new HashMap<>();\n\n for (char c : t.toCharArray()) {\n need.merge(c, 1, Integer::sum);\n }\n\n int required = need.size();\n int formed = 0;\n int left = 0;\n int minLen = Integer.MAX_VALUE;\n int minLeft = 0;\n\n for (int right = 0; right < s.length(); right++) {\n char c = s.charAt(right);\n have.merge(c, 1, Integer::sum);\n\n if (need.containsKey(c) && have.get(c).equals(need.get(c))) {\n formed++;\n }\n\n // Shrink window\n while (formed == required) {\n if (right - left + 1 < minLen) {\n minLen = right - left + 1;\n minLeft = left;\n }\n\n char leftChar = s.charAt(left);\n have.merge(leftChar, -1, Integer::sum);\n\n if (need.containsKey(leftChar) &&\n have.get(leftChar) < need.get(leftChar)) {\n formed--;\n }\n\n left++;\n }\n }\n\n return minLen == Integer.MAX_VALUE ? \"\" : s.substring(minLeft, minLeft + minLen);\n }\n\n // Longest Substring Without Repeating Characters\n public int lengthOfLongestSubstring(String s) {\n Set seen = new HashSet<>();\n int left = 0;\n int maxLen = 0;\n\n for (int right = 0; right < s.length(); right++) {\n while (seen.contains(s.charAt(right))) {\n seen.remove(s.charAt(left));\n left++;\n }\n\n seen.add(s.charAt(right));\n maxLen = Math.max(maxLen, right - left + 1);\n }\n\n return maxLen;\n }\n\n // Longest Substring with At Most K Distinct Characters\n public int lengthOfLongestSubstringKDistinct(String s, int k) {\n Map count = new HashMap<>();\n int left = 0;\n int maxLen = 0;\n\n for (int right = 0; right < s.length(); right++) {\n count.merge(s.charAt(right), 1, Integer::sum);\n\n while (count.size() > k) {\n char leftChar = s.charAt(left);\n count.merge(leftChar, -1, Integer::sum);\n if (count.get(leftChar) == 0) {\n count.remove(leftChar);\n }\n left++;\n }\n\n maxLen = Math.max(maxLen, right - left + 1);\n }\n\n return maxLen;\n }\n\n // Minimum Size Subarray Sum\n public int minSubArrayLen(int target, int[] nums) {\n int left = 0;\n int sum = 0;\n int minLen = Integer.MAX_VALUE;\n\n for (int right = 0; right < nums.length; right++) {\n sum += nums[right];\n\n while (sum >= target) {\n minLen = Math.min(minLen, right - left + 1);\n sum -= nums[left];\n left++;\n }\n }\n\n return minLen == Integer.MAX_VALUE ? 0 : minLen;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Monotonic Stack/Queue\n\n### Next Greater Element\n\n```java\npublic class MonotonicStack {\n // Next Greater Element\n public int[] nextGreaterElement(int[] nums) {\n int n = nums.length;\n int[] result = new int[n];\n Arrays.fill(result, -1);\n\n Deque stack = new ArrayDeque<>(); // Stores indices\n\n for (int i = 0; i < n; i++) {\n while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {\n result[stack.pop()] = nums[i];\n }\n stack.push(i);\n }\n\n return result;\n }\n\n // Daily Temperatures (days until warmer)\n public int[] dailyTemperatures(int[] temperatures) {\n int n = temperatures.length;\n int[] result = new int[n];\n Deque stack = new ArrayDeque<>();\n\n for (int i = 0; i < n; i++) {\n while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {\n int prevIndex = stack.pop();\n result[prevIndex] = i - prevIndex;\n }\n stack.push(i);\n }\n\n return result;\n }\n\n // Largest Rectangle in Histogram\n public int largestRectangleArea(int[] heights) {\n Deque stack = new ArrayDeque<>();\n int maxArea = 0;\n\n for (int i = 0; i <= heights.length; i++) {\n int h = (i == heights.length) ? 0 : heights[i];\n\n while (!stack.isEmpty() && heights[stack.peek()] > h) {\n int height = heights[stack.pop()];\n int width = stack.isEmpty() ? i : i - stack.peek() - 1;\n maxArea = Math.max(maxArea, height * width);\n }\n\n stack.push(i);\n }\n\n return maxArea;\n }\n\n // Trapping Rain Water\n public int trap(int[] height) {\n Deque stack = new ArrayDeque<>();\n int water = 0;\n\n for (int i = 0; i < height.length; i++) {\n while (!stack.isEmpty() && height[stack.peek()] < height[i]) {\n int bottom = stack.pop();\n if (stack.isEmpty()) break;\n\n int left = stack.peek();\n int width = i - left - 1;\n int h = Math.min(height[left], height[i]) - height[bottom];\n water += width * h;\n }\n stack.push(i);\n }\n\n return water;\n }\n}\n```\n\n### Monotonic Queue\n\n```java\npublic class MonotonicQueue {\n // Maximum in Sliding Window (already shown above)\n\n // Shortest Subarray with Sum at Least K (can have negatives!)\n public int shortestSubarray(int[] nums, int k) {\n int n = nums.length;\n long[] prefix = new long[n + 1];\n\n for (int i = 0; i < n; i++) {\n prefix[i + 1] = prefix[i] + nums[i];\n }\n\n Deque deque = new ArrayDeque<>();\n int minLen = n + 1;\n\n for (int i = 0; i <= n; i++) {\n // Check if we found a valid subarray\n while (!deque.isEmpty() && prefix[i] - prefix[deque.peekFirst()] >= k) {\n minLen = Math.min(minLen, i - deque.pollFirst());\n }\n\n // Maintain increasing order\n while (!deque.isEmpty() && prefix[i] <= prefix[deque.peekLast()]) {\n deque.pollLast();\n }\n\n deque.offerLast(i);\n }\n\n return minLen <= n ? minLen : -1;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Binary Search on Answer\n\n### The Pattern\n\n```java\npublic class BinarySearchOnAnswer {\n // Template for \"minimum possible maximum\" or \"maximum possible minimum\"\n\n // Split Array Largest Sum (minimize the maximum sum)\n public int splitArray(int[] nums, int k) {\n int left = Arrays.stream(nums).max().getAsInt(); // Min possible answer\n int right = Arrays.stream(nums).sum(); // Max possible answer\n\n while (left < right) {\n int mid = left + (right - left) / 2;\n\n if (canSplit(nums, k, mid)) {\n right = mid; // Try smaller max sum\n } else {\n left = mid + 1; // Need larger max sum\n }\n }\n\n return left;\n }\n\n private boolean canSplit(int[] nums, int k, int maxSum) {\n int count = 1;\n int currentSum = 0;\n\n for (int num : nums) {\n if (currentSum + num > maxSum) {\n count++;\n currentSum = num;\n } else {\n currentSum += num;\n }\n }\n\n return count <= k;\n }\n\n // Koko Eating Bananas (minimum speed to finish in H hours)\n public int minEatingSpeed(int[] piles, int h) {\n int left = 1;\n int right = Arrays.stream(piles).max().getAsInt();\n\n while (left < right) {\n int mid = left + (right - left) / 2;\n\n if (canFinish(piles, h, mid)) {\n right = mid;\n } else {\n left = mid + 1;\n }\n }\n\n return left;\n }\n\n private boolean canFinish(int[] piles, int h, int speed) {\n int hours = 0;\n for (int pile : piles) {\n hours += (pile + speed - 1) / speed; // Ceiling division\n }\n return hours <= h;\n }\n\n // Capacity to Ship Packages Within D Days\n public int shipWithinDays(int[] weights, int days) {\n int left = Arrays.stream(weights).max().getAsInt();\n int right = Arrays.stream(weights).sum();\n\n while (left < right) {\n int mid = left + (right - left) / 2;\n\n if (canShip(weights, days, mid)) {\n right = mid;\n } else {\n left = mid + 1;\n }\n }\n\n return left;\n }\n\n private boolean canShip(int[] weights, int days, int capacity) {\n int daysNeeded = 1;\n int currentLoad = 0;\n\n for (int weight : weights) {\n if (currentLoad + weight > capacity) {\n daysNeeded++;\n currentLoad = weight;\n } else {\n currentLoad += weight;\n }\n }\n\n return daysNeeded <= days;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Prefix Sum\n\n```java\npublic class PrefixSumPatterns {\n // Range Sum Query\n public class NumArray {\n private int[] prefix;\n\n public NumArray(int[] nums) {\n prefix = new int[nums.length + 1];\n for (int i = 0; i < nums.length; i++) {\n prefix[i + 1] = prefix[i] + nums[i];\n }\n }\n\n public int sumRange(int left, int right) {\n return prefix[right + 1] - prefix[left];\n }\n }\n\n // Subarray Sum Equals K (count subarrays)\n public int subarraySum(int[] nums, int k) {\n Map prefixCount = new HashMap<>();\n prefixCount.put(0, 1);\n\n int sum = 0;\n int count = 0;\n\n for (int num : nums) {\n sum += num;\n // If prefix[i] - prefix[j] = k, then prefix[j] = prefix[i] - k\n count += prefixCount.getOrDefault(sum - k, 0);\n prefixCount.merge(sum, 1, Integer::sum);\n }\n\n return count;\n }\n\n // Contiguous Array (longest subarray with equal 0s and 1s)\n public int findMaxLength(int[] nums) {\n Map firstSeen = new HashMap<>();\n firstSeen.put(0, -1);\n\n int count = 0; // +1 for 1, -1 for 0\n int maxLen = 0;\n\n for (int i = 0; i < nums.length; i++) {\n count += nums[i] == 1 ? 1 : -1;\n\n if (firstSeen.containsKey(count)) {\n maxLen = Math.max(maxLen, i - firstSeen.get(count));\n } else {\n firstSeen.put(count, i);\n }\n }\n\n return maxLen;\n }\n\n // 2D Prefix Sum\n public class NumMatrix {\n private int[][] prefix;\n\n public NumMatrix(int[][] matrix) {\n int m = matrix.length, n = matrix[0].length;\n prefix = new int[m + 1][n + 1];\n\n for (int i = 0; i < m; i++) {\n for (int j = 0; j < n; j++) {\n prefix[i + 1][j + 1] = matrix[i][j] +\n prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];\n }\n }\n }\n\n public int sumRegion(int r1, int c1, int r2, int c2) {\n return prefix[r2 + 1][c2 + 1] - prefix[r1][c2 + 1] -\n prefix[r2 + 1][c1] + prefix[r1][c1];\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Meet in the Middle\n\n```java\npublic class MeetInTheMiddle {\n // 4Sum Count\n public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {\n Map sumAB = new HashMap<>();\n\n // All sums of A + B\n for (int a : A) {\n for (int b : B) {\n sumAB.merge(a + b, 1, Integer::sum);\n }\n }\n\n // Count complementary sums in C + D\n int count = 0;\n for (int c : C) {\n for (int d : D) {\n count += sumAB.getOrDefault(-(c + d), 0);\n }\n }\n\n return count;\n }\n\n // Closest Subsequence Sum\n public int minAbsDifference(int[] nums, int goal) {\n int n = nums.length;\n\n // Split into two halves\n List left = allSubsetSums(nums, 0, n / 2);\n List right = allSubsetSums(nums, n / 2, n);\n\n Collections.sort(right);\n\n int minDiff = Math.abs(goal);\n\n for (int sum : left) {\n int target = goal - sum;\n\n // Binary search for closest value in right\n int idx = Collections.binarySearch(right, target);\n if (idx < 0) idx = -idx - 1;\n\n if (idx < right.size()) {\n minDiff = Math.min(minDiff, Math.abs(goal - sum - right.get(idx)));\n }\n if (idx > 0) {\n minDiff = Math.min(minDiff, Math.abs(goal - sum - right.get(idx - 1)));\n }\n }\n\n return minDiff;\n }\n\n private List allSubsetSums(int[] nums, int start, int end) {\n List sums = new ArrayList<>();\n int n = end - start;\n\n for (int mask = 0; mask < (1 << n); mask++) {\n int sum = 0;\n for (int i = 0; i < n; i++) {\n if ((mask & (1 << i)) != 0) {\n sum += nums[start + i];\n }\n }\n sums.add(sum);\n }\n\n return sums;\n }\n}\n```\n\n---\n\n## 📊 Pattern Recognition Guide\n\n### Problem → Pattern Mapping\n\n```\n┌──────────────────────────────────────────────────────────────────┐\n│ PATTERN RECOGNITION GUIDE │\n├──────────────────────────────────────────────────────────────────┤\n│ │\n│ \"Find pair/triplet with sum...\" → Two Pointers │\n│ \"Longest/shortest substring/subarray...\" → Sliding Window │\n│ \"Next greater/smaller element...\" → Monotonic Stack │\n│ \"Find cycle in linked list...\" → Fast & Slow │\n│ \"Minimum/maximum possible value...\" → Binary Search │\n│ \"Count subarrays with sum...\" → Prefix Sum + HashMap│\n│ \"All permutations/combinations...\" → Backtracking │\n│ \"Shortest path with constraints...\" → BFS/Dijkstra │\n│ \"Count ways to reach target...\" → DP │\n│ \"Merge sorted structures...\" → Two Pointers/Heap │\n│ \"Top K elements...\" → Heap │\n│ \"Valid parentheses/matching...\" → Stack │\n│ \"Design LRU/LFU cache...\" → HashMap + DLL │\n│ │\n└──────────────────────────────────────────────────────────────────┘\n```\n\n### Data Structure → Use Case\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ DATA STRUCTURE SELECTION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Array: • Fixed size, random access │\n│ • Prefix sums, sliding window │\n│ │\n│ HashMap: • O(1) lookup/insert │\n│ • Counting, grouping, caching │\n│ │\n│ HashSet: • O(1) membership test │\n│ • Deduplication, cycle detection │\n│ │\n│ Stack: • LIFO operations │\n│ • Parsing, backtracking, monotonic problems │\n│ │\n│ Queue: • FIFO operations │\n│ • BFS, level-order traversal │\n│ │\n│ Deque: • Both ends operations │\n│ • Sliding window max/min │\n│ │\n│ Heap: • O(log n) insert, O(1) min/max │\n│ • Top K, merge sorted, Dijkstra │\n│ │\n│ TreeMap: • O(log n) sorted operations │\n│ • Range queries, ceiling/floor │\n│ │\n│ Union-Find: • Near O(1) union/find │\n│ • Connected components, Kruskal │\n│ │\n│ Trie: • Prefix operations │\n│ • Autocomplete, word search │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🐛 Debug This: Sliding Window Bug\n\nThis sliding window solution for \"longest substring with at most 2 distinct characters\" has a bug. Can you find it?\n\n```java\npublic int lengthOfLongestSubstringTwoDistinct(String s) {\n Map count = new HashMap<>();\n int left = 0;\n int maxLen = 0;\n\n for (int right = 0; right < s.length(); right++) {\n count.put(s.charAt(right), count.getOrDefault(s.charAt(right), 0) + 1);\n\n while (count.size() > 2) {\n char leftChar = s.charAt(left);\n count.put(leftChar, count.get(leftChar) - 1);\n // BUG IS HERE\n if (count.get(leftChar) == 0) {\n count.remove(leftChar);\n }\n left++;\n }\n\n maxLen = Math.max(maxLen, right - left + 1);\n }\n\n return maxLen;\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Actually, this code is correct!** The bug hunt was a trick question.\n\nHowever, a common bug in similar code is forgetting to remove the key when count reaches 0:\n\n```java\n// ❌ COMMON BUG: Not removing when count is 0\ncount.put(leftChar, count.get(leftChar) - 1);\n// Forgot: if (count.get(leftChar) == 0) count.remove(leftChar);\n// This causes count.size() to remain > 2 even after shrinking\n\n// The given code is correct because it DOES remove:\nif (count.get(leftChar) == 0) {\n count.remove(leftChar); // ✓ Correct!\n}\n```\n\n**Another common bug** is updating maxLen inside the while loop instead of after:\n\n```java\n// ❌ WRONG: Update inside while loop\nwhile (count.size() > 2) {\n // ... shrink ...\n maxLen = Math.max(maxLen, right - left + 1); // Wrong position!\n}\n\n// ✅ CORRECT: Update after while loop\nwhile (count.size() > 2) {\n // ... shrink ...\n}\nmaxLen = Math.max(maxLen, right - left + 1); // After ensuring valid window\n```\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Longest Repeating Character Replacement ⭐⭐\n\nGiven string s and integer k, find longest substring where you can replace at most k characters to make all same.\n\n```java\npublic int characterReplacement(String s, int k) {\n // Hint: Sliding window with frequency tracking\n}\n```\n\n---\n\n### Exercise 2: Product of Array Except Self ⭐⭐\n\nReturn array where result[i] is product of all elements except nums[i]. No division!\n\n```java\npublic int[] productExceptSelf(int[] nums) {\n // Hint: Prefix and suffix products\n}\n```\n\n---\n\n### Exercise 3: Longest Valid Parentheses ⭐⭐⭐\n\nFind length of longest valid parentheses substring.\n\n```java\npublic int longestValidParentheses(String s) {\n // Multiple approaches: Stack, DP, or Two-pass\n}\n```\n\n---\n\n### Exercise 4: Median from Data Stream ⭐⭐⭐\n\nDesign a data structure that supports addNum() and findMedian() efficiently.\n\n```java\npublic class MedianFinder {\n // Hint: Two heaps\n}\n```\n\n---\n\n### Exercise 5: Sliding Window Median ⭐⭐⭐⭐\n\nFind median of each window of size k.\n\n```java\npublic double[] medianSlidingWindow(int[] nums, int k) {\n // Hint: Two TreeMaps or two heaps with lazy deletion\n}\n```\n\n---\n\n## 🎤 Mock Interview Questions\n\n### Question 1: String Processing\n\n**Problem**: Given a string with parentheses, remove minimum parentheses to make it valid.\n\n**Example**: \"()())()\" → \"()()()\" or \"(())()\"; \"(((\" → \"\"\n\n**Solution approach**:\n```java\npublic String minRemoveToMakeValid(String s) {\n // Pass 1: Mark unmatched ')' with stack\n // Pass 2: Mark unmatched '(' with stack\n // Build result excluding marked indices\n}\n```\n\n---\n\n### Question 2: Array/Two Pointers\n\n**Problem**: Given sorted array, find number of pairs with difference exactly k.\n\n**Example**: [1, 3, 5, 7], k=2 → 3 pairs: (1,3), (3,5), (5,7)\n\n**Follow-up**: What if array isn't sorted?\n\n---\n\n### Question 3: Graph\n\n**Problem**: Clone a graph where nodes have random neighbors.\n\n**Key points**:\n- Use HashMap to track original → clone mapping\n- DFS or BFS traversal\n- Handle cycles (check if already cloned)\n\n---\n\n### Question 4: Design\n\n**Problem**: Design a time-based key-value store that supports set(key, value, timestamp) and get(key, timestamp).\n\n**Key points**:\n- HashMap>>\n- Binary search for get() with timestamp\n- Handle case when no value exists before timestamp\n\n---\n\n### Question 5: DP\n\n**Problem**: Given coin denominations and amount, find number of combinations (not permutations) to make the amount.\n\n**Key insight**: Process coins in outer loop to avoid counting same combination multiple times.\n\n```java\nfor (int coin : coins) {\n for (int amount = coin; amount <= target; amount++) {\n dp[amount] += dp[amount - coin];\n }\n}\n```\n\n---\n\n## 📋 Quick Reference\n\n### Time Complexity Cheatsheet\n\n| Pattern | Typical Time | When to Use |\n|---------|--------------|-------------|\n| Two Pointers | O(n) | Sorted arrays, pair finding |\n| Sliding Window | O(n) | Contiguous subarray/substring |\n| Binary Search | O(log n) | Sorted data, monotonic function |\n| BFS/DFS | O(V + E) | Graph traversal |\n| DP | O(n²) or O(n×m) | Optimization, counting |\n| Heap | O(n log k) | Top K problems |\n| Monotonic Stack | O(n) | Next greater/smaller |\n\n### Interview Checklist\n\n```\nBefore coding:\n□ Understand problem completely\n□ Ask about edge cases\n□ Discuss approach and complexity\n□ Get confirmation to proceed\n\nWhile coding:\n□ Write clean, readable code\n□ Use meaningful names\n□ Handle edge cases\n□ Think out loud\n\nAfter coding:\n□ Trace through example\n□ Test edge cases\n□ Discuss optimizations\n□ Ask if any questions\n```\n\n---\n\n## 🎯 Final Summary\n\n### The Complete Algorithms Compendium Journey\n\n```\nPart 0-1: Foundations → Understanding complexity, recursion\nPart 2-3: Theory → Recursion, Divide & Conquer\nPart 4-7: Sorting → QuickSort to advanced techniques\nPart 8-10: Searching → Binary search, string matching\nPart 11-15: Graphs → Traversal, shortest path, MST, applications\nPart 16-18: Dynamic Programming → Foundations to advanced DP\nPart 19-20: Greedy & Backtracking → When each works\nPart 21: Probabilistic → Bloom filters, HyperLogLog\nPart 22: Interview Patterns → Putting it all together\n```\n\n### Key Takeaways\n\n1. **Pattern recognition** is the most valuable skill\n2. **Practice implementation**, not just understanding\n3. **Analyze complexity** before coding\n4. **Communicate clearly** in interviews\n5. **Test edge cases** systematically\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + practice problems | 90 min |\n| 1 | Pattern recognition guide | 15 min |\n| 3 | Two pointers + sliding window | 30 min |\n| 7 | Mock interview practice | 45 min |\n| 14 | All patterns review | 30 min |\n| 30 | Full mock interview | 60 min |\n\n---\n\n## 🎉 Congratulations!\n\nYou've completed the **Algorithms Compendium: From Theory to Production**.\n\n### What's Next?\n\n1. **Practice**: Solve problems on LeetCode, HackerRank, CodeSignal\n2. **Review**: Use the spaced repetition schedule\n3. **Teach**: Explaining concepts solidifies understanding\n4. **Apply**: Use these patterns in real projects\n\n### Recommended Practice Order\n\n1. Easy problems to build confidence\n2. Medium problems for pattern recognition\n3. Hard problems for interview readiness\n4. Mock interviews for real pressure\n\n---\n\n**Start**: [Part 0: How to Use This Series →](./algorithms-part-0-series-overview.md)\n\n**Full Series**: 23 parts covering algorithms from theory to production\n\n**Total Investment**: ~35 hours for complete mastery\n\n**Your Investment**: Countless opportunities ahead\n\n---\n\n*\"The best time to learn algorithms was 10 years ago. The second best time is now.\"*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.343789Z","createdAt","2026-06-10T07:19:25.344520Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",20,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",22,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":95,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":92,"_73":93,"_35":94},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},209,"Two Pointers","two-pointers",210,"Sliding Window","sliding-window",211,"Monotonic Stack","monotonic-stack",212,"Interview Prep","interview-prep",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]