DSA Patterns

// Find the pair of numbers that adds up to target sum
function pairSum(nums, target) {
  let left = 0;
  let right = nums.length - 1;
 
  // While left is smaller than right
  while (left < right) {
    // sum is the "left" number plus the "right" number
    const sum = nums[left] + nums[right];
 
    // If sum equals to the target,
    // return the left and right indices
    if (sum === target) return [left, right];
 
    // If sum is smaller than the target,
    // increment "left" by 1
    if (sum < target) left++;
    // Other wise, decrement right by 1
    else right--;
  }
 
  return [];
}

// Find the longest substring without repeating characters
function lengthOfLongest(s) {
  const seen = new Set();
  let left = 0;
  let max = 0;
 
  // Initialize the window, left = 0, right = 0
  // For every iteration, expand the window by moving "right" right
  for (let right = 0; right < s.length; right++) {
    // While seen contains the "right" character
    while (seen.has(s[right])) {
      // Shrink the window by removing the "left" character
      seen.delete(s[left]);
      left++;
    }
 
    // If seen doesn't contain the "right" character
    // Add the new "right" character to the window
    seen.add(s[right]);
 
    // Update the maximum window size
    max = Math.max(max, right - left + 1);
  }
 
  return max;
}

// Detect a cycle in a linked list
function hasCycle(head) {
  let slow = head;
  let fast = head;
 
  // Fast moves 2 steps, slow moves 1 step
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
 
    // If they meet, there is a cycle
    if (slow === fast) return true;
  }
 
  // Fast reached the end, no cycle
  return false;
}

// Find the target in a sorted array
function binarySearch(nums, target) {
  let left = 0;
  let right = nums.length - 1;
 
  // Keep searching while "left" hasn't gone past "right"
  while (left <= right) {
    // Calculate the middle index
    const mid = left + Math.floor((right - left) / 2);
 
    // If the middle element is the target, return it
    if (nums[mid] === target) return mid;
 
    // If the middle is too small, move "left" to mid + 1
    // to search the right half
    if (nums[mid] < target) left = mid + 1;
    // Otherwise, search the left half
    else right = mid - 1;
  }
 
  return -1;
}

// Traverse a tree level by level
function bfs(root) {
  if (!root) return;
 
  // Start with the root in the queue
  const queue = [root];
 
  // Process nodes until the queue is empty
  while (queue.length > 0) {
    // Dequeue the front node
    const node = queue.shift();
    console.log(node.value);
 
    // Enqueue all children
    for (const child of node.children ?? []) {
      queue.push(child);
    }
  }
}

// Traverse a graph depth-first
function dfs(node, visited = new Set()) {
  // Skip if already visited
  if (!node || visited.has(node)) return;
 
  // Mark as visited
  visited.add(node);
  console.log(node.value);
 
  // Visit each neighbor recursively
  for (const neighbor of node.neighbors ?? []) {
    dfs(neighbor, visited);
  }
}

// Generate all subsets of an array
function subsets(nums) {
  const result = [];
 
  function backtrack(start, current) {
    // Save the current subset
    result.push([...current]);
 
    // Try adding each remaining element
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]); // choose
      backtrack(i + 1, current); // explore
      current.pop(); // unchoose
    }
  }
 
  backtrack(0, []);
  return result;
}

// Count the ways to climb n stairs (1 or 2 steps at a time)
function climbStairs(n) {
  // Base cases: 1 way for 1 stair, 2 ways for 2 stairs
  if (n <= 2) return n;
 
  let prev = 1; // dp[i-2]
  let curr = 2; // dp[i-1]
 
  // Each step is reachable from the previous one or two
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
 
  return curr;
}

const nums = [1, 2, 3, 4, 5];
 
// Build the prefix sum array, starting with 0
const prefix = [0];
for (const n of nums) {
  prefix.push(prefix[prefix.length - 1] + n);
}
// prefix = [0, 1, 3, 6, 10, 15]
 
// Sum of nums[i..j] inclusive = prefix[j+1] - prefix[i]
function rangeSum(i, j) {
  return prefix[j + 1] - prefix[i];
}
 
rangeSum(1, 3); // 2 + 3 + 4 = 9

// Find two numbers that add up to the target
function twoSum(nums, target) {
  const seen = new Map();
 
  for (let i = 0; i < nums.length; i++) {
    // Calculate what number we need to reach the target
    const complement = target - nums[i];
 
    // If we have seen it before, return both indices
    if (seen.has(complement)) return [seen.get(complement), i];
 
    // Otherwise, store the current number and its index
    seen.set(nums[i], i);
  }
 
  return [];
}

// Find the next greater element for each position
function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = []; // indices with decreasing values
 
  for (let i = 0; i < nums.length; i++) {
    // Pop all smaller elements — their next greater is nums[i]
    while (stack.length && nums[stack.at(-1)] < nums[i]) {
      result[stack.pop()] = nums[i];
    }
 
    // Push the current index
    stack.push(i);
  }
 
  // Remaining indices in the stack have no greater element
  return result;
}

// Merge all overlapping intervals
function merge(intervals) {
  // Sort by start time so overlaps are adjacent
  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 the current interval overlaps with the last merged one
    if (intervals[i][0] <= last[1]) {
      // Extend the last interval's end
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      // No overlap, add as a new interval
      merged.push(intervals[i]);
    }
  }
 
  return merged;
}