Common Patterns Summary

// JavaScript — Remove duplicates from sorted array
function removeDuplicates(arr) {
  if (arr.length === 0) return 0;
  let writeIdx = 1;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] !== arr[i - 1]) {
      arr[writeIdx] = arr[i];
      writeIdx++;
    }
  }
  return writeIdx;
}

# Python
def remove_duplicates(arr):
    if not arr:
        return 0
    write_idx = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_idx] = arr[i]
            write_idx += 1
    return write_idx

// JavaScript — Happy number (sum of squared digits eventually reaches 1)
function isHappy(n) {
  function digitSquareSum(num) {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  let slow = n, fast = n;
  do {
    slow = digitSquareSum(slow);
    fast = digitSquareSum(digitSquareSum(fast));
  } while (slow !== fast);
  return slow === 1;
}

# Python
def is_happy(n):
    def digit_square_sum(num):
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total
    slow = fast = n
    while True:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
        if slow == fast:
            break
    return slow == 1

// JavaScript — Longest substring without repeating characters
function lengthOfLongestSubstring(s) {
  const charIdx = new Map();
  let maxLen = 0, left = 0;
  for (let right = 0; right < s.length; right++) {
    if (charIdx.has(s[right]) && charIdx.get(s[right]) >= left) {
      left = charIdx.get(s[right]) + 1;
    }
    charIdx.set(s[right], right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

# Python
def length_of_longest_substring(s):
    char_idx = {}
    max_len = left = 0
    for right, ch in enumerate(s):
        if ch in char_idx and char_idx[ch] >= left:
            left = char_idx[ch] + 1
        char_idx[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len

// JavaScript
function mergeIntervals(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;
}

# Python
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

// JavaScript — Top K frequent elements using bucket sort
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  // Bucket: index = frequency, value = list of elements
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) buckets[count].push(num);
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

# Python
import heapq
from collections import Counter

def top_k_frequent(nums, k):
    freq = Counter(nums)
    # nlargest uses a heap internally
    return [item for item, count in freq.most_common(k)]

// JavaScript — Count subarrays with sum divisible by k
function subarraysDivByK(arr, k) {
  const modCount = new Map([[0, 1]]);
  let prefix = 0, count = 0;
  for (const num of arr) {
    prefix = ((prefix + num) % k + k) % k; // handle negatives
    count += modCount.get(prefix) || 0;
    modCount.set(prefix, (modCount.get(prefix) || 0) + 1);
  }
  return count;
}

# Python
def subarrays_div_by_k(arr, k):
    mod_count = {0: 1}
    prefix = 0
    count = 0
    for num in arr:
        prefix = (prefix + num) % k
        count += mod_count.get(prefix, 0)
        mod_count[prefix] = mod_count.get(prefix, 0) + 1
    return count

// JavaScript
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

# Python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

// Decision guide:
// 'Shortest' or 'minimum steps' → BFS
// 'All paths' or 'does a path exist' → DFS
// 'Level order' → BFS
// 'Permutations/combinations' → DFS (backtracking)

// JavaScript — Minimum steps to reach target in grid
function minSteps(grid, start, end) {
  const rows = grid.length, cols = grid[0].length;
  const queue = [[...start, 0]]; // [row, col, steps]
  const visited = new Set([start.toString()]);
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  while (queue.length) {
    const [r, c, steps] = queue.shift();
    if (r === end[0] && c === end[1]) return steps;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      const key = `${nr},${nc}`;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && grid[nr][nc] === 0 && !visited.has(key)) {
        visited.add(key);
        queue.push([nr, nc, steps + 1]);
      }
    }
  }
  return -1;
}

# Python
from collections import deque

def min_steps(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start[0], start[1], 0)])
    visited = {(start[0], start[1])}
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        pass  # directions defined in loop below
    while queue:
        r, c, steps = queue.popleft()
        if (r, c) == tuple(end):
            return steps
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0 and (nr,nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc, steps + 1))
    return -1