Comparing Array and Pointer Patterns
1. Applying Decision Framework
When to Use Array vs Pointer Patterns
- Array Pattern: Use when you need random access, fixed size, or contiguous memory layout. Ideal for scenarios where elements are accessed by index.
- Pointer Pattern: Use when you need dynamic sizing, frequent insertions/deletions, or flexible memory allocation. Suitable for complex data structures like linked lists or trees.
| Pattern | Use Case | Advantages | Disadvantages |
|---|---|---|---|
| Array | Fixed-size data with frequent index-based access | Fast random access, cache-friendly, memory efficient | Fixed size, expensive insertions/deletions in middle |
| Pointer | Dynamic data with frequent modifications | Flexible size, efficient insertions/deletions, memory-efficient for sparse data | Slower random access, more memory overhead, complex to manage |
Decision Framework Steps
- Identify Data Access Patterns: Determine how often elements are accessed by index vs. traversed sequentially.
- Evaluate Memory Constraints: Assess whether fixed memory allocation (arrays) or dynamic allocation (pointers) is more suitable.
- Assess Modification Frequency: Decide if frequent insertions/deletions favor pointer-based structures.
- Consider Performance Requirements: Analyze if cache locality or memory overhead is more critical.
2. Comparing Two Pointers vs Sliding Window
| Pattern | Description | Use Case | Time Complexity |
|---|---|---|---|
| Two Pointers | Uses two indices to traverse the array from both ends towards center. | Searching for a pair of elements that sum to a target, reversing an array. | O(n) |
| Sliding Window | Maintains a window of elements and expands or contracts it based on conditions. | Find maximum/minimum sum subarray, longest substring without repeating characters. | O(n) |
Example: Two Pointers for Pair Sum
function twoSum(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const sum = arr[left] + arr[right];
if (sum === target) return [left, right];
else if (sum < target) left++;
else right--;
}
return [];
}Example: Sliding Window for Max Sum Subarray
function maxSumSubarray(arr, k) {
let windowSum = arr.slice(0, k).reduce((a, b) => a + b, 0);
let maxSum = windowSum;
for (let i = k; i < arr.length; i++) {
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}3. Comparing Fast-Slow Pointers vs Hash Set
| Pattern | Approach | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|---|
| Fast-Slow Pointers | Use two pointers moving at different speeds to detect cycles or find middle elements. | O(n) |
O(1) |
Find cycles in linked lists, detect loop start, find middle element |
| Hash Set | Store visited elements in a set to detect duplicates or cycles. | O(n) |
O(n) |
Detect duplicates, find intersection of arrays, solve problems with frequent lookups |
Example: Detecting Cycle in Linked List
// Fast-Slow Pointers approach
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
// Hash Set approach
function hasCycleWithSet(head) {
const visited = new Set();
let current = head;
while (current) {
if (visited.has(current)) return true;
visited.add(current);
current = current.next;
}
return false;
}When to Use Which?
- Fast-Slow Pointers: When memory is constrained and you want to avoid extra space.
- Hash Set: When frequent lookups or duplicate detection is required and space is not a constraint.
4. Comparing Cyclic Sort vs Hash Map
| Pattern | Description | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|---|
| Cyclic Sort | Used to sort arrays where elements are in range [1, n]. It places each element at its correct index. | O(n) |
O(1) |
Sorting arrays with elements in a known range |
| Hash Map | Uses a hash table to store element frequencies or indices for quick lookup and sorting. | O(n log n) |
O(n) |
General-purpose sorting or frequency counting |
Example: Cyclic Sort
function cyclicSort(arr) {
let i = 0;
while (i < arr.length) {
const correctIndex = arr[i] - 1;
if (arr[i] !== arr[correctIndex]) {
[arr[i], arr[correctIndex]] = [arr[correctIndex], arr[i]];
} else {
i++;
}
}
return arr;
}
const input = [3, 1, 5, 4, 2];
console.log(cyclicSort(input)); // [1, 2, 3, 4, 5]
Example: Hash Map for Frequency Counting
function sortWithHashMap(arr) {
const freqMap = new Map();
for (let num of arr) {
freqMap.set(num, (freqMap.get(num) || 0) + 1);
}
const result = [];
for (let i = 1; i <= arr.length; i++) {
if (freqMap.has(i)) {
result.push(i);
}
}
return result;
}
const input = [3, 1, 5, 4, 2];
console.log(sortWithHashMap(input)); // [1, 2, 3, 4, 5]
Comparison Summary
- Cyclic Sort: Efficient for arrays with elements in range [1, n]. No extra space needed.
- Hash Map: More flexible but uses extra space. Good for general sorting or frequency analysis.
5. Comparing Binary Search Variants
| Variation | Description | Use Case | Time Complexity |
|---|---|---|---|
| Standard Binary Search | Searches for a target value in a sorted array by repeatedly dividing the search interval in half. | Searching for an element in a sorted array | O(log n) |
| Lower Bound Binary Search | Finds the leftmost occurrence of a target value in a sorted array. | Locating insertion point for duplicates | O(log n) |
| Upper Bound Binary Search | Finds the rightmost occurrence of a target value in a sorted array. | Counting occurrences or finding insertion point after last occurrence | O(log n) |
| Rotated Array Search | Searches for a target in a rotated sorted array (e.g., [4,5,6,7,0,1,2]). | Searching in rotated sorted arrays | O(log n) |
| Peak Finding | Finds an element that is greater than or equal to its neighbors in a 1D array. | Identifying local maxima | O(log n) |
Example: Standard Binary Search Implementation
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Example usage:
const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(arr, 7)); // Output: 3Example: Lower Bound Implementation
function lowerBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Example usage:
const arr = [1, 2, 2, 2, 3, 4];
console.log(lowerBound(arr, 2)); // Output: 1Example: Upper Bound Implementation
function upperBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Example usage:
const arr = [1, 2, 2, 2, 3, 4];
console.log(upperBound(arr, 2)); // Output: 4Example: Rotated Array Search
function searchRotated(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
}
// Left half is sorted
if (arr[left] <= arr[mid]) {
if (arr[left] <= target && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// Right half is sorted
if (arr[mid] < target && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
// Example usage:
const rotatedArr = [4, 5, 6, 7, 0, 1, 2];
console.log(searchRotated(rotatedArr, 0)); // Output: 4
Note: The rotated array search variant requires careful handling of the sorted halves to ensure correctness.
6. Comparing Prefix Sum vs Difference Array
| Pattern | Description | Use Case | Time Complexity |
|---|---|---|---|
| Prefix Sum | Precompute cumulative sums for range queries | Fast range sum queries with updates | O(1) for query, O(n) for preprocessing |
| Difference Array | Efficiently apply range updates to an array | Batch updates with minimal recalculation | O(1) for update, O(n) for query |
Example: Prefix Sum for Range Sum Query
const arr = [1, 3, 5, 7, 9];
const prefixSum = [0];
for (let i = 0; i < arr.length; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}
// Range sum from index 1 to 3
const rangeSum = prefixSum[4] - prefixSum[1]; // 15
Example: Difference Array for Range Updates
const diff = new Array(5).fill(0);
const updates = [[1, 3, 2], [2, 4, -1]];
// Apply updates
for (const [start, end, value] of updates) {
diff[start] += value;
if (end + 1 < diff.length) {
diff[end + 1] -= value;
}
}
// Convert back to original array
const result = [diff[0]];
for (let i = 1; i < diff.length; i++) {
result[i] = result[i - 1] + diff[i];
}
Comparison Summary
- Prefix Sum: Best for frequent range sum queries
- Diff Array: Best for frequent range updates
7. Comparing Hash Table vs Two Pointers
| Pattern | Use Case | Time Complexity | Space Complexity | Best For |
|---|---|---|---|---|
| Hash Table | Searching, counting, grouping elements | O(1) average for lookup/insertion | O(n) | Reducing nested loops, frequent lookups |
| Two Pointers | Sorted array problems, subarray sums, palindrome checks | O(n) | O(1) | Memory-constrained environments, sorted data |
Example: Finding Two Sum Using Hash Table
const twoSum = (nums, target) => {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
};Example: Valid Palindrome Using Two Pointers
const isPalindrome = (s) => {
let left = 0;
let right = s.length - 1;
while (left < right) {
if (s[left] !== s[right]) return false;
left++;
right--;
}
return true;
};When to Choose Which
- Hash Table: When you need fast lookups or frequent access to previously seen elements.
- Two Pointers: When working with sorted data and the problem can be solved by moving from both ends towards the center.
8. Evaluating Array Pattern Tradeoffs
| Aspect | Array Pattern | Pointer Pattern |
|---|---|---|
| Memory Access | O(1) for random access |
O(n) in worst case, O(1) for sequential |
| Space Efficiency | Fixed size, potential for unused space | Dynamic allocation, efficient use of memory |
| Insertion/Deletion | O(n) for shifting elements |
O(1) for node manipulation |
| Cache Locality | High due to contiguous memory layout | Lower due to scattered memory locations |
| Flexibility | Fixed size, less flexible for dynamic data | Highly flexible for dynamic data structures |
| Implementation Complexity | Simple, straightforward | More complex due to pointer management |
Example: Performance Comparison
const array = [1, 2, 3, 4, 5];
array.splice(2, 0, 10); // Inserting at index 2 - O(n) operation
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
// Inserting a node - O(1) operation