Exploring Essential Programming Patterns

In computer science, mastering common programming patterns can greatly enhance your problem-solving skills. This article explores a variety of patterns—from simple techniques like prefix sums to more complex methods like backtracking—each useful in different types of challenges.

1. Prefix Sum

Overview: The prefix sum technique involves computing the cumulative sum of an array (or other sequence), enabling you to answer range sum queries efficiently.

Use Cases:

• Range query problems
• Calculating moving averages
• Solving dynamic programming challenges

Example (JavaScript):

function prefixSums(arr) {
  const prefix = [0];
  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[i] + arr[i]);
  }
  return prefix;
}

const arr = [1, 2, 3, 4];
console.log(prefixSums(arr)); // [0, 1, 3, 6, 10]

2. Two Pointers

Overview: The two pointers technique uses two indices to traverse data structures, often from different ends or at different speeds.

Use Cases:

• Finding pairs that sum to a specific value
• Merging sorted arrays
• Removing duplicates

Example (JavaScript):

function twoSumSorted(arr, target) {
  let left = 0,
    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 [];
}

console.log(twoSumSorted([1, 2, 3, 4, 6], 7)); // [0, 3]

3. Sliding Window

Overview: This pattern involves maintaining a window that slides over the data to calculate values over subarrays or substrings dynamically.

Use Cases:

• Finding the maximum/minimum sum subarray
• Solving substring problems in strings
• Real-time data processing

Example (JavaScript):

function maxSubarraySum(arr, k) {
  let maxSum = 0,
    currentSum = 0;
  for (let i = 0; i < arr.length; i++) {
    currentSum += arr[i];
    if (i >= k - 1) {
      maxSum = Math.max(maxSum, currentSum);
      currentSum -= arr[i - (k - 1)];
    }
  }
  return maxSum;
}

console.log(maxSubarraySum([1, 4, 2, 10, 23, 3, 1, 0, 20], 4)); // 39

4. Linked List Reversal

Overview: Reversing a linked list is a common pattern where you reverse the pointers of a linked list to change the order of its nodes.

Use Cases:

• Reordering data
• Solving problems in interviews
• Manipulating data structures

Example (JavaScript):

function reverseLinkedList(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

5. Monotonic Stack

Overview: A monotonic stack is maintained in either increasing or decreasing order. It is useful for solving problems that require finding the next greater or smaller element.

Use Cases:

• Stock span problems
• Finding nearest greater/smaller elements
• Histogram problems

Example (JavaScript):

function nextGreaterElements(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = [];
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
      result[stack.pop()] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElements([2, 1, 2, 4, 3])); // [4, 2, 4, -1, -1]

6. Top K Elements

Overview: This pattern involves finding the top K elements in a dataset, which is often done using heaps.

Use Cases:

• Ranking or sorting problems
• Real-time data analysis
• Recommendation systems

Example (JavaScript using a Min-Heap):

class MinHeap {
constructor() {
this.heap = [];
}

insert(val) {
this.heap.push(val);
this.bubbleUp();
}

bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.heap[index] >= this.heap[parent]) break;
[this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]];
index = parent;
}
}

extractMin() {
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown(0);
}
return min;
}

sinkDown(index) {
const length = this.heap.length;
const element = this.heap[index];
while (true) {
let left = 2 _ index + 1;
let right = 2 _ index + 2;
let swap = null;
if (left < length && this.heap[left] < element) swap = left;
if (right < length && this.heap[right] < (swap === null ? element : this.heap[left])) swap = right;
if (swap === null) break;
[this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
index = swap;
}
}
}

function topKElements(arr, k) {
const heap = new MinHeap();
for (let num of arr) {
heap.insert(num);
if (heap.heap.length > k) {
heap.extractMin();
}
}
return heap.heap;
}

console.log(topKElements([3, 1, 5, 12, 2, 11], 3)); // [3, 11, 12] (order may vary)

7. Overlapping Intervals

Overview: This pattern deals with merging or processing intervals that overlap, a common task in scheduling problems.

Use Cases:

• Merging meeting times
• Booking systems
• Calendar applications

Example (JavaScript):

function mergeIntervals(intervals) {
  if (!intervals.length) return intervals;
  intervals.sort((a, b) => a[0] - b[0]);
  const merged = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = merged[merged.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      merged.push(intervals[i]);
    }
  }
  return merged;
}

console.log(
  mergeIntervals([
    [1, 3],
    [2, 6],
    [8, 10],
    [15, 18],
  ]),
); // [[1,6],[8,10],[15,18]]

8. Modified Binary Search

Overview: A twist on the classic binary search, this pattern is adapted to find answers in a modified or constrained search space.

Use Cases:

• Finding a peak element
• Searching in rotated sorted arrays
• Optimization problems where a decision function is monotonic

Example (JavaScript - Finding Peak Element):

function findPeakElement(nums) {
  let left = 0,
    right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] < nums[mid + 1]) left = mid + 1;
    else right = mid;
  }
  return left;
}

console.log(findPeakElement([1, 2, 3, 1])); // 2

9. Depth-First Search (DFS)

Overview: DFS is a graph traversal technique that explores as far as possible along each branch before backtracking.

Use Cases:

• Solving puzzles like mazes
• Topological sorting
• Connected components in graphs

Example (JavaScript):

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);
  for (let neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

const graph = {
  A: ["B", "C"],
  B: ["D", "E"],
  C: ["F"],
  D: [],
  E: ["F"],
  F: [],
};

dfs(graph, "A");

10. Breadth-First Search (BFS)

Overview: BFS explores a graph layer by layer, making it ideal for finding the shortest path in unweighted graphs.

Use Cases:

• Shortest path problems
• Level order traversal in trees
• Social network analysis

Example (JavaScript):

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  while (queue.length) {
    const vertex = queue.shift();
    console.log(vertex);
    for (let neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

bfs(graph, "A");

11. Matrix Traversal

Overview: Matrix traversal involves navigating a 2D array, which is common in image processing and game development.

Use Cases:

• Searching for elements in a grid
• Flood fill algorithms
• Pathfinding in mazes

Example (JavaScript):

function traverseMatrix(matrix) {
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[i].length; j++) {
      console.log(matrix[i][j]);
    }
  }
}

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
traverseMatrix(matrix);

12. Backtracking

Overview: Backtracking is a recursive technique used to solve problems incrementally, abandoning solutions that do not meet the criteria.

Use Cases:

• Puzzle solving (e.g., Sudoku, N-Queens)
• Combinatorial problems
• Constraint satisfaction problems

Example (JavaScript - N-Queens):

function solveNQueens(n) {
  function isSafe(board, row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i] === col || Math.abs(board[i] - col) === row - i) {
        return false;
      }
    }
    return true;
  }

  function backtrack(board, row) {
    if (row === n) {
      solutions.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(board, row, col)) {
        board[row] = col;
        backtrack(board, row + 1);
        board[row] = -1;
      }
    }
  }

  let solutions = [];
  backtrack(new Array(n).fill(-1), 0);
  return solutions;
}

console.log(solveNQueens(4));

Conclusion

Each of these programming patterns is a powerful tool in a developer’s toolkit. Whether you’re optimizing your code’s performance with prefix sums or solving complex puzzles with backtracking, understanding these techniques can help you tackle a wide array of problems effectively. Experiment with these patterns, integrate them into your projects, and elevate your problem-solving skills!