Common Interview Algorithm Patterns. #CrackLeetCode

1. The Sliding Window Algorithm

Solves problems by moving a fixed-size window through the data, updating the solution as it goes. It’s used for tasks like substring or subarray search.

function averageSubArrays(arr, k) {
  // Array to store averages of subarrays
  const averages = []
  // Pointer to the start of the current window
  let start = 0
  // Variable to store the sum of elements in the current window
  let sum = 0

  // Loop through the array with the end pointer
  for (let end = 0; end < arr.length; end++) {
    // Add the current element to the sum
    sum += arr[end]

    // If the window size is equal to k
    if (end >= k - 1) {
      // Calculate the average of the current window and push it to averages[]
      averages.push(sum / k)

      // Subtract the element at the start of the window from the sum
      sum -= arr[start]

      // Move the window start one position to the right
      start++
    }
  }

  // Return the array of averages
  return averages
}

console.log(averageSubArrays([1, 2, 3, 4, 5], 3))
// [2, 3, 4]
console.log(averageSubArrays([1, 6, 3, -1, 8, 4, 5, 3, 2], 5))
// [3.4, 4, 3.8, 3.8, 4.4]

2. Two Pointers

Solves problems by iterating through a sequence with two pointers, typically starting from opposite ends and moving towards each other. It’s commonly used for tasks like finding pairs with specific properties, removing duplicates in arrays, linked lists or strings, and avoiding looping over the data structure multiple times.

// works with sorted arr
function findSumOfPair(arr, target) {
  // Initialize pointers at the beginning and end of the array
  let left = 0
  let right = arr.length - 1
  // Initialize variable to store the pair
  let pair = null
  // Initialize variable to store the sum of elements at the pointers
  let sum

  // Loop until the pointers meet
  while (left !== right) {
    // Calculate the sum of elements at the current pointers
    sum = arr[left] + arr[right]

    // If the sum matches the target, store the pair and exit the loop
    if (sum === target) {
      pair = [arr[left], arr[right]]
      break
    }
    // If the sum is less than the target, move the left pointer to the right
    else if (sum < target) {
      left++
    }
    // If the sum is greater than the target, move the right pointer to the left
    else if (sum > target) {
      right--
    }
  }

  // Return the pair
  return pair
}

console.log(findSumOfPair([1, 2, 3, 4, 5], 7)) // [2, 5]
console.log(findSumOfPair([1, 6, 8, 9, 10], 14)) // [6, 8]
console.log(findSumOfPair([1, 3, 4, 6, 8, 10], 12)) // [4, 8]
console.log(findSumOfPair([1, 2, 3, 4, 5], 10)) // null

3. Fast and Slow Pointers

Aka Hare and Tortoise Algorithm that uses two pointers (1x and 2x) to traverse an array or cyclic linked list. The fast pointer should catch the slow one once both the pointers are in cyclic loop.

// Function to check if a linked list has a cycle
function hasCycle(head) {
  // If the linked list is empty or has only one node, return false
  if (!head || !head.next) {
      return false
  }
  
  // Initialize two pointers, slow and fast
  let slow = head // Slow pointer moves one step at a time (x1)
  let fast = head.next // Fast pointer moves two steps at a time (x2)
  
  // Iterate until slow and fast pointers meet
  while (slow !== fast) {
      // If fast pointer reaches the end of the list or next node is null, there is no cycle
      if (!fast || !fast.next) {
          return false
      }
      // Move slow pointer one step ahead
      slow = slow.next
      // Move fast pointer two steps ahead
      fast = fast.next.next
  }
  
  // If slow and fast pointers meet, there is a cycle
  return true
}

// TEST CASES
function createLinkedListWithCycle(arr, pos) {
  if (arr.length === 0) return null

  // Create nodes
  const nodes = arr.map((val) => ({ val, next: null }))

  // Connect nodes
  for (let i = 0; i < nodes.length - 1; i++) {
    nodes[i].next = nodes[i + 1]
  }

  // Create cycle if pos is valid
  if (pos >= 0 && pos < nodes.length) {
    nodes[nodes.length - 1].next = nodes[pos]
  }

  // Return head of the linked list
  return nodes[0]
}

console.log(hasCycle(createLinkedListWithCycle([3, 2, 0, -4], 1))) // true
console.log(hasCycle(createLinkedListWithCycle([1, 2], 0)))         // false

4. Merge Intervals

Is a technique used to merge overlapping intervals or ranges. Commonly used in scenarios where you have a collection of intervals and you need to merge those intervals where they overlap, resulting in a consolidated set of non-overlapping intervals.

function mergeIntervals(intervals) {
  if (!intervals || intervals.length === 0) {
      return []
  }

  // Sort intervals based on their start points
  intervals.sort((a, b) => a[0] - b[0])

  // Initialize the merged array with the first interval
  const merged = [intervals[0]]

  // Iterate through the intervals starting from the second one
  for (let i = 1; i < intervals.length; i++) {
      const [currentStart, currentEnd] = intervals[i]
      const [previousStart, previousEnd] = merged[merged.length - 1]

      // If current interval overlaps with the previous one, merge them
      if (currentStart <= previousEnd) {
          merged[merged.length - 1] = [previousStart, Math.max(previousEnd, currentEnd)]
      } else {
          // If current interval doesn't overlap, add it to merged intervals
          merged.push([currentStart, currentEnd])
      }
  }

  return merged
}

console.log(mergeIntervals([[1, 4], [7, 9], [2, 5]])) // [[1, 5], [7, 9]]
console.log(mergeIntervals([[6, 7], [2, 4], [5, 9]])) // [[2, 4], [5, 9]]
console.log(mergeIntervals([[1, 4], [2, 6], [3, 5]])) // [[1, 6]]

5. Breadth First Search (BFS)

BFS explores the graph/tree level by level, starting from the given source node. It uses a queue to keep track of the nodes to be visited next.

class Graph {
  constructor() {
    this.adjacencyList = new Map()
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, [])
    }
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList.get(vertex1).push(vertex2)
    this.adjacencyList.get(vertex2).push(vertex1) // For an undirected graph
  }

  bfs(startingNode) {
    const visited = new Set()
    const queue = []

    visited.add(startingNode)
    queue.push(startingNode)

    while (queue.length > 0) {
      const currentNode = queue.shift()
      console.log(currentNode)

      const neighbors = this.adjacencyList.get(currentNode)
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor)
          queue.push(neighbor)
        }
      }
    }
  }
}

// Example usage:

const graph = new Graph()

// Adding vertices
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")

// Adding edges
graph.addEdge("A", "B")
graph.addEdge("A", "C")
graph.addEdge("B", "D")
graph.addEdge("C", "E")

// Perform BFS starting from node "A"
console.log("Breadth First Search starting from node A:")
graph.bfs("A")

// Graph visualisation:
//    A
//   / \
//  B   C
//  |   |
//  D   E

// Output:
// A
// B
// C
// D
// E

6. Depth First Search (DFS)

DFS explores the graph/tree as far as possible along each branch before backtracking, starting from the given source node. It uses a stack.

class Graph {
  constructor() {
    this.adjacencyList = new Map()
  }

  addVertex(vertex) {
    this.adjacencyList.set(vertex, [])
  }

  addEdge(vertex1, vertex2) {
    this.adjacencyList.get(vertex1).push(vertex2)
    this.adjacencyList.get(vertex2).push(vertex1) // for an undirected graph
  }

  dfs(startingNode) {
    const visited = new Set()

    const explore = (node) => {
      if (visited.has(node)) {
        return
      }

      console.log(node)
      visited.add(node)

      const neighbors = this.adjacencyList.get(node)
      for (const neighbor of neighbors) {
        explore(neighbor)
      }
    }

    explore(startingNode)
  }
}

// Example usage:

const graph = new Graph()

// Adding vertices
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")

// Adding edges
graph.addEdge("A", "B")
graph.addEdge("A", "C")
graph.addEdge("B", "D")
graph.addEdge("D", "E")

// Perform DFS starting from node "A"
console.log("Depth First Search starting from node A:")
graph.dfs("A")

// Graph visualisation:
//     A
//    / \
//   B   C
//   |
//   D
//   |
//   E

// Output:
// A
// B
// D
// E
// C

7. Subset

8. Top ‘K’ elements

9. Dynamic Programming

(will be expanded soon…)