LogoBytesFor Developers
HomeBytesheetsRoadmapsUI TemplatesUI ToolsStack Discussion
10 Topics
Chapter•360 Minutes

Hard DSA — Linked Lists, Combinatorial Backtracking & Math

Master node pointer manipulation in groups, exhaustive combinatorial search spaces, number theory algorithms, and geometric sweep line techniques.

01. Reverse Nodes in k-Group

Difficulty:HardPattern:Linked List In-Place ReversalTime:O(n)Space:O(1)

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. k is a positive integer. If the number of nodes is not a multiple of k, left-out nodes at the end remain as they are.

How It Works & Algorithmic Design

Solves using Iterative Group Traversal with Pointer Reversal:

  1. Lookahead Check: Verify if at least k nodes exist from current head. If fewer, keep them intact.
  2. Group Reversal: Reverse k nodes in place by adjusting next pointers.
  3. Pointer Rewiring: Connect previous group's tail to the new head of the reversed group, and connect new tail to the next remaining group.

Why This Approach Works Best

Reverses complete groups in linear $O(n)$ time using $O(1)$ extra space.

Example Walkthrough
Input: head = [1,2,3,4,5], k = 2
Reverse in pairs of 2.
Reversal Steps: Group 1: [1,2] -> [2,1]. Group 2: [3,4] -> [4,3]. Last group: [5] (unchanged).
Grouped node reversal.
Output: [2, 1, 4, 3, 5]
Modified list.

Answer: Reverse Nodes in k-Group implementation

function reverseKGroup(head, k) {
  const dummy = { val: 0, next: head };
  let groupPrev = dummy;
  while (true) {
    let kth = groupPrev;
    for (let i = 0; i < k && kth; i++) kth = kth.next;
    if (!kth) break;
    let groupNext = kth.next;
    let prev = groupNext, curr = groupPrev.next;
    while (curr !== groupNext) {
      const tmp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = tmp;
    }
    const tmp = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = tmp;
  }
  return dummy.next;
}
💡 Iterate through linked list in groups of k nodes and reverse pointers in-place.
Key Takeaways
  • Use lookahead iteration to ensure at least $k$ nodes exist before reversing.
  • Dummy node simplifies updates to head pointer.
  • Runs in $O(n)$ time and $O(1)$ extra memory.

02. N-Queens

Difficulty:HardPattern:Combinatorial BacktrackingTime:O(n!)Space:O(n^2)

The N-Queens puzzle requires placing n queens on an $n \times n$ chessboard such that no two queens attack each other. Return all distinct board configurations.

How It Works & Algorithmic Design

Solves using DFS Backtracking with Sets:

  1. Conflict Sets: Maintain sets for used cols, main diagonals (r - c), and anti-diagonals (r + c).
  2. Row Placement DFS: Place queens row by row. For each row $r$, test column $c$:
    • If column or diagonals are occupied, skip.
    • Place queen, mark conflict sets, and recurse to row $r + 1$.
    • Backtrack: remove queen and unmark sets.

Why This Approach Works Best

Set lookups determine placement safety in $O(1)$ time, reducing the search space to $O(n!)$ time.

Example Walkthrough
Input: n = 4
4x4 chessboard.
Valid Layouts: Distinct solutions placing 4 non-attacking queens.
No shared rows, columns, or diagonals.
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
2 distinct arrangements.

Answer: N-Queens Backtracking implementation

function solveNQueens(n) {
  const res = [];
  const cols = new Set(), diag = new Set(), antiDiag = new Set();
  const board = Array.from({ length: n }, () => new Array(n).fill('.'));
  function backtrack(r) {
    if (r === n) {
      res.push(board.map(row => row.join('')));
      return;
    }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag.has(r - c) || antiDiag.has(r + c)) continue;
      cols.add(c); diag.add(r - c); antiDiag.add(r + c);
      board[r][c] = 'Q';
      backtrack(r + 1);
      cols.delete(c); diag.delete(r - c); antiDiag.delete(r + c);
      board[r][c] = '.';
    }
  }
  backtrack(0);
  return res;
}
💡 Recursively place queens row by row while checking column and diagonal conflict sets.
Key Takeaways
  • Main diagonal identity is $r - c$; anti-diagonal identity is $r + c$.
  • Set lookups prune invalid attack positions in $O(1)$ time.
  • Overall execution takes $O(n!)$ time.

03. Sudoku Solver

Difficulty:HardPattern:Backtracking + BitmaskTime:O(9^N)Space:O(1)

Write a program to solve a Sudoku puzzle by filling empty cells ('.'). A valid solution must satisfy the constraint that digits '1'-'9' appear once per row, column, and $3 \times 3$ sub-box.

How It Works & Algorithmic Design

Solves using Bitmask State Constraint Backtracking:

  1. Constraint Hash/Bitmasks: Track digits used in rows[r], cols[c], and boxes[boxIdx].
  2. Cell Processing: Find next empty cell (r, c):
    • Try placing digits $d \in [1, 9]$:
      • Check if bit for $d$ is clear in row, col, and box bitmasks.
      • Toggle bit mask, update board cell board[r][c] = d.
      • Recurse to next empty cell.
      • If recursion succeeds, return true.
      • Backtrack: un-toggle bit mask, reset cell to '.'.

Why This Approach Works Best

Bitwise checks make validation $O(1)$, rapidly terminating invalid grid paths.

Example Walkthrough
Input: 9x9 grid with '.' empty cells
Unsolved Sudoku matrix.
Validation: Each 1-9 digit appears once in every row, column, and 3x3 block.
Standard rules.
Output: Fully filled valid 9x9 board
In-place board mutation.

Answer: Sudoku Solver implementation

function solveSudoku(board) {
  const rows = new Array(9).fill(0);
  const cols = new Array(9).fill(0);
  const boxes = new Array(9).fill(0);
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== '.') {
        const val = Number(board[r][c]);
        const mask = 1 << val;
        const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
        rows[r] |= mask; cols[c] |= mask; boxes[b] |= mask;
      }
    }
  }
  function solve(r, c) {
    if (r === 9) return true;
    if (c === 9) return solve(r + 1, 0);
    if (board[r][c] !== '.') return solve(r, c + 1);
    const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
    for (let val = 1; val <= 9; val++) {
      const mask = 1 << val;
      if (!(rows[r] & mask) && !(cols[c] & mask) && !(boxes[b] & mask)) {
        rows[r] |= mask; cols[c] |= mask; boxes[b] |= mask;
        board[r][c] = String(val);
        if (solve(r, c + 1)) return true;
        rows[r] &= ~mask; cols[c] &= ~mask; boxes[b] &= ~mask;
        board[r][c] = '.';
      }
    }
    return false;
  }
  solve(0, 0);
}
💡 Backtrack across empty cells while tracking digit constraints using bitmasks.
Key Takeaways
  • Box index calculated via (r / 3) * 3 + (c / 3).
  • Bitwise masks make $O(1)$ digit availability checks.
  • Modifies board array directly in-place.

04. Expression Add Operators

Difficulty:HardPattern:Combinatorial BacktrackingTime:O(4^N)Space:O(N)

Given a string num containing only digits and an integer target, return all possibilities to insert binary operators '+', '-', or '*' between the digits so that the resulting expression evaluates to target.

How It Works & Algorithmic Design

Solves using Operator Choice Backtracking with Multiplication Precedence Tracking:

  1. DFS Signature: dfs(index, path, eval, multed).
  2. Branch Choice: Extract substring currStr = num[index...i] with numeric value curr.
    • Skip leading zero multi-digit strings (e.g. '05').
  3. Operations:
    • Start position (index === 0): dfs(i + 1, currStr, curr, curr).
    • Addition +: dfs(i + 1, path + '+' + currStr, eval + curr, curr).
    • Subtraction -: dfs(i + 1, path + '-' + currStr, eval - curr, -curr).
    • Multiplication *: Undo last term addition then add product: dfs(i + 1, path + '*' + currStr, eval - multed + multed * curr, multed * curr).

Why This Approach Works Best

Tracking multed handles operator precedence naturally during left-to-right recursion.

Example Walkthrough
Input: num = "123", target = 6
Evaluate expression options.
Matches: "1+2+3" = 6 and "1*2*3" = 6.
Valid generated strings.
Output: ["1+2+3", "1*2*3"]
All valid operators.

Answer: Expression Add Operators implementation

function addOperators(num, target) {
  const res = [];
  function dfs(index, path, evalVal, multed) {
    if (index === num.length) {
      if (evalVal === target) res.push(path);
      return;
    }
    for (let i = index; i < num.length; i++) {
      if (i !== index && num[index] === '0') break;
      const str = num.substring(index, i + 1);
      const curr = Number(str);
      if (index === 0) {
        dfs(i + 1, str, curr, curr);
      } else {
        dfs(i + 1, path + '+' + str, evalVal + curr, curr);
        dfs(i + 1, path + '-' + str, evalVal - curr, -curr);
        dfs(i + 1, path + '*' + str, evalVal - multed + multed * curr, multed * curr);
      }
    }
  }
  dfs(0, '', 0, 0);
  return res;
}
💡 Recursively split digits into terms, testing plus, minus, and times operator additions.
Key Takeaways
  • Prune numbers with leading zeroes (e.g. '05').
  • Subtract multed from running evaluation before adding product term.
  • Explores $O(4^N)$ search paths.

05. Basic Calculator

Difficulty:HardPattern:Stack Math Expression ParserTime:O(n)Space:O(n)

Given a string s representing a valid expression containing digits, '+', '-', '(', and ')', evaluate the expression and return its value.

How It Works & Algorithmic Design

Solves using Linear Scan Stack Parentheses State Preservation:

  1. Variables: sum = 0, sign = 1, stack = [].
  2. Scan String:
    • Digit: parse complete number $N$, update sum += sign * N.
    • Operator +: set sign = 1.
    • Operator -: set sign = -1.
    • Open Parenthesis '(': push current sum and sign onto stack, reset sum = 0, sign = 1.
    • Close Parenthesis ')': pop prevSign and prevSum from stack; set sum = prevSum + prevSign * sum.

Why This Approach Works Best

Evaluates nested parenthesis expressions in a single pass $O(n)$ time and $O(n)$ stack space.

Example Walkthrough
Input: s = "(1+(4+5+2)-3)+(6+8)"
Nested math string.
Evaluation: (1+11-3) + 14 = 9 + 14 = 23
Evaluated calculation.
Output: 23
Final computed integer.

Answer: Basic Calculator implementation

function calculate(s) {
  let sum = 0, sign = 1;
  const stack = [];
  let i = 0;
  while (i < s.length) {
    const ch = s[i];
    if (ch >= '0' && ch <= '9') {
      let num = 0;
      while (i < s.length && s[i] >= '0' && s[i] <= '9') {
        num = num * 10 + Number(s[i++]);
      }
      sum += sign * num;
      continue;
    } else if (ch === '+') sign = 1;
    else if (ch === '-') sign = -1;
    else if (ch === '(') {
      stack.push(sum);
      stack.push(sign);
      sum = 0; sign = 1;
    } else if (ch === ')') {
      sum = stack.pop() * sum + stack.pop();
    }
    i++;
  }
  return sum;
}
💡 Evaluate expressions linearly using a stack to preserve sum and sign context across parentheses.
Key Takeaways
  • Parentheses save scope state onto stack.
  • Handles nested expressions in $O(n)$ linear time.
  • Consumes minimal space bounded by depth of nested parentheses.

06. Erect the Fence (Convex Hull Graham Scan)

Difficulty:HardPattern:Convex Hull Monotone ChainTime:O(n log n)Space:O(n)

Given an array trees where trees[i] = [x, y] represents the location of a tree in the garden, return the coordinates of trees that are located on the perimeter of the fence enclosing all trees (Convex Hull).

How It Works & Algorithmic Design

Solves using Andrew's Monotone Chain Convex Hull Algorithm:

  1. Sort: Sort points primarily by x-coordinate, secondarily by y-coordinate.
  2. Cross Product Helper: cross(p1, p2, p3) determines orientation of turns.
  3. Build Upper & Lower Hulls:
    • Loop through sorted points and construct lower hull using stack.
    • Pop points from stack while cross product indicates non-left turn (cross < 0).
    • Repeat procedure in reverse to construct upper hull.
  4. Combine & Deduplicate: Merge lower and upper hull sets.

Why This Approach Works Best

Monotone chain processes geometric points cleanly in $O(n \log n)$ time.

Example Walkthrough
Input Coordinates: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
2D trees points.
Convex Perimeter: Outer points enclosing all internal trees.
Fence boundary.
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Hull boundary points.

Answer: Erect the Fence Monotone Chain implementation

function outerTrees(trees) {
  trees.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
  function cross(p1, p2, p3) {
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);
  }
  const lower = [], upper = [];
  for (const p of trees) {
    while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], p) < 0) {
      lower.pop();
    }
    lower.push(p);
  }
  for (let i = trees.length - 1; i >= 0; i--) {
    const p = trees[i];
    while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], p) < 0) {
      upper.pop();
    }
    upper.push(p);
  }
  const set = new Set();
  const res = [];
  for (const p of [...lower, ...upper]) {
    const key = `${p[0]},${p[1]}`;
    if (!set.has(key)) {
      set.add(key);
      res.push(p);
    }
  }
  return res;
}
💡 Construct upper and lower convex hulls by sorting points and checking cross-product orientation.
Key Takeaways
  • Cross product sign determines left vs right geometric turns.
  • Monotone chain constructs lower and upper perimeter hulls independently.
  • Time complexity $O(n \log n)$ due to initial point sorting.

07. Max Points on a Line

Difficulty:HardPattern:GCD Slope Hash MapTime:O(n^2)Space:O(n)

Given an array of points where points[i] = [x_i, y_i] represents a point on the 2D plane, return the maximum number of points that lie on the same straight line.

How It Works & Algorithmic Design

Solves using GCD Reduced Normalized Slope Frequency Maps:

  1. Outer Loop: Pick anchor point $i$.
  2. Inner Loop: For each point $j > i$:
    • Compute $\Delta x = x_j - x_i$, $\Delta y = y_j - y_i$.
    • Normalize slope fraction using Greatest Common Divisor: g = gcd(|dx|, |dy|). Divide both by g.
    • Ensure canonical sign (e.g. dx > 0 or if dx === 0, dy = 1).
    • Store slope string key "dy/dx" in frequency map.
  3. Track Maximum: maxPoints = Math.max(maxPoints, slopeMap[key] + 1).

Why This Approach Works Best

Normalizing slopes using GCD avoids floating point precision issues across arbitrary lines in $O(n^2)$ time.

Example Walkthrough
Input Points: [[1,1],[2,2],[3,3]]
Points array.
Slope Alignment: All three points share identical reduced slope 1/1.
Collinear points.
Output: 3
Maximum points on a line.

Answer: Max Points on a Line implementation

function maxPoints(points) {
  if (points.length <= 2) return points.length;
  let maxCount = 0;
  function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
  }
  for (let i = 0; i < points.length; i++) {
    const map = new Map();
    let localMax = 0;
    for (let j = i + 1; j < points.length; j++) {
      let dx = points[j][0] - points[i][0];
      let dy = points[j][1] - points[i][1];
      const g = gcd(Math.abs(dx), Math.abs(dy));
      dx /= g; dy /= g;
      if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
      const key = `${dy}/${dx}`;
      map.set(key, (map.get(key) || 0) + 1);
      localMax = Math.max(localMax, map.get(key));
    }
    maxCount = Math.max(maxCount, localMax + 1);
  }
  return maxCount;
}
💡 Iterate over anchor points and map collinear frequencies using GCD-reduced slope representations.
Key Takeaways
  • Use GCD tuple reduction to avoid floating point division inaccuracies.
  • Anchor points eliminate duplicate backward line checks.
  • Executes in $O(n^2)$ quadratic time.

08. Integer to English Words

Difficulty:HardPattern:3-Digit Chunk ParsingTime:O(1)Space:O(1)

Convert a non-negative integer num to its English words representation.

How It Works & Algorithmic Design

Solves using Chunking by Thousands with Static Word Arrays:

  1. Static Lookup Arrays: Define arrays for units ["", "One", ...], teens ["Ten", "Eleven", ...], tens ["", "", "Twenty", ...], and thousands ["", "Thousand", "Million", "Billion"].
  2. Three-Digit Helper helper(n):
    • If $n < 20$, lookup units/teens.
    • If $n < 100$, return tens[n/10] + helper(n%10).
    • If $n \ge 100$, return units[n/100] + " Hundred " + helper(n%100).
  3. Loop Thousands: Process num in 3-digit chunks, appending thousand group names.

Why This Approach Works Best

Recursively converts 3-digit groups in $O(1)$ constant time.

Example Walkthrough
Input: num = 1234567
Target integer.
Chunks: 1 (Million) + 234 (Thousand) + 567
3-digit groups.
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Converted text.

Answer: Integer to English Words implementation

function numberToWords(num) {
  if (num === 0) return 'Zero';
  const LESS_THAN_20 = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen'];
  const TENS = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety'];
  const THOUSANDS = ['', 'Thousand', 'Million', 'Billion'];
  function helper(n) {
    if (n === 0) return '';
    else if (n < 20) return LESS_THAN_20[n] + ' ';
    else if (n < 100) return TENS[Math.floor(n / 10)] + ' ' + helper(n % 10);
    else return LESS_THAN_20[Math.floor(n / 100)] + ' Hundred ' + helper(n % 100);
  }
  let res = '', i = 0;
  while (num > 0) {
    if (num % 1000 !== 0) {
      res = helper(num % 1000) + THOUSANDS[i] + ' ' + res;
    }
    num = Math.floor(num / 1000);
    i++;
  }
  return res.trim().replace(/\s+/g, ' ');
}
💡 Parse number in groups of 3 digits appending Thousand, Million, and Billion suffix scale tags.
Key Takeaways
  • Chunks integers into 3-digit groups (thousands scale).
  • Helper function handles standard sub-1000 numbers recursively.
  • Executes in $O(1)$ bounded time.

09. Subsets II (Duplicates Handling)

Difficulty:HardPattern:Backtracking Duplicate SkipTime:O(2^n)Space:O(n)

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

How It Works & Algorithmic Design

Solves using Sorted Input Backtracking with Duplicate Pruning:

  1. Sort: Sort nums so identical values are adjacent.
  2. Backtracking DFS dfs(start, path):
    • Push copy of path to results.
    • Loop $i$ from start to nums.length:
      • Duplicate Pruning: If $i > \text{start}$ and nums[i] === nums[i - 1], continue.
      • Add nums[i] to path.
      • Recurse dfs(i + 1, path).
      • Backtrack: remove nums[i].

Why This Approach Works Best

Pruning duplicate branches at the loop level prevents duplicate subsets without needing post-processing hash sets.

Example Walkthrough
Input: nums = [1, 2, 2]
Array with duplicate values.
Pruned Branching: Skip second '2' at loop level $i > start$.
Avoids identical power set outputs.
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Unique subsets.

Answer: Subsets II implementation

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  function backtrack(start, path) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return res;
}
💡 Sort array to bring duplicate elements together and skip duplicate sibling branch calls.
Key Takeaways
  • Sort input array first to group identical elements.
  • Skip condition i > start && nums[i] === nums[i-1] prevents duplicate subtree calls.
  • Generates all $2^n$ subsets without hash set overhead.

10. Permutation Sequence

Difficulty:HardPattern:Factorial Math Block ParsingTime:O(n^2)Space:O(n)

The set [1, 2, 3, ..., n] contains n! unique permutations. Given n and k, return the $k$-th permutation sequence.

How It Works & Algorithmic Design

Solves using Factorial Block Deconstruction:

  1. Factorial Lookup: Precompute factorials: fact[i] = i!.
  2. Numbers List: Build array numbers = [1, 2, ..., n].
  3. Zero-Indexing: Set k = k - 1.
  4. Group Selection Loop (from $i = n$ down to $1$):
    • Block size $S = (i - 1)!$.
    • Index $idx = \lfloor k / S \rfloor$.
    • Append numbers[idx] to result string and remove from numbers.
    • Update k = k % S.

Why This Approach Works Best

Calculates the $k$-th permutation directly in $O(n^2)$ time, avoiding $O(n!)$ generation.

Example Walkthrough
Input: n = 3, k = 3
Target permutation.
Permutation List: 1: "123", 2: "132", 3: "213", 4: "231"...
Ordered permutations.
Output: "213"
3rd permutation sequence.

Answer: Permutation Sequence implementation

function getPermutation(n, k) {
  const numbers = Array.from({ length: n }, (_, i) => i + 1);
  const fact = [1];
  for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
  k--; // Convert to 0-based index
  let res = '';
  for (let i = n; i >= 1; i--) {
    const idx = Math.floor(k / fact[i - 1]);
    res += numbers[idx];
    numbers.splice(idx, 1);
    k %= fact[i - 1];
  }
  return res;
}
💡 Directly locate target permutation digits using factorial block division.
Key Takeaways
  • Converts $k$ to 0-based indexing first.
  • Determines digits directly using block division by $(i-1)!$.
  • Runs in $O(n^2)$ time due to list element removal.

STAY UPDATED WITH BYTES!

© 2026 Bytes4Dev. All rights reserved.

v.0.4.0