Array Patterns

This file lists all commonly used array patterns for DSA problems, along with typical problem types and keywords. Once you read this deeply, the keywords and use cases should stay in your mind as a mental map for solving problems efficiently. Focus on pattern recognition first, then the implementation.

Pattern Table (Simplified & Prioritized)

Pattern / Category	Typical Question Types	Keywords	Notes / Use Case / Rarity
Sliding Window (Fixed / Dynamic)	Max/min sum subarray, Longest substring, Min window substring	contiguous, subarray, window, smallest/largest	Expand/shrink window; O(n) optimal; universal for arrays & strings
Two Pointers	Pair sum, Triplets, Triplets with sum/target	pair, triplet, start/end	Reduces O(n²) → O(n) on sorted arrays; also works on linked lists
Prefix Sum / Hashing	Range sum queries, Subarray sum equals k	sum of range, cumulative, frequency, lookup	Precompute cumulative sum; combine with hashmaps; O(1) query after O(n) prep
Kadane’s Algorithm	Maximum subarray sum, Max profit	contiguous max sum, max profit	Sliding sum approach; handles negatives efficiently; often combined with DP
Partition / Dutch National Flag	Sort colors, Segregate elements	in-place, sort 0/1/2	Swap elements in-place; one-pass linear scan; ideal for constrained memory
Binary Search / Quick Select / Heap	Search element, Rotated sorted array, Kth largest/smallest	sorted, minimum, maximum, find target, top k	Divide & conquer; O(log n) search; heap or partition for selection problems
Merge Intervals	Interval scheduling, Merge overlapping intervals	merge, overlapping, schedule	Sort + linear scan; standard for calendar, booking, or interval problems
Sliding Window Maximum (Deque)	Max/min in every subarray of size k	max/min, window of size k	Use deque to maintain candidates; O(n) efficient scan for each window
Difference Array (Bonus / Rare)	Range update queries	update, range	O(1) range updates; ideal for cumulative updates in array segments
XOR Patterns (Bonus / Rare)	Single number, Pair XOR, Subarrays	XOR, unique, subset	Bitwise operations; often combined with hashmaps or prefix XOR technique

---

Mini Notes / Tips

### Tips

- Always start with a brute-force solution to understand the problem.
- Sliding window frequently overlaps with two pointers; check for “contiguous” or “window” keywords.
- Prefix sums + hashmaps is a common combo for subarray sum queries.
- Kadane’s algorithm is essentially a sliding window for max sum with negative numbers.
- Partition/Dutch flag patterns are frequent in constrained memory or in-place problems.
- Binary search/Quick select/Heap patterns appear in sorted or selection problems; know both approaches.
- Merge intervals and deque-based sliding windows are DS-specific but appear in coding interviews regularly.
- Difference arrays and XOR patterns are rare but important for specialized problems.

Array Patterns – Detection & Usage Guide

1. Sliding Window (Fixed / Dynamic) – Common (Arrays & Strings)

When to use / Detection cues:

• Input structure: Array or string, usually linear, may require contiguous subarrays or substrings.
• Question keywords: contiguous, subarray, window, smallest/largest, longest.
• Problem hints: Maximum/minimum sum or product in a subarray, longest substring with constraints (unique characters, k distinct elements, etc.), minimum window substring containing all characters.
• Why it works: You expand the window to include elements, shrink it to maintain constraints. Optimizes brute-force O(n²) → O(n).

Typical questions:

• Max sum subarray of size k
• Longest substring without repeating characters
• Minimum window substring containing all pattern characters

Mental trigger: “Contiguous” + “optimal in linear time” → Sliding Window.

---

2. Two Pointers – Common (Arrays & Strings)

When to use / Detection cues:

• Input structure: Sorted array, string, or linked list. Sometimes unsorted but can sort.
• Question keywords: pair, triplet, start/end, sum, target, sorted.
• Problem hints: Find pairs or triplets satisfying sum/condition, remove duplicates, reverse sections, or move elements meeting certain criteria.
• Why it works: Reduces O(n²) → O(n) for pair/triplet problems by moving two pointers toward each other.

Typical questions:

• Two-sum in sorted array
• Triplets with sum = 0
• Remove duplicates or partition array

Mental trigger: “Start/end” pointers moving inward → Two Pointers.

---

3. Prefix Sum / Hashing – Common (Arrays & Strings)

When to use / Detection cues:

• Input structure: Linear array or string, multiple queries on ranges or sums.
• Question keywords: sum, cumulative, frequency, lookup, subarray sum k.
• Problem hints: Repeated subarray sum queries, contiguous subarray sums, counting patterns efficiently.
• Why it works: Precompute cumulative sums (prefix array) or store counts in hashmap to achieve O(1) range queries or O(n) for counting.

Typical questions:

• Subarray sum equals k
• Range sum queries
• Count subarrays with given XOR

Mental trigger: “Range sum” + “multiple queries” → Prefix Sum / Hashing.

---

4. Kadane’s Algorithm – Common (Arrays / DP)

When to use / Detection cues:

• Input structure: Linear array, can have negative numbers.
• Question keywords: max contiguous sum, max profit, max subarray.
• Problem hints: Need the maximum sum of consecutive elements; simple sliding window fails with negatives.
• Why it works: Maintain running sum and track max, reset when sum < 0. Handles negatives efficiently.

Typical questions:

• Maximum subarray sum
• Max profit from stock prices (single transaction)
• Max sum circular subarray (variation)

Mental trigger: “Max contiguous sum” → Kadane’s Algorithm.

---

5. Partition / Dutch National Flag – Common (Arrays only)

When to use / Detection cues:

• Input structure: Array of small range integers or categories (like 0/1/2).
• Question keywords: sort in-place, reorder, segregate, partition, colors.
• Problem hints: Need in-place rearrangement by category, often O(n) and single pass.
• Why it works: Two or three pointers swap elements to correct partition efficiently.

Typical questions:

• Sort colors (0/1/2)
• Segregate even/odd
• Move all zeros to end

Mental trigger: “Reorder in-place” + “small number of categories” → Partition / Dutch National Flag.

---

6. Binary Search / Quick Select / Heap – Common (Arrays / Heap)

When to use / Detection cues:

• Input structure: Sorted array or need k-th largest/smallest.
• Question keywords: sorted, find target, kth largest/smallest, top k, minimum, maximum.
• Problem hints: Search efficiently in sorted data, find threshold/min-max satisfying condition.
• Why it works: Divide and conquer (binary search), or heap for selection problems.

Typical questions:

• Search in rotated sorted array
• Find kth largest element
• Minimize maximum in array split problems

Mental trigger: “Sorted” or “top k” → Binary Search / Heap / Quick Select.

---

7. Merge Intervals – Common (Arrays only)

When to use / Detection cues:

• Input structure: Array of intervals [start, end].
• Question keywords: merge, overlapping, schedule, interval.
• Problem hints: Merge or count overlapping intervals, schedule tasks without conflict.
• Why it works: Sort by start time, then linear scan to merge or check conflicts.

Typical questions:

• Merge overlapping intervals
• Meeting room problems
• Maximum number of non-overlapping intervals

Mental trigger: “Intervals” + “overlap/merge” → Merge Intervals.

---

8. Sliding Window Maximum (Deque) – Common (Arrays only)

When to use / Detection cues:

• Input structure: Array, need max/min in subarray of size k.
• Question keywords: window of size k, max/min, sliding window.
• Problem hints: O(n) solution needed; naive O(nk) too slow.
• Why it works: Maintain a deque of candidates; always keep the largest (or smallest) at front.

Typical questions:

• Max in every subarray of size k
• Min in sliding window problem

Mental trigger: “Max/min in subarray of size k” → Sliding Window (Deque).

---

9. Difference Array – Rare (Arrays only)

When to use / Detection cues:

• Input structure: Array with multiple range update queries.
• Question keywords: update range, increment subarray, modify range.
• Problem hints: Many updates + need final array values efficiently.
• Why it works: Apply delta at start and end+1, then take prefix sum for final array.

Typical questions:

• Range addition/subtraction
• Increment subarray values multiple times efficiently

Mental trigger: “Multiple range updates” → Difference Array.

---

10. XOR Patterns – Rare (Arrays & Graphs)

When to use / Detection cues:

• Input structure: Array, usually integers; sometimes tree/graph for path XOR.
• Question keywords: XOR, unique, single number, subset XOR.
• Problem hints: Detect single element, pairs, or subarrays using XOR properties.
• Why it works: XOR of same numbers = 0, XOR is associative; can be combined with prefix XOR or hashmaps.

Typical questions:

• Single non-repeating number
• Count subarrays with given XOR
• Find two numbers in array with XOR = target

Mental trigger: “XOR” + “unique/single” → XOR Patterns.