Advanced Data Structures & Techniques

1. Heaps / Priority Queue

What is a Heap?

A heap is a complete binary tree that satisfies the heap property. It is the data structure behind a priority queue -- it lets you efficiently access, insert, and remove the minimum (or maximum) element.

• Min-heap: Every parent node is less than or equal to its children. The smallest element is always at the root.
• Max-heap: Every parent node is greater than or equal to its children. The largest element is always at the root.
• Complete binary tree: Every level is fully filled except possibly the last, which is filled left to right.
• Array storage: Heaps are stored as arrays. For a node at index i:
  • Parent: Math.floor((i - 1) / 2)
  • Left child: 2 * i + 1
  • Right child: 2 * i + 2

           1              Array: [1, 3, 5, 7, 8, 9, 6]
         /   \
        3     5           Index:  0  1  2  3  4  5  6
       / \   / \
      7   8 9   6         Parent of index 4 (value 8):
                            floor((4-1)/2) = index 1 (value 3)

                          Children of index 1 (value 3):
                            2*1+1 = index 3 (value 7)
                            2*1+2 = index 4 (value 8)

Time Complexity

Using Heaps in Python

Python provides the heapq module which implements a min-heap by default. There is no built-in max-heap, but you can negate values as a workaround.

Python
import heapq

# --- Min-Heap ---
heap = []

# Push elements
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print(heap)        # [1, 2, 8, 5]

# Peek at smallest
print(heap[0])     # 1

# Pop smallest
smallest = heapq.heappop(heap)
print(smallest)    # 1
print(heap)        # [2, 5, 8]

# Build heap from existing list (in-place, O(n))
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print(nums)        # [1, 2, 8, 5, 3]

# --- Max-Heap (negate values) ---
max_heap = []
for val in [5, 2, 8, 1]:
    heapq.heappush(max_heap, -val)

largest = -heapq.heappop(max_heap)
print(largest)     # 8

# --- Heap with tuples (priority, value) ---
tasks = []
heapq.heappush(tasks, (3, "low priority"))
heapq.heappush(tasks, (1, "high priority"))
heapq.heappush(tasks, (2, "medium priority"))

print(heapq.heappop(tasks))  # (1, 'high priority')

Using Heaps in JavaScript

JavaScript has no built-in heap. You need to implement one yourself. Here is a clean MinHeap class you can use in interviews.

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

  size()    { return this.data.length; }
  peek()    { return this.data[0]; }
  isEmpty() { return this.data.length === 0; }

  push(val) {
    this.data.push(val);
    this._bubbleUp(this.data.length - 1);
  }

  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this._sinkDown(0);
    }
    return top;
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.data[i] >= this.data[parent]) break;
      [this.data[i], this.data[parent]] =
        [this.data[parent], this.data[i]];
      i = parent;
    }
  }

  _sinkDown(i) {
    const n = this.data.length;
    while (true) {
      let smallest = i;
      const left  = 2 * i + 1;
      const right = 2 * i + 2;
      if (left  < n && this.data[left]  < this.data[smallest]) smallest = left;
      if (right < n && this.data[right] < this.data[smallest]) smallest = right;
      if (smallest === i) break;
      [this.data[i], this.data[smallest]] =
        [this.data[smallest], this.data[i]];
      i = smallest;
    }
  }
}

// Usage
const heap = new MinHeap();
heap.push(5);
heap.push(2);
heap.push(8);
heap.push(1);
console.log(heap.peek()); // 1
console.log(heap.pop());  // 1
console.log(heap.pop());  // 2

Common Heap Problems

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element. Use a min-heap of size k -- the top is always the kth largest.

Python
import heapq

def findKthLargest(nums, k):
    # Min-heap of size k
    heap = nums[:k]
    heapq.heapify(heap)       # O(k)

    for num in nums[k:]:
        if num > heap[0]:     # bigger than current kth largest?
            heapq.heapreplace(heap, num)  # pop smallest, push num

    return heap[0]           # root = kth largest

# Example
print(findKthLargest([3,2,1,5,6,4], 2))  # 5
print(findKthLargest([3,2,3,1,2,4,5,5,6], 4))  # 4

JavaScript
function findKthLargest(nums, k) {
  const heap = new MinHeap();

  for (const num of nums) {
    heap.push(num);
    if (heap.size() > k) {
      heap.pop(); // remove smallest, keep k largest
    }
  }

  return heap.peek(); // kth largest
}

console.log(findKthLargest([3,2,1,5,6,4], 2)); // 5

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. Count frequencies with a hash map, then use a min-heap of size k.

Python
import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    # nlargest returns k items with highest count
    return heapq.nlargest(k, count.keys(), key=count.get)

# Example
print(topKFrequent([1,1,1,2,2,3], 2))  # [1, 2]

JavaScript
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) {
    freq.set(n, (freq.get(n) || 0) + 1);
  }

  // Bucket sort approach: index = frequency
  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);
}

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

Merge K Sorted Lists

Push the head of each list into a min-heap. Pop the smallest, add it to the result, and push the next node from that list. Repeat until the heap is empty.

Find Median from Data Stream

Use two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep them balanced (sizes differ by at most 1). The median is the top of the larger heap, or the average of both tops.

2. Tries (Prefix Trees)

What is a Trie?

A trie (pronounced "try") is a tree-like data structure where each path from the root to a node represents a prefix of a word. Each node has children (one per character), and nodes can be marked as the end of a word.

• The root node is empty (represents the empty string).
• Each edge represents a single character.
• Words that share a prefix share the same path from the root.
• Lookup, insert, and prefix search are all O(m) where m is the length of the word.

        (root)
          |
          c
          |
          a
         / \
        t   r
        *   *
            |
            d
            *

    * = end of word

    "cat"  : root -> c -> a -> t*
    "car"  : root -> c -> a -> r*
    "card" : root -> c -> a -> r -> d*

    Searching "ca" : root -> c -> a (found prefix, not a complete word)
    Searching "cab": root -> c -> a -> b (no 'b' child -- not found)

Implementation

Python
class TrieNode:
    def __init__(self):
        self.children = {}       # char -> TrieNode
        self.is_end = False     # marks end of a word


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """Insert a word into the trie. O(m)"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        """Return True if the exact word is in the trie. O(m)"""
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        """Return True if any word starts with the prefix. O(m)"""
        return self._find(prefix) is not None

    def _find(self, prefix):
        """Traverse trie following the prefix. Return last node or None."""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

# Usage
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("card")

print(trie.search("car"))        # True
print(trie.search("ca"))         # False (not a complete word)
print(trie.startsWith("ca"))     # True
print(trie.startsWith("dog"))    # False

JavaScript
class TrieNode {
  constructor() {
    this.children = {};   // char -> TrieNode
    this.isEnd = false;   // marks end of a word
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  /** Insert a word into the trie. O(m) */
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  /** Return true if the exact word is in the trie. O(m) */
  search(word) {
    const node = this._find(word);
    return node !== null && node.isEnd;
  }

  /** Return true if any word starts with the prefix. O(m) */
  startsWith(prefix) {
    return this._find(prefix) !== null;
  }

  _find(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return null;
      node = node.children[ch];
    }
    return node;
  }
}

// Usage
const trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("card");

console.log(trie.search("car"));       // true
console.log(trie.search("ca"));        // false
console.log(trie.startsWith("ca"));    // true
console.log(trie.startsWith("dog"));   // false

Applications

• Autocomplete: Traverse to the prefix node, then DFS to find all completions.
• Spell checking: Check if a word exists; suggest corrections via similar paths.
• IP routing: Longest prefix matching in routers (binary trie).
• Word search problems: Build a trie of target words, then DFS on the board.

LeetCode: Implement Trie (Medium)

The implementation above is the complete solution for LeetCode 208: Implement Trie. The key insight is using a dictionary (or object) of children at each node, plus a boolean flag for word endings.

LeetCode: Word Search II (Hard)

Build a trie from all target words. Then for each cell in the board, DFS while following the trie. This prunes invalid paths early instead of searching for each word separately. The trie turns an O(words * cells * 4^L) brute force into something much faster.

3. Union-Find (Disjoint Set Union)

What is Union-Find?

Union-Find (also called Disjoint Set Union or DSU) is a data structure that tracks a set of elements partitioned into disjoint (non-overlapping) groups. It supports two operations efficiently:

• Find(x): Which group does element x belong to? (Returns the group's representative/root.)
• Union(x, y): Merge the groups containing x and y into one group.

With path compression and union by rank, both operations run in nearly O(1) amortized time -- specifically O(alpha(n)) where alpha is the inverse Ackermann function, which is effectively constant for any practical input size.

Implementation

Python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # each element is its own root
        self.rank = [0] * n             # rank for union by rank
        self.count = n                   # number of disjoint sets

    def find(self, x):
        """Find root of x with path compression."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        """Merge sets containing x and y. Return False if already same set."""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # already connected

        # Union by rank: attach smaller tree under larger
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

        self.count -= 1
        return True

    def connected(self, x, y):
        """Check if x and y are in the same set."""
        return self.find(x) == self.find(y)

# Usage
uf = UnionFind(5)   # elements: 0, 1, 2, 3, 4
uf.union(0, 1)       # merge {0} and {1}
uf.union(2, 3)       # merge {2} and {3}
print(uf.connected(0, 1))  # True
print(uf.connected(0, 2))  # False
uf.union(1, 3)       # merge {0,1} and {2,3}
print(uf.connected(0, 2))  # True
print(uf.count)            # 2 (groups: {0,1,2,3} and {4})

JavaScript
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n; // number of disjoint sets
  }

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

  union(x, y) {
    let rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false; // already connected

    // Union by rank
    if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];
    this.parent[ry] = rx;
    if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;

    this.count--;
    return true;
  }

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

// Usage
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
console.log(uf.connected(0, 1)); // true
console.log(uf.connected(0, 2)); // false
uf.union(1, 3);
console.log(uf.connected(0, 2)); // true
console.log(uf.count);            // 2

Applications

• Number of connected components: Union all edges, then check uf.count.
• Cycle detection in undirected graph: If union(u, v) returns false, there is a cycle (u and v are already connected).
• Kruskal's MST algorithm: Sort edges by weight, union vertices; skip if already connected.

LeetCode: Number of Provinces (Medium)

Given an adjacency matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected, return the number of provinces (connected components).

Python
def findCircleNum(isConnected):
    n = len(isConnected)
    uf = UnionFind(n)

    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                uf.union(i, j)

    return uf.count

# Example
print(findCircleNum([[1,1,0],[1,1,0],[0,0,1]]))  # 2
print(findCircleNum([[1,0,0],[0,1,0],[0,0,1]]))  # 3

JavaScript
function findCircleNum(isConnected) {
  const n = isConnected.length;
  const uf = new UnionFind(n);

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) {
        uf.union(i, j);
      }
    }
  }

  return uf.count;
}

console.log(findCircleNum([[1,1,0],[1,1,0],[0,0,1]])); // 2

LeetCode: Redundant Connection (Medium)

Given a graph that was a tree plus one extra edge, find that extra edge. Process edges in order; the first edge where union(u, v) returns false (both already connected) is the answer. This is a direct application of cycle detection with Union-Find.

4. Monotonic Stack / Monotonic Queue

Monotonic Stack

A monotonic stack is a stack that maintains its elements in either strictly increasing or strictly decreasing order. When you push a new element, you first pop all elements that violate the monotonic property.

When to use: Any problem asking for the "next greater element", "next smaller element", "previous greater/smaller", or "how many days until a warmer temperature". The key pattern is: for each element, find the nearest element that is larger/smaller.

Template: Next Greater Element

Python
def nextGreaterElement(nums):
    """For each element, find the next element that is strictly greater.
    Return -1 if no such element exists."""
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices, values decrease from bottom to top

    for i in range(n):
        # While current element is greater than stack top
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]  # nums[i] is the next greater for nums[idx]
        stack.append(i)

    return result

# Example
print(nextGreaterElement([2, 1, 2, 4, 3]))
# [4, 2, 4, -1, -1]

JavaScript
function nextGreaterElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = []; // stores indices

  for (let i = 0; i < n; i++) {
    while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
      const idx = stack.pop();
      result[idx] = nums[i];
    }
    stack.push(i);
  }

  return result;
}

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

Daily Temperatures

Given an array of daily temperatures, return an array where answer[i] is the number of days until a warmer temperature. This is the "next greater element" pattern but returning the index distance instead of the value.

Monotonic Deque (Sliding Window Maximum)

A monotonic deque maintains elements in decreasing order. The front of the deque is always the maximum in the current window. When the window slides, we remove elements that fall out of the window from the front and maintain the decreasing order from the back.

Sliding Window Maximum -- Full Solution

Given an array nums and window size k, return the maximum value in each sliding window of size k.

Python
from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()   # stores indices, values decreasing front-to-back
    result = []

    for i in range(len(nums)):
        # Remove elements outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove elements smaller than current (they can't be max)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Window is fully formed starting at i = k - 1
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Example
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

JavaScript
function maxSlidingWindow(nums, k) {
  const dq = [];    // indices, values decreasing front-to-back
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove elements outside window
    while (dq.length && dq[0] < i - k + 1) {
      dq.shift();
    }

    // Remove elements smaller than current
    while (dq.length && nums[dq[dq.length - 1]] < nums[i]) {
      dq.pop();
    }

    dq.push(i);

    if (i >= k - 1) {
      result.push(nums[dq[0]]);
    }
  }

  return result;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// [3, 3, 5, 5, 6, 7]

5. Segment Tree (Brief)

A segment tree is a binary tree used for storing information about intervals (segments) of an array. It allows for efficient range queries (sum, min, max over a subarray) and point updates.

• Query (range sum/min/max): O(log n)
• Update (change a single element): O(log n)
• Build: O(n)
• Space: O(n)

When you need it: When a problem requires both range queries (sum of subarray, minimum in range) AND point updates. If you only need range queries without updates, a prefix sum array works. If you only need updates without queries, a simple array works. Segment trees solve the case where you need both.

Python
class SegmentTree:
    """Segment tree for range sum queries with point updates."""

    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (2 * self.n)
        # Build: place values in leaves, then fill parents
        for i in range(self.n):
            self.tree[self.n + i] = nums[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, index, value):
        """Set nums[index] = value. O(log n)"""
        i = index + self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def query(self, left, right):
        """Sum of nums[left..right] inclusive. O(log n)"""
        res = 0
        l, r = left + self.n, right + self.n + 1
        while l < r:
            if l & 1:
                res += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                res += self.tree[r]
            l >>= 1
            r >>= 1
        return res

# Usage
nums = [1, 3, 5, 7, 9, 11]
st = SegmentTree(nums)
print(st.query(1, 3))   # 15 (3 + 5 + 7)
st.update(2, 10)        # change index 2 from 5 to 10
print(st.query(1, 3))   # 20 (3 + 10 + 7)

6. Bit Manipulation

Binary Representation

Computers store numbers in binary (base 2). Each digit is a bit (0 or 1). Understanding how to work with bits directly lets you solve certain problems with extreme efficiency -- O(1) space and blazing fast operations.

Decimal   Binary     How to read it
  0       0000       no bits set
  1       0001       2^0 = 1
  5       0101       2^2 + 2^0 = 4 + 1 = 5
  10      1010       2^3 + 2^1 = 8 + 2 = 10
  15      1111       2^3 + 2^2 + 2^1 + 2^0 = 8+4+2+1 = 15
  255     11111111   all 8 bits set

Common Bitwise Operators

Useful Bit Tricks

Check if Power of 2

A power of 2 has exactly one bit set. n & (n - 1) clears the lowest set bit. If the result is 0, only one bit was set.

Python
def isPowerOfTwo(n):
    return n > 0 and (n & (n - 1)) == 0

print(isPowerOfTwo(16))  # True  (10000 & 01111 = 0)
print(isPowerOfTwo(18))  # False (10010 & 10001 = 10000)

JavaScript
function isPowerOfTwo(n) {
  return n > 0 && (n & (n - 1)) === 0;
}

console.log(isPowerOfTwo(16)); // true
console.log(isPowerOfTwo(18)); // false

Get, Set, and Clear a Bit

Python
def getBit(n, pos):
    """Check if bit at position pos is set (0-indexed from right)."""
    return (n >> pos) & 1

def setBit(n, pos):
    """Set bit at position pos to 1."""
    return n | (1 << pos)

def clearBit(n, pos):
    """Clear bit at position pos to 0."""
    return n & ~(1 << pos)

# Example: n = 10 (1010 in binary)
print(getBit(10, 1))    # 1 (bit at position 1 is set)
print(getBit(10, 2))    # 0 (bit at position 2 is not set)
print(setBit(10, 2))    # 14 (1110)
print(clearBit(10, 1))  # 8  (1000)

JavaScript
function getBit(n, pos)   { return (n >> pos) & 1; }
function setBit(n, pos)   { return n | (1 << pos); }
function clearBit(n, pos) { return n & ~(1 << pos); }

console.log(getBit(10, 1));   // 1
console.log(setBit(10, 2));   // 14
console.log(clearBit(10, 1)); // 8

Count Set Bits (Brian Kernighan's Algorithm)

n & (n - 1) removes the lowest set bit. Keep doing it until n is 0, counting each step.

Python
def countBits(n):
    count = 0
    while n:
        n &= (n - 1)  # remove lowest set bit
        count += 1
    return count

print(countBits(11))  # 3 (1011 has three 1-bits)
print(countBits(7))   # 3 (0111 has three 1-bits)

JavaScript
function countBits(n) {
  let count = 0;
  while (n) {
    n &= (n - 1);
    count++;
  }
  return count;
}

console.log(countBits(11)); // 3
console.log(countBits(7));  // 3

XOR Tricks

XOR has two key properties that make it magical for certain problems:

• a ^ a = 0 (XOR with itself cancels out)
• a ^ 0 = a (XOR with zero gives itself)
• XOR is commutative and associative: order does not matter

Python
# Single Number: every element appears twice except one. Find it.
def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num  # pairs cancel out, only single remains
    return result

print(singleNumber([2, 1, 4, 1, 2]))  # 4

# Missing Number: array has 0..n with one missing. Find it.
def missingNumber(nums):
    result = len(nums)  # start with n
    for i, num in enumerate(nums):
        result ^= i ^ num  # XOR index and value
    return result

print(missingNumber([3, 0, 1]))  # 2

JavaScript
// Single Number
function singleNumber(nums) {
  let result = 0;
  for (const num of nums) {
    result ^= num;
  }
  return result;
}

console.log(singleNumber([2, 1, 4, 1, 2])); // 4

// Missing Number
function missingNumber(nums) {
  let result = nums.length;
  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }
  return result;
}

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

LeetCode Bit Manipulation Problems

7. Math for Interviews

You don't need to be a math whiz for coding interviews, but these few algorithms and tricks come up regularly.

GCD (Euclidean Algorithm)

The greatest common divisor of two numbers. Used in fraction simplification, LCM calculation, and various number theory problems.

Python
import math

# Built-in (Python 3.5+)
print(math.gcd(12, 8))   # 4

# Manual Euclidean algorithm
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(12, 8))   # 4
print(gcd(54, 24))  # 6

# LCM using GCD
def lcm(a, b):
    return a * b // gcd(a, b)

print(lcm(4, 6))  # 12

JavaScript
function gcd(a, b) {
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

console.log(gcd(12, 8));  // 4
console.log(lcm(4, 6));   // 12

Power of 2, 3, 4 Checks

Python
# Power of 2: exactly one bit set
def isPowerOf2(n):
    return n > 0 and (n & (n - 1)) == 0

# Power of 3: largest power of 3 in int range is 3^19 = 1162261467
def isPowerOf3(n):
    return n > 0 and 1162261467 % n == 0

# Power of 4: power of 2 AND only even-position bits set
def isPowerOf4(n):
    return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0

JavaScript
function isPowerOf2(n) { return n > 0 && (n & (n - 1)) === 0; }
function isPowerOf3(n) { return n > 0 && 1162261467 % n === 0; }
function isPowerOf4(n) {
  return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
}

Sieve of Eratosthenes

Find all prime numbers up to a given limit. Time complexity is O(n log log n), which is nearly linear.

Python
def sieve(limit):
    """Return list of all primes up to limit."""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

    return [i for i in range(2, limit + 1) if is_prime[i]]

print(sieve(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

JavaScript
function sieve(limit) {
  const isPrime = new Array(limit + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let i = 2; i * i <= limit; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= limit; j += i) {
        isPrime[j] = false;
      }
    }
  }

  const primes = [];
  for (let i = 2; i <= limit; i++) {
    if (isPrime[i]) primes.push(i);
  }
  return primes;
}

console.log(sieve(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Modular Arithmetic

When problems say "return the answer modulo 10^9 + 7", use these rules:

Python
MOD = 10**9 + 7

# Addition
(a + b) % MOD

# Subtraction (add MOD to avoid negatives)
(a - b + MOD) % MOD

# Multiplication
(a * b) % MOD

# Exponentiation (fast power)
pow(a, b, MOD)  # Python built-in: computes (a^b) % MOD efficiently

# Division: multiply by modular inverse
# a / b mod p = a * pow(b, p-2, p) mod p  (when p is prime)

JavaScript
const MOD = 1_000_000_007;

// Addition
(a + b) % MOD;

// Subtraction
((a - b) % MOD + MOD) % MOD;

// Multiplication -- use BigInt for large numbers
Number(BigInt(a) * BigInt(b) % BigInt(MOD));

// Fast exponentiation
function modPow(base, exp, mod) {
  let result = 1n;
  base = BigInt(base) % BigInt(mod);
  exp = BigInt(exp);
  mod = BigInt(mod);
  while (exp > 0n) {
    if (exp % 2n === 1n) result = result * base % mod;
    exp >>= 1n;
    base = base * base % mod;
  }
  return Number(result);
}

8. Practice Quiz

Test your understanding of the advanced topics covered on this page.