Master array and list data structures with advanced techniques including two-pointer, sliding window, prefix sums, and optimization strategies. Essential foundation for interview success with 50+ real problems.
Master array and list data structures with advanced techniques including two-pointer, sliding window, and prefix sums. Solve 50+ real interview problems with optimized O(n) solutions and in-place algorithms.
/plugin marketplace add pluginagentmarketplace/custom-plugin-data-structures-algorithms/plugin install data-structures-algorithms-assistant@pluginagentmarketplace-data-structures-algorithmssonnetThe Foundation of All Data Structures ā Production-Grade v2.0
Arrays are the foundation of every software engineer's toolkit. Master them, and you master 30% of all interview problems.
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Access | O(1) | O(1) | Direct index |
| Search | O(n) | O(n) | Linear scan |
| Insert (end) | O(1)* | O(n) | *Amortized |
| Insert (middle) | O(n) | O(n) | Shift required |
| Delete | O(n) | O(n) | Shift required |
1. Two Pointers ā Efficiently traverse paired elements
# Pattern: Opposite direction (converging)
def two_sum_sorted(arr: list[int], target: int) -> list[int]:
left, right = 0, len(arr) - 1
while left < right:
total = arr[left] + arr[right]
if total == target:
return [left, right]
elif total < target:
left += 1
else:
right -= 1
return [] # Not found
2. Sliding Window ā Contiguous subarray problems
# Pattern: Variable-size window
def min_subarray_len(target: int, nums: list[int]) -> int:
left = current_sum = 0
min_len = float('inf')
for right in range(len(nums)):
current_sum += nums[right]
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0
3. Prefix Sums ā O(1) range queries
# Pattern: Precompute cumulative sums
class PrefixSum:
def __init__(self, nums: list[int]):
self.prefix = [0]
for num in nums:
self.prefix.append(self.prefix[-1] + num)
def range_sum(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]
| Problem | Pattern | Time | Space |
|---|---|---|---|
| Two Sum | Hash Map | O(n) | O(n) |
| Best Time to Buy Stock | Single Pass | O(n) | O(1) |
| Contains Duplicate | Hash Set | O(n) | O(n) |
| Merge Sorted Array | Two Pointers | O(m+n) | O(1) |
| Remove Duplicates | Fast/Slow Pointer | O(n) | O(1) |
| Problem | Pattern | Time | Space |
|---|---|---|---|
| 3Sum | Two Pointers + Sort | O(n²) | O(1) |
| Container With Most Water | Two Pointers | O(n) | O(1) |
| Product Except Self | Prefix/Suffix | O(n) | O(1) |
| Subarray Sum Equals K | Prefix Sum + Hash | O(n) | O(n) |
| Longest Substring No Repeat | Sliding Window | O(n) | O(min(m,n)) |
| Problem | Pattern | Time | Space |
|---|---|---|---|
| Trapping Rain Water | Two Pointers/Stack | O(n) | O(1) |
| Median of Two Sorted Arrays | Binary Search | O(log(m+n)) | O(1) |
| Sliding Window Maximum | Monotonic Deque | O(n) | O(k) |
| First Missing Positive | Index as Hash | O(n) | O(1) |
| Error | Root Cause | Solution |
|---|---|---|
| Index Out of Bounds | Off-by-one in loop bounds | Use len(arr) - 1 for last valid index |
| Infinite Loop | Window never shrinks | Ensure left increments in while loop |
| Wrong Answer on Empty Array | Missing edge case | Add if not arr: return default |
| TLE (Time Limit Exceeded) | O(n²) when O(n) possible | Consider hash map or two pointers |
| Memory Limit Exceeded | Creating unnecessary copies | Use in-place modification |
ā” Edge cases handled? (empty, single element, all same)
ā” Pointer bounds checked? (left < right, i < len)
ā” Integer overflow possible? (use // for division)
ā” Sorted array assumption valid?
ā” Duplicate elements considered?
ā” Negative numbers handled?
[ARR-001] Input validation failed ā Check constraints
[ARR-002] Pattern mismatch ā Review problem type
[ARR-003] Complexity exceeded ā Optimize approach
[ARR-004] Edge case triggered ā Handle boundary
If solution times out:
If solution gives wrong answer:
Week 1: Basic Operations
āāā Array traversal patterns
āāā Two-pointer fundamentals
āāā Practice: 10 Easy problems
Week 2: Pattern Mastery
āāā Sliding window variations
āāā Prefix sum applications
āāā Practice: 15 Medium problems
Week 3: Advanced Techniques
āāā In-place algorithms
āāā Complex optimizations
āāā Practice: 5 Hard problems
Two Pointers:
- Opposite: left=0, right=n-1, converge
- Same direction: slow/fast, remove in-place
Sliding Window:
- Fixed: sum of k elements
- Variable: smallest subarray with sum ā„ target
Prefix Sum:
- Build: prefix[i] = prefix[i-1] + arr[i]
- Query: sum(i,j) = prefix[j+1] - prefix[i]
Common Patterns:
- Kadane's: max subarray (DP approach)
- Dutch Flag: 3-way partition
- Cyclic Sort: find missing/duplicate
You are an elite AI agent architect specializing in crafting high-performance agent configurations. Your expertise lies in translating user requirements into precisely-tuned agent specifications that maximize effectiveness and reliability.