Algorithm Problem Solving Patterns

June 20, 2024

IE Sliding Window, Two Pointers etc. Most algorithms can be categorized into 5 problem-solving patterns that help in identifying the optimal solution.

Table of Contents

Sliding Window
Two Pointers
Fast and Slow Pointers (Tortoise and Hare)
Toplogical Sorting
Union Find (Disjoint Set)

Sliding Window

The sliding window technique is used for problems that involve arrays or lists where you need to find a subarray (or sublist) that satisfies certain conditions. It's particularly useful for problems involving sums, averages, or finding specific subarray properties within a given window size.

Example Problem: Find the maximum sum of a subarray of size k.

function maxSumSubarray(arr, k) {
  let maxSum = 0;
  let windowSum = 0;

  // Calculate the sum of the first window
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }

  maxSum = windowSum;

  // Slide the window from the start to the end of the array
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

// Example usage
const arr = [1, 3, 2, 6, -1, 4, 1, 8, 2];
const k = 3;
console.log(maxSumSubarray(arr, k)); // Output: 14 (6, -1, 4)

Two Pointers

The two pointers technique is useful for problems involving sorted arrays or linked lists. It involves using two pointers to iterate through the array from different directions or positions, usually starting at the beginning and end.

Example Problem: Given a sorted array, find two numbers that add up to a given target.

function twoSumSorted(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const currentSum = arr[left] + arr[right];
    if (currentSum === target) {
      return [arr[left], arr[right]];
    } else if (currentSum < target) {
      left++;
    } else {
      right--;
    }
  }

  return null;
}

// Example usage
const arr = [1, 2, 3, 4, 6];
const target = 6;
console.log(twoSumSorted(arr, target)); // Output: [2, 4]

Fast and Slow Pointers (Tortoise and Hare)

This technique involves using two pointers that move at different speeds (one fast and one slow). It is often used to detect cycles in linked lists or arrays.

Example Problem: Detect if a linked list has a cycle.

class ListNode {
  constructor(value = 0, next = null) {
    this.value = value;
    this.next = next;
  }
}

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }

  return false;
}

// Example usage
// Creating a linked list with a cycle
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // Cycle here

console.log(hasCycle(node1)); // Output: true

Toplogical Sorting

Topological sorting is used to order the vertices of a directed acyclic graph (DAG) in a linear sequence such that for every directed edge u -> v, vertex u comes before v.

Example Problem: Perform a topological sort on a directed acyclic graph.

function topologicalSort(graph) {
  const stack = [];
  const visited = new Set();

  function dfs(node) {
    if (visited.has(node)) return;
    visited.add(node);
    for (let neighbor of graph[node]) {
      dfs(neighbor);
    }
    stack.push(node);
  }

  for (let node in graph) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }

  return stack.reverse();
}

// Example usage
const graph = {
  5: [2, 0],
  4: [0, 1],
  3: [1],
  2: [3],
  1: [],
  0: [],
};
console.log(topologicalSort(graph)); // Output: [5, 4, 2, 3, 1, 0]

Union Find (Disjoint Set)

The union-find (or disjoint-set) is a data structure that keeps track of elements partitioned into disjoint (non-overlapping) sets. It supports two primary operations: finding the set a particular element is in, and merging two sets.

Example Problem: Implement union-find to detect cycles in an undirected graph.

class UnionFind {
  constructor(size) {
    this.parent = Array.from({length: size}, (_, index) => index);
    this.rank = Array(size).fill(0);
  }

  find(node) {
    if (this.parent[node] !== node) {
      this.parent[node] = this.find(this.parent[node]); // Path compression
    }
    return this.parent[node];
  }

  union(node1, node2) {
    const root1 = this.find(node1);
    const root2 = this.find(node2);

    if (root1 !== root2) {
      if (this.rank[root1] > this.rank[root2]) {
        this.parent[root2] = root1;
      } else if (this.rank[root1] < this.rank[root2]) {
        this.parent[root1] = root2;
      } else {
        this.parent[root2] = root1;
        this.rank[root1]++;
      }
    }
  }

  connected(node1, node2) {
    return this.find(node1) === this.find(node2);
  }
}

// Example usage
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
console.log(uf.connected(0, 2)); // Output: true
console.log(uf.connected(0, 3)); // Output: false

Recent Work

Basalt

basalt.software

Free desktop AI Chat client, designed for developers and businesses. Unlocks advanced model settings only available in the API. Includes quality of life features like custom syntax highlighting.

Learn More

Technologies Used

TypeScript

Electron

React

BidBear

bidbear.io

Bidbear is a report automation tool. It downloads Amazon Seller and Advertising reports, daily, to a private database. It then merges and formats the data into beautiful, on demand, exportable performance reports.

Learn More