Common Array Patterns
Array patterns are widely used in problem-solving, algorithm design, and data
manipulation. Recognizing and understanding these patterns can significantly
improve efficiency and clarity when working with arrays. Below are some
common array patterns:
1. Sliding Window Pattern
Used for problems involving subarrays or contiguous segments of an array.
When to Use:
o Fixed or variable-length subarrays.
o Summing or finding specific properties of subarrays.
Key Idea: Maintain a "window" of elements and slide it across the array,
updating results incrementally.
Python Example: Maximum sum of a subarray of size kkk.
def max_subarray_sum(arr, k):
max_sum = current_sum = sum(arr[:k])
for i in range(k, len(arr)):
current_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, current_sum)
return max_sum
print(max_subarray_sum([2, 1, 5, 1, 3, 2], 3)) # Output: 9
JavaScript Example:
function maxSubarraySum(arr, k) {
let maxSum = 0, currentSum = 0;
for (let i = 0; i < k; i++) currentSum += arr[i];
maxSum = currentSum;
for (let i = k; i < arr.length; i++) {
currentSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, currentSum);
, }
return maxSum;
}
console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3)); // Output: 9
2. Two Pointers Pattern
Uses two pointers to solve problems on sorted arrays, subarrays, or comparisons.
When to Use:
o Problems involving pairs or subarrays.
o Optimized traversal without nested loops.
Key Idea: Use two pointers to explore different parts of the array.
Python Example: Find a pair that sums to a target.
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return []
print(two_sum_sorted([1, 2, 3, 4, 6], 6)) # Output: [1, 3]
JavaScript Example:
function twoSumSorted(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
const currentSum = arr[left] + arr[right];
Array patterns are widely used in problem-solving, algorithm design, and data
manipulation. Recognizing and understanding these patterns can significantly
improve efficiency and clarity when working with arrays. Below are some
common array patterns:
1. Sliding Window Pattern
Used for problems involving subarrays or contiguous segments of an array.
When to Use:
o Fixed or variable-length subarrays.
o Summing or finding specific properties of subarrays.
Key Idea: Maintain a "window" of elements and slide it across the array,
updating results incrementally.
Python Example: Maximum sum of a subarray of size kkk.
def max_subarray_sum(arr, k):
max_sum = current_sum = sum(arr[:k])
for i in range(k, len(arr)):
current_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, current_sum)
return max_sum
print(max_subarray_sum([2, 1, 5, 1, 3, 2], 3)) # Output: 9
JavaScript Example:
function maxSubarraySum(arr, k) {
let maxSum = 0, currentSum = 0;
for (let i = 0; i < k; i++) currentSum += arr[i];
maxSum = currentSum;
for (let i = k; i < arr.length; i++) {
currentSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, currentSum);
, }
return maxSum;
}
console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3)); // Output: 9
2. Two Pointers Pattern
Uses two pointers to solve problems on sorted arrays, subarrays, or comparisons.
When to Use:
o Problems involving pairs or subarrays.
o Optimized traversal without nested loops.
Key Idea: Use two pointers to explore different parts of the array.
Python Example: Find a pair that sums to a target.
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return []
print(two_sum_sorted([1, 2, 3, 4, 6], 6)) # Output: [1, 3]
JavaScript Example:
function twoSumSorted(arr, target) {
let left = 0, right = arr.length - 1;
while (left < right) {
const currentSum = arr[left] + arr[right];
