🎨 Writing Your Own Algorithm: A Fresher's Design Guide ( Final Part )

┌─────────────────────────────────────────────┐
│              HUMAN CREATIVITY               │
├─────────────────────────────────────────────┤
│                                             │
│  1. INTUITION                               │
│     "What if we think of it differently?"   │
│                                             │
│  2. EXPERIMENTATION                         │
│     "Let me try this example by hand..."    │
│                                             │
│  3. PATTERN RECOGNITION                     │
│     "Oh! This is similar to..."             │
│                                             │
│  4. ABSTRACTION                             │
│     "The general principle is..."           │
│                                             │
│  5. REFINEMENT                              │
│     "Can we make this more elegant?"        │
│                                             │
└─────────────────────────────────────────────┘

Novice sees:    "Find product except self"
Expert sees:    "Left products × Right products"

Novice sees:    "Count overlapping meetings"
Expert sees:    "Event timeline with start/end markers"

Novice sees:    "Merge intervals"
Expert sees:    "Sort then scan for adjacent overlaps"

When: Need to scan from both ends or track two positions
Example: Remove duplicates, find pairs

When: Need to process subarrays of varying size
Example: Longest substring, maximum sum subarray

When: Need to track occurrences
Example: Anagrams, duplicates, most frequent element

When: Need cumulative information from left/right
Example: Product except self, range sum queries

When: Problem becomes easier with ordering
Example: Merge intervals, meeting rooms

When: Need to track overlapping intervals
Example: Meeting rooms, calendar scheduling

Input:  [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: [1, 2, 3, 4]

Your design process:
1. Understand: What makes a sequence consecutive?
2. Explore: Try [100] → alone, [4,3,2,1] → sequence of 4
3. Pattern: How to efficiently check if n-1 and n+1 exist?
4. Design: Hash set for O(1) lookup?
5. Optimize: Only start counting from sequence beginnings?

Hint: Use hash set, only count from start of sequences
Time goal: O(n)
Space goal: O(n)

Input:  [1,1,1,2,2,3], k=2
Output: [1,2]

Your design process:
1. Understand: Need both frequency AND ranking
2. Explore: Count frequencies first
3. Pattern: How to get top k from frequencies?
4. Design: Heap? Sorting? Bucket sort?
5. Optimize: Can we do better than O(n log n)?

Hint: Frequency map + min-heap of size k, or bucket sort
Time goal: O(n log k) or O(n)
Space goal: O(n)

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Your design process:
1. Understand: Must contain ALL chars from t (with frequencies)
2. Explore: Sliding window? Expand/contract?
3. Pattern: How to track "valid window"?
4. Design: Two pointers + frequency map?
5. Optimize: When to expand? When to contract?

Hint: Sliding window with character frequency tracking
Time goal: O(n)
Space goal: O(1) for fixed alphabet

┌────────────────────────────────────────────┐
│  Before coding, ask yourself:              │
├────────────────────────────────────────────┤
│  ✓ What's the simplest approach?           │
│  ✓ What pattern does this match?           │
│  ✓ Can sorting help?                       │
│  ✓ Can preprocessing help?                 │
│  ✓ What data structure fits naturally?     │
│  ✓ What's the time-space trade-off?        │
│  ✓ Can I solve a simpler version first?    │
└────────────────────────────────────────────┘

Problem Statement
      ↓
  Understand (examples, edge cases)
      ↓
  Explore (manual solution)
      ↓
  Pattern (what repeats?)
      ↓
  Design (choose approach)
      ↓
  Implement (write code)
      ↓
  Optimize (improve complexity)
      ↓
  Test (verify correctness)

The Loop:
  Problem → Creativity → Algorithm → Solution
     ↑                                  ↓
     └──────── Learn & Improve ─────────┘