Arrays Practice & Revision

1. Introduction

What is Array Practice & Revision?

This lesson synthesizes all fundamental array operations and major coding interview patterns into a structured Pattern Recognition Framework.

Why is it Important?

During timed technical interviews, the hardest step isn't writing the code—it's identifying which pattern to apply within the first 3 minutes. Having a decision framework allows you to instantly map problem prompts to optimal O(N) or O(N log N) strategies.

Where is it Used?

Technical Screenings & Onsites: Passing FAANG/Unicorn coding rounds by solving array questions in under 25 minutes.

System Architecture: Choosing optimal memory layouts (sparse arrays, circular buffers, prefix tables) under real-world performance constraints.

---

2. Mental Model

Think of array patterns as a Toolbox of Specialized Keys.

Instead of trying 100 random keys (brute force), you analyze the keyhole features (problem constraints and keywords) to pick the exact right key on the first attempt!

---

3. Concept: The Array Pattern Decision Tree

When presented with any array problem, follow this exact decision workflow:

---

4. Visuals

Pattern Recognition Map

Top 15 Must-Solve Array Interview Problems

---

5. Real-World Examples

Production Refactoring: Converting an O(N²) nested loop scanning transaction windows into a single-pass O(N) sliding window, reducing server CPU utilization from 95% to 4%.

Memory-Constrained Embedded Systems: Applying the Three-Reverse rotation trick to re-orient framebuffer displays in microcontrollers without allocating secondary display buffers.

---

6. Interview Perspective

5-Step Interview Strategy

1. Clarify Constraints (1 min): Ask: "Is the array sorted? Are elements unique? Can numbers be negative? What are N and value limits?" 2. State Brute Force (2 min): State the obvious O(N²) or O(N³) approach. Prove you understand the baseline problem. 3. Identify Bottleneck & Select Pattern (3 min): Point out where redundant work happens. Explain why Two Pointers / Sliding Window / Prefix Sum optimizes it. 4. Code Cleanly (10 min): Write modular code with clear variable names (left, right, currentSum, writeHead). 5. Dry-Run Edge Cases (4 min): Step through your code line-by-line using edge cases: empty array [], single element [1], all negative numbers [-3, -1].

---

7. Summary & Revision Cheat Sheet

---

8. Quiz

Question 1: Which pattern should you use for "Find a contiguous subarray of sum K in an array with negative numbers"?

Answer: Prefix Sum + HashMap. Two pointers and sliding window fail because negative numbers break monotonicity.

Question 2: How do you rotate an array of size N right by K steps in O(N) time and O(1) space?

Answer: 1. K = K \pmod N 2. Reverse entire array (0 to N - 1). 3. Reverse first K elements (0 to K - 1). 4. Reverse remaining elements (K to N - 1).

Question 3: What is the optimal time and space complexity for 3Sum?

Answer: Time: O(N²), Space: O(1) auxiliary (excluding output space) by sorting first and running Two Pointers for each outer loop iteration.

Question 4: In a slow-fast pointer pattern for removing elements in-place, what do the slow and fast pointers represent?

Answer: fast is the reader scanning every position. slow is the writer marking the next valid destination slot in the array.

Question 5: What is the key difference between Kadane's Algorithm and Prefix Sum?

Answer: Kadane's algorithm finds the maximum sum of ANY contiguous subarray in O(N) time. Prefix Sum precomputes cumulative totals to answer SPECIFIC range sum queries [L, R] in O(1) time.