“Scan once. Maintain minimal state. Compute answer incrementally.”

• Single pass (or fixed small passes)
• No dynamic resizing window
• No auxiliary data structure needed
• You maintain 1–3 running variables
• Answer builds as you scan

• “maximum / minimum”
• “count”
• “running”
• “track”
• “difference”
• “scan array”

30 MUST-DO INTERVIEW PROBLEMS

EASY (1–10): Traversal Muscle Memory

1. #
   LC #1920 — Build Array from Permutation - COMPLETED
2. #
   LC #1480 — Running Sum of 1D Array - COMPLETED
3. #
   LC #2011 — Final Value of Variable After Operations - COMPLETED
4. #
   LC #2114 — Maximum Number of Words Found in Sentences - COMPLETED
5. #
   LC #485 — Max Consecutive Ones - COMPLETED
6. #
   LC #724 — Find Pivot Index - COMPLETED
7. #
   GFG — Find Largest Element in Array - COMPLETED
8. #
   GFG — Second Largest Element - COMPLETED
9. #
   GFG — Leaders in an Array - COMPLETED
10. #
    GFG — Check if Array Is Sorted - COMPLETED

️ MEDIUM (11–20): Multi-Variable State Control

1. #
   LC #53 — Maximum Subarray - COMPLETED
2. #
   LC #121 — Best Time to Buy and Sell Stock (1 Transaction) - COMPLETED
3. #
   LC #169 — Majority Element - COMPLETED
4. #
   LC #665 — Non-decreasing Array
5. #
   LC #283 — Move Zeroes - COMPLETED
6. #
   GFG — Equilibrium Point - COMPLETED
7. #
   LC #152 — Maximum Product Subarray - COMPLETED
8. #
   LC #845 — Longest Mountain in Array - COMPLETED
9. #
   LC #674 — Longest Continuous Increasing Subsequence - COMPLETED
10. #
    LC #2765 — Longest Alternating Subarray - COMPLETED

• Clean reset logic
• Handling negatives
• Maintaining 2–3 states simultaneously

HARD (21–30): Traversal Under Pressure

1. #
   LC #122 — Best Time to Buy and Sell Stock II - COMPLETED
2. #
   LC #918 — Maximum Sum Circular Subarray - COMPLETED
3. #
   LC #238 — Product of Array Except Self - COMPLETED
4. #
   LC #414 — Third Maximum Number - COMPLETED
5. #
   LC #1014 — Best Sightseeing Pair - COMPLETED
6. #
   LC #1566 — Detect Pattern of Length M Repeated K or More Times - COMPLETED - COMPLETED
7. #
   LC #896 — Monotonic Array - COMPLETED - COMPLETED
8. #
   LC #1752 — Check if Array Is Sorted and Rotated - COMPLETED - COMPLETED
9. #
   LC #1800 — Maximum Ascending Subarray Sum - COMPLETED - COMPLETED
10. #
    LC #2012 — Sum of Beauty in the Array - COMPLETED - COMPLETED

• Absolute control over running state
• Edge-case maturity
• No panic resets

The ONE Rule That Wins Interviews

“What variables am I maintaining and why?”

Common Interview Killers

• Overcomplicating simple scans
• Using extra arrays unnecessarily
• Reset logic mistakes
• Forgetting edge cases (all negatives, single element, etc.)

1️⃣ Pattern in One Line

"Scan the array once, maintain 1–3 running variables, build the answer incrementally."

2️⃣ Recognize It When...

• Single pass is enough
• No extra data structure needed
• You're tracking running max/min/sum/count
• Trigger words: "scan", "track", "running", "difference", "maximum/minimum"
• Constraints hint O(N) time, O(1) space

3️⃣ Don't Confuse With...

• Prefix Sum (P3) → when you need range queries
• Sliding Window (P4) → when window boundaries move dynamically
• Hashing (P2) → when you need fast lookups of past values

4️⃣ Approach in 3 Steps

1. #
   Identify what variables to maintain (max, min, sum, count, reset trigger)
2. #
   Define reset condition clearly — when does state restart?
3. #
   Update answer at every step or at the end

5️⃣ Invariant to Maintain

"At every index i, my variables correctly represent the best answer for arr[0..i]."

6️⃣ Complexity to Justify

• Time: O(N) — single pass
• Space: O(1) — only variables, no extra arrays
• Why: No nested loops, no recursion, no auxiliary structures

7️⃣ Edge Cases to Always Check

• Empty array
• Single element array
• All elements same
• All elements negative
• Array of length 2

8️⃣ One Line to Say in Interview

"This is a pure traversal — I'll maintain running state variables and update the answer incrementally in O(N) time and O(1) space."

“Just traversal. Maintain state.”