DEV Community: Bhuvaneswari Shanker

DSA pattern cheatsheet for TS

Bhuvaneswari Shanker — Fri, 12 Sep 2025 10:14:49 +0000

Compiled the following list of patterns and examples from ChatGPT for quick reference in the future.

Pattern	Best	Avg	Worst	Space
Two Pointers	O(n)	O(n)	O(n)	O(1)
Sliding Window	O(n)	O(n)	O(n)	O(1)/O(k)
Fast & Slow Pointers	O(n)	O(n)	O(n)	O(1)
Merge Intervals	—	O(n log n)	O(n log n)	O(n)
Cyclic Sort	O(n)	O(n)	O(n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1)
DFS / BFS	O(V+E)	O(V+E)	O(V+E)	O(V)
Backtracking	O(1)	Exp	O(b^d)	O(d)+out
Dynamic Programming	Varies	Poly	O(n²)	O(n)/O(n²)
Greedy	O(n)	O(n log n)	O(n log n)	O(1)/O(n)
Heap / Priority Queue	O(n)	O(n log n)	O(n log n)	O(n)
Union Find (DSU)	~O(1)	~O(α(n))	~O(α(n))	O(n)
Topological Sort	O(V+E)	O(V+E)	O(V+E)	O(V)

📑 Index – DSA Patterns

Two Pointers

Use when checking pairs/subarrays in sorted data.
Sliding Window

Great for substrings/subarrays with max/min/unique.
Fast & Slow Pointers (Cycle Detection)

Detect cycles or find middle in linked lists.
Merge Intervals

When working with overlapping intervals.
Cyclic Sort

Perfect for finding missing/duplicate in 1..n arrays.
Binary Search

When data is sorted and you need to search quickly.
DFS / BFS

Traverse graphs/trees or explore grids.
Backtracking

Generate all combinations/permutations/choices.
Dynamic Programming (DP)

Optimal for overlapping subproblems & recursion.
Greedy

Pick local best to build global solution.
Heap / Priority Queue

For top-k, scheduling, median, streaming data.
Union Find (Disjoint Set Union - DSU)

Check connectivity / detect cycles efficiently.
Topological Sort

Order tasks/nodes with dependencies (DAG).

📘 DSA Patterns & Problem Examples

This file contains common DSA patterns and 10 example problems for each pattern.

Two Pointers

Pair with Target Sum (sorted array)
Remove Duplicates from Sorted Array
Valid Palindrome Check
Container With Most Water
3Sum Problem
4Sum Problem
Trapping Rain Water
Sort Colors (Dutch National Flag)
Subarray Product Less than K
Minimum Window Subsequence

Two Pointers — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Two Pointers example.

Pair with Target Sum (sorted array)

Given a sorted array of integers and a target value, return indices of the two numbers such that they add up to the target.

Sample Input: nums = [1,2,3,4,6], target = 6

Sample Output: [1,3] # indices (0-based) of 2 and 4

// Two-pointer approach for pair with target sum (sorted array)
function pairWithTargetSum(nums: number[], target: number): [number, number] | null {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;
}
// Example:
console.log(pairWithTargetSum([1,2,3,4,6], 6)); // [1,3]

Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length.

Sample Input: nums = [0,0,1,1,1,2,2,3,3,4]

Sample Output: 5 and nums becomes [0,1,2,3,4,...]

// Remove duplicates in-place and return new length
function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[read - 1]) {
      nums[write++] = nums[read];
    }
  }
  return write;
}
// Example:
const arr = [0,0,1,1,1,2,2,3,3,4];
console.log(removeDuplicates(arr)); // 5
console.log(arr.slice(0,5)); // [0,1,2,3,4]

Valid Palindrome Check

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Sample Input: s = "A man, a plan, a canal: Panama"

Sample Output: true

// Valid palindrome: alphanumeric only, case-insensitive
function isPalindrome(s: string): boolean {
  let left = 0, right = s.length - 1;
  while (left < right) {
    while (left < right && !/[0-9a-zA-Z]/.test(s[left])) left++;
    while (left < right && !/[0-9a-zA-Z]/.test(s[right])) right--;
    if (left < right && s[left].toLowerCase() !== s[right].toLowerCase()) return false;
    left++; right--;
  }
  return true;
}
// Example:
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true

Container With Most Water

Given height array where each element represents vertical line at x coordinate, find two lines that together with x-axis forms a container, maximize the container area. Return max area.

Sample Input: height = [1,8,6,2,5,4,8,3,7]

Sample Output: 49

// Container With Most Water two-pointer solution
function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1, maxA = 0;
  while (left < right) {
    const width = right - left;
    const area = Math.min(height[left], height[right]) * width;
    maxA = Math.max(maxA, area);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return maxA;
}
// Example:
console.log(maxArea([1,8,6,2,5,4,8,3,7])); // 49

3Sum Problem

Given array nums, return all unique triplets [a,b,c] such that a+b+c == 0.

Sample Input: nums = [-1,0,1,2,-1,-4]

Sample Output: [[-1,-1,2],[-1,0,1]]

// 3Sum using sorting + two pointers
function threeSum(nums: number[]): number[][] {
  nums.sort((a,b)=>a-b);
  const res: number[][] = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i-1]) continue;
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        res.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left+1]) left++;
        while (left < right && nums[right] === nums[right-1]) right--;
        left++; right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return res;
}
// Example:
console.log(threeSum([-1,0,1,2,-1,-4]));

4Sum Problem

Given array nums and target, return all unique quadruplets that sum to target.

Sample Input: nums = [1,0,-1,0,-2,2], target = 0

Sample Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

// 4Sum using sorting + two pointers (nested loops)
function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a,b)=>a-b);
  const res: number[][] = [];
  const n = nums.length;
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i-1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j-1]) continue;
      let left = j + 1, right = n - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          res.push([nums[i], nums[j], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left+1]) left++;
          while (left < right && nums[right] === nums[right-1]) right--;
          left++; right--;
        } else if (sum < target) left++;
        else right--;
      }
    }
  }
  return res;
}
// Example:
console.log(fourSum([1,0,-1,0,-2,2], 0));

Trapping Rain Water

Given height array representing elevation map, compute how much water it is able to trap after raining.

Sample Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Sample Output: 6

// Trapping Rain Water using two pointers
function trap(height: number[]): number {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) leftMax = height[left];
      else water += leftMax - height[left];
      left++;
    } else {
      if (height[right] >= rightMax) rightMax = height[right];
      else water += rightMax - height[right];
      right--;
    }
  }
  return water;
}
// Example:
console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6

Sort Colors (Dutch National Flag)

Sort an array with values 0,1,2 (colors) in-place so that same colors are adjacent (Dutch National Flag).

Sample Input: nums = [2,0,2,1,1,0]

Sample Output: [0,0,1,1,2,2]

// Dutch National Flag algorithm (one-pass)
function sortColors(nums: number[]): void {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++; mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else { // 2
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}
// Example:
const arr2 = [2,0,2,1,1,0];
sortColors(arr2);
console.log(arr2); // [0,0,1,1,2,2]

Subarray Product Less than K

Given an array of positive integers nums and integer k, find the number of contiguous subarrays where the product of all the elements is less than k.

Sample Input: nums = [10,5,2,6], k = 100

Sample Output: 8

// Count subarrays with product less than k using sliding two-pointer window
function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k <= 1) return 0;
  let prod = 1, left = 0, count = 0;
  for (let right = 0; right < nums.length; right++) {
    prod *= nums[right];
    while (prod >= k && left <= right) {
      prod /= nums[left++];
    }
    count += right - left + 1;
  }
  return count;
}
// Example:
console.log(numSubarrayProductLessThanK([10,5,2,6], 100)); // 8

Minimum Window Subsequence

Given strings S and T, find the minimum window in S which will contain T as a subsequence. (Not substring)

Sample Input: S = "abcdebdde", T = "bde"

Sample Output: bcde (one valid minimal window)

// Minimum Window Subsequence (DP-ish + two-pointer scanning approach)
// This is a concise implementation suitable for interview-style answers.
function minWindowSubsequence(S: string, T: string): string {
  const m = S.length, n = T.length;
  let minLen = Infinity, start = -1;
  for (let i = 0; i < m; i++) {
    if (S[i] !== T[0]) continue;
    let si = i, ti = 0;
    // advance to match T as subsequence
    while (si < m) {
      if (S[si] === T[ti]) ti++;
      if (ti === n) break;
      si++;
    }
    if (ti !== n) break; // can't find further
    // now work backward to minimize window
    let end = si;
    ti = n - 1;
    while (si >= i) {
      if (S[si] === T[ti]) ti--;
      if (ti < 0) break;
      si--;
    }
    const len = end - si + 1;
    if (len < minLen) {
      minLen = len;
      start = si;
    }
  }
  return start === -1 ? "" : S.slice(start, start + minLen);
}
// Example:
console.log(minWindowSubsequence("abcdebdde", "bde")); // "bcde"

Sliding Window

Maximum Sum Subarray of Size K
Smallest Subarray with Given Sum
Longest Substring Without Repeating Characters
Longest Substring with K Distinct Characters
Permutation in String
Minimum Window Substring
Max Consecutive Ones III
Longest Repeating Character Replacement
Fruits into Baskets
Longest Subarray of Ones after Replacement

Sliding Window — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Sliding Window example.

Maximum Sum Subarray of Size K

Given an array of integers and a number k, find the maximum sum of any contiguous subarray of size k.

Sample Input: nums = [2,1,5,1,3,2], k = 3

Sample Output: 9 # subarray [5,1,3]

// Maximum sum subarray of size k (sliding window)
function maxSubarrayOfSizeK(nums: number[], k: number): number {
  if (nums.length < k) return 0;
  let maxSum = 0, windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];
  maxSum = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}
// Example:
console.log(maxSubarrayOfSizeK([2,1,5,1,3,2], 3)); // 9

Smallest Subarray with Given Sum

Given an array of positive integers and a target sum S, find the length of the smallest contiguous subarray whose sum is at least S. Return 0 if none.

Sample Input: nums = [2,1,5,2,3,2], S = 7

Sample Output: 2 # subarray [5,2]

// Smallest subarray with sum >= S
function smallestSubarrayWithSum(nums: number[], S: number): number {
  let minLen = Infinity, left = 0, sum = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= S) {
      minLen = Math.min(minLen, right - left + 1);
      sum -= nums[left++];
    }
  }
  return minLen === Infinity ? 0 : minLen;
}
// Example:
console.log(smallestSubarrayWithSum([2,1,5,2,3,2], 7)); // 2

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Sample Input: s = "abcabcbb"

Sample Output: 3 # "abc"

// Longest substring without repeating characters
function lengthOfLongestSubstring(s: string): number {
  const seen = new Map<string, number>();
  let left = 0, maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (seen.has(ch) && seen.get(ch)! >= left) {
      left = seen.get(ch)! + 1;
    }
    seen.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}
// Example:
console.log(lengthOfLongestSubstring("abcabcbb")); // 3

Longest Substring with K Distinct Characters

Given a string, find the length of the longest substring that contains at most k distinct characters.

Sample Input: s = "eceba", k = 2

Sample Output: 3 # "ece"

// Longest substring with at most k distinct characters
function longestKDistinct(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0, maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    freq.set(s[right], (freq.get(s[right]) || 0) + 1);
    while (freq.size > k) {
      freq.set(s[left], freq.get(s[left])! - 1);
      if (freq.get(s[left]) === 0) freq.delete(s[left]);
      left++;
    }
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}
// Example:
console.log(longestKDistinct("eceba", 2)); // 3

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1.

Sample Input: s1 = "ab", s2 = "eidbaooo"

Sample Output: true ("ba" exists)

// Check if s2 contains permutation of s1
function checkInclusion(s1: string, s2: string): boolean {
  if (s1.length > s2.length) return false;
  const need = new Array(26).fill(0);
  const window = new Array(26).fill(0);
  for (let i = 0; i < s1.length; i++) need[s1.charCodeAt(i)-97]++;
  for (let i = 0; i < s2.length; i++) {
    window[s2.charCodeAt(i)-97]++;
    if (i >= s1.length) window[s2.charCodeAt(i - s1.length)-97]--;
    if (need.every((v, idx) => v === window[idx])) return true;
  }
  return false;
}
// Example:
console.log(checkInclusion("ab", "eidbaooo")); // true

Minimum Window Substring

Given strings s and t, find the minimum window in s which will contain all the characters in t (including multiplicity). Return empty string if no such window.

Sample Input: s = "ADOBECODEBANC", t = "ABC"

Sample Output: BANC

// Minimum window substring (classic sliding window)
function minWindow(s: string, t: string): string {
  if (!s || !t) return "";
  const need = new Map<string, number>();
  for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
  let left = 0, minLen = Infinity, minStart = 0, missing = t.length;
  for (let right = 0; right < s.length; right++) {
    const rc = s[right];
    if ((need.get(rc) || 0) > 0) missing--;
    need.set(rc, (need.get(rc) || 0) - 1);
    while (missing === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      const lc = s[left];
      need.set(lc, (need.get(lc) || 0) + 1);
      if (need.get(lc)! > 0) missing++;
      left++;
    }
  }
  return minLen === Infinity ? "" : s.slice(minStart, minStart + minLen);
}
// Example:
console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"

Max Consecutive Ones III

Given a binary array and an integer k, return the maximum number of consecutive 1s in the array if you can flip at most k zeros.

Sample Input: nums = [1,1,1,0,0,1,1,0,1,1,1], k = 2

Sample Output: 6

// Max Consecutive Ones III using sliding window
function longestOnes(nums: number[], k: number): number {
  let left = 0, zeros = 0, maxLen = 0;
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;
    while (zeros > k) {
      if (nums[left] === 0) zeros--;
      left++;
    }
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}
// Example:
console.log(longestOnes([1,1,1,0,0,1,1,0,1,1,1], 2)); // 6

Longest Repeating Character Replacement

Given a string s and integer k, return the length of the longest substring that can be obtained by replacing at most k characters so that all characters in the substring are the same.

Sample Input: s = "AABABBA", k = 1

Sample Output: 4 ("AABA" -> replace one B)

// Longest Repeating Character Replacement
function characterReplacement(s: string, k: number): number {
  const freq = new Array(26).fill(0);
  let left = 0, maxCount = 0, res = 0;
  for (let right = 0; right < s.length; right++) {
    maxCount = Math.max(maxCount, ++freq[s.charCodeAt(right)-65]);
    while (right - left + 1 - maxCount > k) {
      freq[s.charCodeAt(left)-65]--;
      left++;
    }
    res = Math.max(res, right - left + 1);
  }
  return res;
}
// Example:
console.log(characterReplacement("AABABBA", 1)); // 4

Fruits into Baskets

Given an array fruits where each element is a type of fruit represented by an integer, return the length of the longest subarray containing at most two distinct fruits.

Sample Input: fruits = [1,2,1]

Sample Output: 3

// Fruits into baskets -> longest subarray with at most 2 distinct
function totalFruit(fruits: number[]): number {
  const freq = new Map<number, number>();
  let left = 0, res = 0;
  for (let right = 0; right < fruits.length; right++) {
    freq.set(fruits[right], (freq.get(fruits[right]) || 0) + 1);
    while (freq.size > 2) {
      freq.set(fruits[left], freq.get(fruits[left])! - 1);
      if (freq.get(fruits[left]) === 0) freq.delete(fruits[left]);
      left++;
    }
    res = Math.max(res, right - left + 1);
  }
  return res;
}
// Example:
console.log(totalFruit([1,2,1])); // 3

Longest Subarray of Ones after Replacement

Given a binary array and integer k, return the length of the longest subarray containing only 1s after replacing at most k zeros.

Sample Input: nums = [1,0,1,1,0,1], k = 1

Sample Output: 4

// Similar to longestOnes, sliding window allowing k zeros
function longestOnesReplacement(nums: number[], k: number): number {
  let left = 0, zeros = 0, res = 0;
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;
    while (zeros > k) {
      if (nums[left] === 0) zeros--;
      left++;
    }
    res = Math.max(res, right - left + 1);
  }
  return res;
}
// Example:
console.log(longestOnesReplacement([1,0,1,1,0,1], 1)); // 4

Fast & Slow Pointers

Linked List Cycle Detection
Linked List Cycle Length
Find the Middle of Linked List
Happy Number
Start of Linked List Cycle
Palindrome Linked List
Circular Array Loop
Rearrange Linked List (odd-even)
Remove N-th Node from End
Intersection of Two Linked Lists

Fast & Slow Pointers — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Fast & Slow Pointers example.

Linked List Cycle Detection

Given a linked list, determine if it has a cycle in it.

Sample Input: head = [3,2,0,-4] where the tail connects to node index 1 (0-based)

Sample Output: true

// Detect cycle in linked list using Floyd's Tortoise and Hare
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
// Example build:
// 3 -> 2 -> 0 -> -4 -|
//      ^------------|
// (tail connects to index 1)

Linked List Cycle Length

Given a linked list that contains a cycle, return the length of the cycle.

Sample Input: cycle of length 3 (e.g., nodes 2->0->-4->back to 2)

Sample Output: 3

// Find cycle length after detection
function cycleLength(head: ListNode | null): number {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      // compute length
      let cur = slow!, len = 0;
      do { cur = cur.next!; len++; } while (cur !== slow);
      return len;
    }
  }
  return 0; // no cycle
}

Find the Middle of Linked List

Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second middle node.

Sample Input: head = [1,2,3,4,5]

Sample Output: Node with value 3

// Find middle node: slow moves 1, fast moves 2.
function middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

Happy Number

Write an algorithm to determine if a number n is a happy number.

Sample Input: n = 19

Sample Output: true (19 -> 1^2+9^2=82 -> ... -> 1)

// Happy number using cycle detection (tortoise-hare)
function sumOfSquares(n: number): number {
  let s = 0;
  while (n > 0) {
    const d = n % 10;
    s += d * d;
    n = Math.floor(n / 10);
  }
  return s;
}

function isHappy(n: number): boolean {
  let slow = n, fast = n;
  do {
    slow = sumOfSquares(slow);
    fast = sumOfSquares(sumOfSquares(fast));
  } while (slow !== fast);
  return slow === 1;
}

Start of Linked List Cycle

Given a linked list that contains a cycle, return the node where the cycle begins. If there is no cycle, return null.

Sample Input: head where tail connects to node index 1

Sample Output: Node with index 1

// Find start of cycle using Floyd's algorithm
function detectCycle(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }
  if (!fast || !fast.next) return null;
  slow = head;
  while (slow !== fast) {
    slow = slow!.next;
    fast = fast!.next;
  }
  return slow;
}

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome.

Sample Input: head = [1,2,2,1]

Sample Output: true

// Check palindrome: find mid, reverse second half, compare
function isPalindromeList(head: ListNode | null): boolean {
  if (!head || !head.next) return true;
  // find mid
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  // reverse second half
  let prev: ListNode | null = null, cur = slow;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  // compare
  let p1 = head, p2 = prev;
  while (p2) {
    if (p1!.val !== p2.val) return false;
    p1 = p1!.next;
    p2 = p2.next;
  }
  return true;
}

Circular Array Loop

Given a circular array of integers, find if there is a cycle in the array. The cycle should be >1 in length and follow one direction (all positive or all negative).

Sample Input: nums = [2,-1,1,2,2]

Sample Output: true

// Circular Array Loop detection using fast & slow pointers
function circularArrayLoop(nums: number[]): boolean {
  const n = nums.length;
  const next = (i: number) => ((i + nums[i]) % n + n) % n;
  for (let i = 0; i < n; i++) {
    if (nums[i] === 0) continue;
    let slow = i, fast = i;
    while (true) {
      slow = next(slow);
      fast = next(next(fast));
      if (slow === fast) break;
      if (nums[slow] * nums[i] < 0 || nums[fast] * nums[i] < 0) { slow = -1; break; }
    }
    if (slow === -1) continue;
    let cur = next(slow), cnt = 1;
    while (cur !== slow) { cur = next(cur); cnt++; }
    if (cnt > 1) return true;
    // mark visited
    cur = i;
    const sign = nums[i] > 0 ? 1 : -1;
    while (nums[cur] * sign > 0) {
      const nxt = next(cur);
      nums[cur] = 0;
      cur = nxt;
    }
  }
  return false;
}

Rearrange Linked List (odd-even)

Given a singly linked list, group all odd nodes together followed by the even nodes. Preserve relative order.

Sample Input: head = [1,2,3,4,5]

Sample Output: [1,3,5,2,4]

// Odd-even linked list rearrangement
function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head) return head;
  let odd = head, even = head.next, evenHead = even;
  while (even && even.next) {
    odd.next = even.next;
    odd = odd.next!;
    even.next = odd.next;
    even = even.next;
  }
  odd.next = evenHead;
  return head;
}

Remove N-th Node from End

Given the head of a linked list, remove the n-th node from the end and return its head.

Sample Input: head = [1,2,3,4,5], n = 2

Sample Output: [1,2,3,5]

// Remove N-th node from end using two pointers (fast ahead by n)
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode | null = dummy, slow: ListNode | null = dummy;
  for (let i = 0; i < n; i++) fast = fast!.next;
  while (fast && fast.next) {
    fast = fast.next;
    slow = slow!.next;
  }
  slow!.next = slow!.next!.next;
  return dummy.next;
}

Intersection of Two Linked Lists

Given the heads of two singly linked-lists, return the node at which they intersect, or null if they do not intersect.

Sample Input: lists that intersect at node with value 8

Sample Output: Node with value 8

// Intersection using two pointers (switch heads trick)
function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  if (!headA || !headB) return null;
  let pA = headA, pB = headB;
  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }
  return pA;
}

Merge Intervals

Merge Intervals
Insert Interval
Employee Free Time
Meeting Rooms
Meeting Rooms II
Minimum Number of Arrows to Burst Balloons
Non-overlapping Intervals
Interval List Intersections
Car Pooling
Range Module

Merge Intervals — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Merge Intervals example.

Merge Intervals

Given a collection of intervals, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sample Input: [[1,3],[2,6],[8,10],[15,18]]

Sample Output: [[1,6],[8,10],[15,18]]

// Merge intervals
function mergeIntervals(intervals: number[][]): number[][] {
  if (!intervals.length) return [];
  intervals.sort((a,b) => a[0]-b[0]);
  const res: number[][] = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const [s,e] = intervals[i];
    const last = res[res.length-1];
    if (s <= last[1]) last[1] = Math.max(last[1], e);
    else res.push([s,e]);
  }
  return res;
}
// Example:
console.log(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));

Insert Interval

Given a set of non-overlapping intervals sorted by start time, insert a new interval and merge if necessary.

Sample Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Sample Output: [[1,5],[6,9]]

// Insert interval and merge
function insertInterval(intervals: number[][], newInterval: number[]): number[][] {
  const res: number[][] = [];
  let i = 0;
  // add intervals before newInterval
  while (i < intervals.length && intervals[i][1] < newInterval[0]) res.push(intervals[i++]);
  // merge overlapping
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval = [Math.min(newInterval[0], intervals[i][0]), Math.max(newInterval[1], intervals[i][1])];
    i++;
  }
  res.push(newInterval);
  // add remaining
  while (i < intervals.length) res.push(intervals[i++]);
  return res;
}
// Example:
console.log(insertInterval([[1,3],[6,9]], [2,5]));

Employee Free Time

Given schedule of multiple employees' working intervals, return the common free time intervals across all employees.

Sample Input: [[[1,2],[5,6]],[[1,3]],[[4,10]]]

Sample Output: [[3,4]]

// Employee free time
function employeeFreeTime(schedule: number[][][]): number[][] {
  const events: number[][] = [];
  for (const s of schedule) for (const it of s) events.push(it);
  events.sort((a,b)=>a[0]-b[0]);
  const merged: number[][] = [];
  for (const it of events) {
    if (!merged.length || merged[merged.length-1][1] < it[0]) merged.push([...it]);
    else merged[merged.length-1][1] = Math.max(merged[merged.length-1][1], it[1]);
  }
  const res: number[][] = [];
  for (let i = 1; i < merged.length; i++) res.push([merged[i-1][1], merged[i][0]]);
  return res;
}
// Example:
console.log(employeeFreeTime([[[1,2],[5,6]],[[1,3]],[[4,10]]]));

Meeting Rooms

Given an array of meeting time intervals consisting of start and end times, determine if a person could attend all meetings (i.e., no overlaps).

Sample Input: [[0,30],[5,10],[15,20]]

Sample Output: false

// Can attend all meetings?
function canAttendMeetings(intervals: number[][]): boolean {
  intervals.sort((a,b)=>a[0]-b[0]);
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i-1][1]) return false;
  }
  return true;
}
// Example:
console.log(canAttendMeetings([[0,30],[5,10],[15,20]])); // false

Meeting Rooms II

Given an array of meeting time intervals, return the minimum number of conference rooms required.

Sample Input: [[0,30],[5,10],[15,20]]

Sample Output: 2

// Meeting Rooms II using min-heap (simulate with array)
function minMeetingRooms(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals.sort((a,b)=>a[0]-b[0]);
  const heap: number[] = []; // store end times
  for (const [s,e] of intervals) {
    // remove rooms that are free
    heap.sort((a,b)=>a-b);
    if (heap.length && heap[0] <= s) heap.shift();
    heap.push(e);
  }
  return heap.length;
}
// Example:
console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2

Minimum Number of Arrows to Burst Balloons

Given points representing horizontal diameter of balloons, return minimum number of arrows to burst all balloons (arrow shot vertically).

Sample Input: [[10,16],[2,8],[1,6],[7,12]]

Sample Output: 2

// Min arrows to burst balloons (greedy by end time)
function findMinArrowShots(points: number[][]): number {
  if (!points.length) return 0;
  points.sort((a,b)=>a[1]-b[1]);
  let arrows = 1, prevEnd = points[0][1];
  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > prevEnd) { arrows++; prevEnd = points[i][1]; }
  }
  return arrows;
}
// Example:
console.log(findMinArrowShots([[10,16],[2,8],[1,6],[7,12]])); // 2

Non-overlapping Intervals

Given intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping.

Sample Input: [[1,2],[2,3],[3,4],[1,3]]

Sample Output: 1

// Minimum intervals to remove to avoid overlaps
function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals.sort((a,b)=>a[1]-b[1]);
  let count = 0, prevEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < prevEnd) count++;
    else prevEnd = intervals[i][1];
  }
  return count;
}
// Example:
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1

Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return their intersection.

Sample Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]

Sample Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

// Interval list intersections
function intervalIntersection(A: number[][], B: number[][]): number[][] {
  const res: number[][] = [];
  let i=0, j=0;
  while (i < A.length && j < B.length) {
    const lo = Math.max(A[i][0], B[j][0]);
    const hi = Math.min(A[i][1], B[j][1]);
    if (lo <= hi) res.push([lo, hi]);
    if (A[i][1] < B[j][1]) i++; else j++;
  }
  return res;
}
// Example:
console.log(intervalIntersection([[0,2],[5,10],[13,23],[24,25]], [[1,5],[8,12],[15,24],[25,26]]));

Car Pooling

Given trips where each trip is [numPassengers, startLocation, endLocation] and vehicle capacity, return true if you can pick up and drop off all passengers for all the given trips.

Sample Input: trips = [[2,1,5],[3,3,7]], capacity = 4

Sample Output: false

// Car pooling using difference array
function carPooling(trips: number[][], capacity: number): boolean {
  const events: number[] = [];
  for (const [p, s, e] of trips) {
    events.push(s, p);
    events.push(e, -p);
  }
  // Transform to map of location->delta (simple approach)
  const map = new Map<number, number>();
  for (let i = 0; i < events.length; i += 2) {
    map.set(events[i], (map.get(events[i]) || 0) + events[i+1]);
  }
  const locations = Array.from(map.keys()).sort((a,b)=>a-b);
  let curr = 0;
  for (const loc of locations) {
    curr += map.get(loc)!;
    if (curr > capacity) return false;
  }
  return true;
}
// Example:
console.log(carPooling([[2,1,5],[3,3,7]], 4)); // false

Range Module

Implement a Range Module to add, query and remove ranges. (Simplified example: check if a given range is covered after adding some ranges.)

Sample Input: addRange([10,20]), queryRange(14,16) -> true

Sample Output: true

// Simplified Range Module example (store merged intervals)
class RangeModule {
  intervals: number[][] = [];
  addRange(left: number, right: number) {
    this.intervals.push([left,right]);
    this.intervals.sort((a,b)=>a[0]-b[0]);
    const merged: number[][] = [];
    for (const it of this.intervals) {
      if (!merged.length || merged[merged.length-1][1] < it[0]) merged.push([...it]);
      else merged[merged.length-1][1] = Math.max(merged[merged.length-1][1], it[1]);
    }
    this.intervals = merged;
  }
  queryRange(left:number, right:number) {
    for (const [s,e] of this.intervals) if (s <= left && e >= right) return true;
    return false;
  }
}
// Example:
const rm = new RangeModule();
rm.addRange(10,20);
console.log(rm.queryRange(14,16)); // true

Cyclic Sort

Cyclic Sort (basic)
Find the Missing Number
Find All Numbers Disappeared in an Array
Find the Duplicate Number
Find All Duplicates in an Array
Set Mismatch
First Missing Positive
Find Error Numbers
Kth Missing Positive Number
Smallest Missing Positive

Cyclic Sort — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Cyclic Sort example.

Cyclic Sort (basic)

Given an array containing numbers from 1..n in arbitrary order (may contain duplicates), rearrange the array so that nums[i] == i+1 wherever possible using cyclic sort.

Sample Input: nums = [3,1,5,4,2]

Sample Output: [1,2,3,4,5]

// In-place cyclic sort for values in range 1..n
function cyclicSort(nums: number[]): void {
  let i = 0;
  while (i < nums.length) {
    const correctIdx = nums[i] - 1;
    if (nums[i] >= 1 && nums[i] <= nums.length && nums[i] !== nums[correctIdx]) {
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    } else {
      i++;
    }
  }
}
// Example:
const a = [3,1,5,4,2];
cyclicSort(a);
console.log(a); // [1,2,3,4,5]

Find the Missing Number

Given an array nums containing n distinct numbers taken from the range [0, n], return the one number missing from the array.

Sample Input: nums = [3,0,1]

Sample Output: 2

// Missing number from 0..n (use cyclic placement or XOR/sum). Here: cyclic-like placement.
function missingNumber(nums: number[]): number {
  let i = 0;
  while (i < nums.length) {
    const v = nums[i];
    if (v < nums.length && nums[i] !== nums[v]) {
      [nums[i], nums[v]] = [nums[v], nums[i]];
    } else {
      i++;
    }
  }
  for (let idx = 0; idx < nums.length; idx++) {
    if (nums[idx] !== idx) return idx;
  }
  return nums.length;
}
// Example:
console.log(missingNumber([3,0,1])); // 2

Find All Numbers Disappeared in an Array

Given an array nums of length n where 1 ≤ nums[i] ≤ n, return all the integers in the range [1, n] that do not appear in nums.

Sample Input: nums = [4,3,2,7,8,2,3,1]

Sample Output: [5,6]

// Find disappeared numbers using cyclic placement
function findDisappearedNumbers(nums: number[]): number[] {
  let i = 0;
  while (i < nums.length) {
    const correctIdx = nums[i] - 1;
    if (nums[i] !== nums[correctIdx]) {
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    } else {
      i++;
    }
  }
  const res: number[] = [];
  for (let idx = 0; idx < nums.length; idx++) {
    if (nums[idx] !== idx + 1) res.push(idx + 1);
  }
  return res;
}
// Example:
console.log(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // [5,6]

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is exactly one repeated number. Find this repeated number.

Sample Input: nums = [1,3,4,2,2]

Sample Output: 2

// Find duplicate using cyclic placement (or Floyd). Here: cyclic placement.
function findDuplicate(nums: number[]): number {
  let i = 0;
  while (i < nums.length) {
    const correctIdx = nums[i] - 1;
    if (nums[i] !== nums[correctIdx]) {
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    } else {
      if (i !== correctIdx) return nums[i];
      i++;
    }
  }
  return -1;
}
// Example:
console.log(findDuplicate([1,3,4,2,2])); // 2

Find All Duplicates in an Array

Given an integer array of length n where 1 ≤ nums[i] ≤ n, some elements appear twice and others once. Return all the elements that appear twice.

Sample Input: nums = [4,3,2,7,8,2,3,1]

Sample Output: [2,3]

// Find all duplicates via cyclic placement
function findDuplicates(nums: number[]): number[] {
  let i = 0;
  while (i < nums.length) {
    const correctIdx = nums[i] - 1;
    if (nums[i] !== nums[correctIdx]) {
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    } else {
      i++;
    }
  }
  const res: number[] = [];
  for (let idx = 0; idx < nums.length; idx++) {
    if (nums[idx] !== idx + 1) res.push(nums[idx]);
  }
  return res;
}
// Example:
console.log(findDuplicates([4,3,2,7,8,2,3,1])); // [2,3]

Set Mismatch

You have an array representing the set [1, 2, ..., n] that has been corrupted by one error: one number appears twice and another is missing. Return the number that occurs twice and the number that is missing.

Sample Input: nums = [1,2,2,4]

Sample Output: [2,3] (duplicate, missing)

// Set mismatch via cyclic placement
function findErrorNums(nums: number[]): number[] {
  let i = 0;
  while (i < nums.length) {
    const correctIdx = nums[i] - 1;
    if (nums[i] !== nums[correctIdx]) {
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    } else {
      i++;
    }
  }
  let dup = -1, missing = -1;
  for (let idx = 0; idx < nums.length; idx++) {
    if (nums[idx] !== idx + 1) { dup = nums[idx]; missing = idx + 1; }
  }
  return [dup, missing];
}
// Example:
console.log(findErrorNums([1,2,2,4])); // [2,3]

First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Sample Input: nums = [3,4,-1,1]

Sample Output: 2

// First missing positive using cyclic placement in range 1..n
function firstMissingPositive(nums: number[]): number {
  let i = 0;
  while (i < nums.length) {
    const v = nums[i];
    const correctIdx = v - 1;
    if (v > 0 && v <= nums.length && nums[i] !== nums[correctIdx]) {
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    } else {
      i++;
    }
  }
  for (let idx = 0; idx < nums.length; idx++) {
    if (nums[idx] !== idx + 1) return idx + 1;
  }
  return nums.length + 1;
}
// Example:
console.log(firstMissingPositive([3,4,-1,1])); // 2

Find Error Numbers

Another variant of set mismatch: return [duplicate, missing] from array nums containing numbers 1..n with one duplicate and one missing.

Sample Input: nums = [2,2]

Sample Output: [2,1]

// Variant helper using marking (alternative approach)
function findErrorNumbersAlt(nums: number[]): number[] {
  let dup = -1, missing = -1;
  for (const v of nums) {
    const idx = Math.abs(v) - 1;
    if (nums[idx] < 0) dup = Math.abs(v);
    else nums[idx] = -nums[idx];
  }
  for (let i = 0; i < nums.length; i++) if (nums[i] > 0) missing = i + 1;
  return [dup, missing];
}
// Example:
console.log(findErrorNumbersAlt([2,2])); // [2,1]

Kth Missing Positive Number

Given a sorted array arr of positive integers and an integer k, return the k-th missing positive number.

Sample Input: arr = [2,3,4,7,11], k = 5

Sample Output: 9

// Kth missing positive number using arithmetic scan
function findKthPositive(arr: number[], k: number): number {
  let missing = 0, cur = 1, i = 0;
  while (missing < k) {
    if (i < arr.length && arr[i] === cur) i++;
    else missing++;
    if (missing === k) return cur;
    cur++;
  }
  return cur;
}
// Example:
console.log(findKthPositive([2,3,4,7,11], 5)); // 9

Smallest Missing Positive

Same as first missing positive: find the smallest missing positive integer in an unsorted array.

Sample Input: nums = [1,2,0]

Sample Output: 3

// Alias of firstMissingPositive
function smallestMissingPositive(nums: number[]): number {
  return firstMissingPositive(nums);
}
// Example:
console.log(smallestMissingPositive([1,2,0])); // 3

Binary Search

Classic Binary Search
Search Insert Position
Search in Rotated Sorted Array
Find Minimum in Rotated Sorted Array
Find Peak Element
Find First and Last Position of Element
Median of Two Sorted Arrays
Capacity to Ship Packages Within D Days
Koko Eating Bananas
Split Array Largest Sum

Binary Search — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Binary Search example.

Classic Binary Search

Implement binary search to find target in sorted array.

Sample Input: nums = [-1,0,3,5,9,12], target = 9

Sample Output: 4

// Classic binary search
function binarySearch(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
// Example:
console.log(binarySearch([-1,0,3,5,9,12], 9)); // 4

Search Insert Position

Given sorted array and target, return index if found. If not, return index where it would be inserted.

Sample Input: nums = [1,3,5,6], target = 5

Sample Output: 2

// Search insert position
function searchInsert(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return left;
}
// Example:
console.log(searchInsert([1,3,5,6], 5)); // 2

Search in Rotated Sorted Array

Search for target in rotated sorted array.

Sample Input: nums = [4,5,6,7,0,1,2], target = 0

Sample Output: 4

// Search in rotated sorted array
function searchRotated(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}
// Example:
console.log(searchRotated([4,5,6,7,0,1,2], 0)); // 4

Find Minimum in Rotated Sorted Array

Find the minimum element in rotated sorted array.

Sample Input: nums = [3,4,5,1,2]

Sample Output: 1

// Find minimum in rotated sorted array
function findMin(nums: number[]): number {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) left = mid + 1;
    else right = mid;
  }
  return nums[left];
}
// Example:
console.log(findMin([3,4,5,1,2])); // 1

Find Peak Element

Find a peak element index where nums[i] > nums[i-1] and nums[i] > nums[i+1].

Sample Input: nums = [1,2,1,3,5,6,4]

Sample Output: 1 or 5

// Find peak element
function findPeakElement(nums: number[]): number {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < nums[mid+1]) left = mid + 1;
    else right = mid;
  }
  return left;
}
// Example:
console.log(findPeakElement([1,2,1,3,5,6,4])); // 1 or 5

Find First and Last Position of Element

Return first and last position of element in sorted array.

Sample Input: nums = [5,7,7,8,8,10], target = 8

Sample Output: [3,4]

// Find first and last position of target
function searchRange(nums: number[], target: number): number[] {
  function bound(isFirst: boolean): number {
    let left = 0, right = nums.length - 1, ans = -1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (nums[mid] === target) {
        ans = mid;
        if (isFirst) right = mid - 1; else left = mid + 1;
      } else if (nums[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
    return ans;
  }
  return [bound(true), bound(false)];
}
// Example:
console.log(searchRange([5,7,7,8,8,10], 8)); // [3,4]

Median of Two Sorted Arrays

Find median of two sorted arrays.

Sample Input: nums1 = [1,3], nums2 = [2]

Sample Output: 2.0

// Median of two sorted arrays (binary search partition method)
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let left = 0, right = m;
  while (left <= right) {
    const i = Math.floor((left + right)/2);
    const j = Math.floor((m+n+1)/2) - i;
    const maxLeftA = (i===0? -Infinity: nums1[i-1]);
    const minRightA = (i===m? Infinity: nums1[i]);
    const maxLeftB = (j===0? -Infinity: nums2[j-1]);
    const minRightB = (j===n? Infinity: nums2[j]);
    if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
      if ((m+n)%2===0) return (Math.max(maxLeftA, maxLeftB)+Math.min(minRightA,minRightB))/2;
      else return Math.max(maxLeftA,maxLeftB);
    } else if (maxLeftA > minRightB) right = i-1;
    else left = i+1;
  }
  return 0;
}
// Example:
console.log(findMedianSortedArrays([1,3],[2])); // 2

Capacity to Ship Packages Within D Days

Given weights and days, return minimum ship capacity to deliver packages within D days.

Sample Input: weights = [1,2,3,1,1], D = 4

Sample Output: 3

// Capacity to ship packages within D days
function shipWithinDays(weights: number[], D: number): number {
  let left = Math.max(...weights), right = weights.reduce((a,b)=>a+b,0);
  while (left < right) {
    const mid = Math.floor((left+right)/2);
    let days = 1, cur = 0;
    for (const w of weights) {
      if (cur+w > mid) { days++; cur=0; }
      cur += w;
    }
    if (days <= D) right = mid; else left = mid+1;
  }
  return left;
}
// Example:
console.log(shipWithinDays([1,2,3,1,1], 4)); // 3

Koko Eating Bananas

Koko loves bananas. Given piles and hours h, return minimum integer speed to eat all bananas within h.

Sample Input: piles = [3,6,7,11], h = 8

Sample Output: 4

// Koko eating bananas
function minEatingSpeed(piles: number[], h: number): number {
  let left = 1, right = Math.max(...piles);
  while (left < right) {
    const mid = Math.floor((left+right)/2);
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p/mid);
    if (hours <= h) right = mid;
    else left = mid+1;
  }
  return left;
}
// Example:
console.log(minEatingSpeed([3,6,7,11], 8)); // 4

Split Array Largest Sum

Split array into m subarrays to minimize largest sum among them.

Sample Input: nums = [7,2,5,10,8], m = 2

Sample Output: 18

// Split array largest sum using binary search on answer
function splitArray(nums: number[], m: number): number {
  let left = Math.max(...nums), right = nums.reduce((a,b)=>a+b,0);
  while (left < right) {
    const mid = Math.floor((left+right)/2);
    let cnt=1, sum=0;
    for (const n of nums) {
      if (sum+n > mid) { cnt++; sum=0; }
      sum+=n;
    }
    if (cnt <= m) right=mid; else left=mid+1;
  }
  return left;
}
// Example:
console.log(splitArray([7,2,5,10,8], 2)); // 18

DFS BFS

Number of Islands
Clone Graph
Word Search
Pacific Atlantic Water Flow
Course Schedule (BFS/DFS)
Rotting Oranges
Surrounded Regions
Minimum Depth of Binary Tree
Word Ladder
Shortest Path in Binary Matrix

DFS / BFS — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each DFS/BFS example.

Number of Islands

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Sample Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

Sample Output: 3

// Number of Islands using DFS
function numIslands(grid: string[][]): number {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  let count = 0;
  const dfs = (i: number, j: number) => {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') return;
    grid[i][j] = '0';
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  };
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (grid[i][j] === '1') { count++; dfs(i,j); }
  return count;
}
// Example:
console.log(numIslands([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']])); // 3

Clone Graph

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

Sample Input: adjacency list representation

Sample Output: cloned graph root node

// Clone graph using DFS + map
class Node {
  val: number;
  neighbors: Node[];
  constructor(val = 0, neighbors: Node[] = []) { this.val = val; this.neighbors = neighbors; }
}

function cloneGraph(node: Node | null): Node | null {
  if (!node) return null;
  const map = new Map<Node, Node>();
  const dfs = (n: Node): Node => {
    if (map.has(n)) return map.get(n)!;
    const copy = new Node(n.val);
    map.set(n, copy);
    for (const nei of n.neighbors) copy.neighbors.push(dfs(nei));
    return copy;
  };
  return dfs(node);
}

Word Search

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells.

Sample Input: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'ABCCED'

Sample Output: true

// Word Search using DFS backtracking
function exist(board: string[][], word: string): boolean {
  const m = board.length, n = board[0].length;
  const dfs = (i:number,j:number,k:number): boolean => {
    if (k === word.length) return true;
    if (i<0||j<0||i>=m||j>=n||board[i][j] !== word[k]) return false;
    const tmp = board[i][j];
    board[i][j] = '#';
    const found = dfs(i+1,j,k+1) || dfs(i-1,j,k+1) || dfs(i,j+1,k+1) || dfs(i,j-1,k+1);
    board[i][j] = tmp;
    return found;
  };
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (dfs(i,j,0)) return true;
  return false;
}
// Example:
console.log(exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'ABCCED')); // true

Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each cell, return coordinates where water can flow to both the Pacific and Atlantic ocean.

Sample Input: height matrix

Sample Output: list of coordinates

// Pacific Atlantic Water Flow using BFS from oceans
function pacificAtlantic(heights: number[][]): number[][] {
  const m = heights.length, n = heights[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  const bfs = (starts: number[][]) => {
    const visited = Array.from({length:m}, ()=>Array(n).fill(false));
    const q: number[][] = [...starts];
    for (const [i,j] of starts) visited[i][j]=true;
    while (q.length) {
      const [i,j] = q.shift()!;
      for (const [di,dj] of dirs) {
        const ni=i+di, nj=j+dj;
        if (ni>=0&&nj>=0&&ni<m&&nj<n && !visited[ni][nj] && heights[ni][nj] >= heights[i][j]) {
          visited[ni][nj]=true; q.push([ni,nj]);
        }
      }
    }
    return visited;
  };
  const pac = [], atl = [];
  for (let i=0;i<m;i++){ pac.push([i,0]); atl.push([i,n-1]); }
  for (let j=0;j<n;j++){ pac.push([0,j]); atl.push([m-1,j]); }
  const pacV = bfs(pac), atlV = bfs(atl);
  const res: number[][] = [];
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (pacV[i][j] && atlV[i][j]) res.push([i,j]);
  return res;
}

Course Schedule (BFS/DFS)

Given number of courses and prerequisites pairs, determine if you can finish all courses (i.e., no cycle).

Sample Input: numCourses = 2, prerequisites = [[1,0]]

Sample Output: true

// Course Schedule using Kahn's algorithm (BFS)
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const indeg = Array(numCourses).fill(0);
  const adj: number[][] = Array.from({length:numCourses}, ()=>[]);
  for (const [a,b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q: number[] = [];
  for (let i=0;i<numCourses;i++) if (indeg[i]===0) q.push(i);
  let cnt=0;
  while (q.length) {
    const u = q.shift()!; cnt++;
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return cnt === numCourses;
}

Rotting Oranges

Given grid of oranges, where 0 is empty, 1 is fresh, 2 is rotten. Each minute, rotten oranges rot adjacent fresh ones. Return minimum minutes until all fresh are rotten or -1.

Sample Input: [[2,1,1],[1,1,0],[0,1,1]]

Sample Output: 4

// Rotting Oranges using BFS multi-source
function orangesRotting(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  const q: number[][] = []; let fresh = 0;
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) {
    if (grid[i][j]===2) q.push([i,j]);
    if (grid[i][j]===1) fresh++;
  }
  let mins = 0; const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length && fresh>0) {
    const sz = q.length;
    for (let k=0;k<sz;k++) {
      const [i,j] = q.shift()!;
      for (const [di,dj] of dirs) {
        const ni=i+di, nj=j+dj;
        if (ni>=0&&nj>=0&&ni<m&&nj<n && grid[ni][nj]===1) {
          grid[ni][nj]=2; fresh--; q.push([ni,nj]);
        }
      }
    }
    mins++;
  }
  return fresh===0? mins : -1;
}

Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. Replace surrounded 'O's with 'X'.

Sample Input: [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]

Sample Output: [['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]

// Surrounded Regions: mark border-connected O's then flip
function solve(board: string[][]): void {
  if (!board.length) return;
  const m = board.length, n = board[0].length;
  const dfs = (i:number,j:number) => {
    if (i<0||j<0||i>=m||j>=n||board[i][j] !== 'O') return;
    board[i][j] = '#';
    dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1);
  };
  for (let i=0;i<m;i++) { dfs(i,0); dfs(i,n-1); }
  for (let j=0;j<n;j++) { dfs(0,j); dfs(m-1,j); }
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) {
    if (board[i][j] === 'O') board[i][j] = 'X';
    else if (board[i][j] === '#') board[i][j] = 'O';
  }
}

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth (shortest distance from root to nearest leaf).

Sample Input: root = [3,9,20,null,null,15,7]

Sample Output: 2

// Minimum depth using BFS
class TreeNode { val:number; left:TreeNode|null; right:TreeNode|null; constructor(val=0,left=null,right=null){this.val=val;this.left=left;this.right=right;} }
function minDepth(root: TreeNode | null): number {
  if (!root) return 0;
  const q: [TreeNode, number][] = [[root,1]];
  while (q.length) {
    const [node,d] = q.shift()!;
    if (!node.left && !node.right) return d;
    if (node.left) q.push([node.left, d+1]);
    if (node.right) q.push([node.right, d+1]);
  }
  return 0;
}

Word Ladder

Given beginWord, endWord and a wordList, return the length of shortest transformation sequence from beginWord to endWord, changing only one letter at a time and each transformed word must exist in wordList.

Sample Input: beginWord = 'hit', endWord = 'cog', wordList = ['hot','dot','dog','lot','log','cog']

Sample Output: 5

// Word Ladder BFS shortest path
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const q: [string, number][] = [[beginWord,1]];
  set.delete(beginWord);
  while (q.length) {
    const [word,steps] = q.shift()!;
    if (word === endWord) return steps;
    for (let i=0;i<word.length;i++) {
      for (let c=97;c<=122;c++) {
        const nxt = word.slice(0,i) + String.fromCharCode(c) + word.slice(i+1);
        if (set.has(nxt)) { set.delete(nxt); q.push([nxt, steps+1]); }
      }
    }
  }
  return 0;
}

Shortest Path in Binary Matrix

Given an n x n binary matrix, return the length of the shortest clear path from top-left to bottom-right, where 0 is clear and 1 is blocked. You can move in 8 directions.

Sample Input: [[0,1],[1,0]]

Sample Output: 2

// Shortest path in binary matrix using BFS
function shortestPathBinaryMatrix(grid: number[][]): number {
  const n = grid.length;
  if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]];
  const q: [number,number,number][] = [[0,0,1]];
  const vis = Array.from({length:n}, ()=>Array(n).fill(false));
  vis[0][0] = true;
  while (q.length) {
    const [i,j,d] = q.shift()!;
    if (i===n-1 && j===n-1) return d;
    for (const [di,dj] of dirs) {
      const ni=i+di, nj=j+dj;
      if (ni>=0&&nj>=0&&ni<n&&nj<n && !vis[ni][nj] && grid[ni][nj]===0) {
        vis[ni][nj]=true; q.push([ni,nj,d+1]);
      }
    }
  }
  return -1;
}

Backtracking

Subsets
Subsets II
Permutations
Permutations II
Combination Sum
Combination Sum II
Word Search
N-Queens
Palindrome Partitioning
Generate Parentheses

Backtracking — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Backtracking example.

Subsets

Given a set of distinct integers, return all possible subsets (the power set).

Sample Input: nums = [1,2,3]

Sample Output: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

// Generate all subsets via backtracking
function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const comb: number[] = [];
  function dfs(idx: number) {
    res.push([...comb]);
    for (let i = idx; i < nums.length; i++) {
      comb.push(nums[i]);
      dfs(i+1);
      comb.pop();
    }
  }
  dfs(0);
  return res;
}
// Example:
console.log(subsets([1,2,3]));

Subsets II

Return all possible subsets from list that may contain duplicates. Each subset must be unique.

Sample Input: nums = [1,2,2]

Sample Output: [[],[1],[2],[1,2],[2,2],[1,2,2]]

// Subsets II handling duplicates
function subsetsWithDup(nums: number[]): number[][] {
  nums.sort((a,b)=>a-b);
  const res: number[][] = [];
  const comb: number[] = [];
  function dfs(idx:number) {
    res.push([...comb]);
    for (let i = idx; i < nums.length; i++) {
      if (i > idx && nums[i] === nums[i-1]) continue;
      comb.push(nums[i]);
      dfs(i+1);
      comb.pop();
    }
  }
  dfs(0);
  return res;
}
// Example:
console.log(subsetsWithDup([1,2,2]));

Permutations

Given a collection of distinct integers, return all possible permutations.

Sample Input: nums = [1,2,3]

Sample Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

// Permutations via backtracking
function permute(nums: number[]): number[][] {
  const res: number[][] = [];
  const used = Array(nums.length).fill(false);
  const cur: number[] = [];
  function dfs() {
    if (cur.length === nums.length) { res.push([...cur]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      cur.push(nums[i]);
      dfs();
      cur.pop();
      used[i] = false;
    }
  }
  dfs();
  return res;
}
// Example:
console.log(permute([1,2,3]));

Permutations II

Return all unique permutations for list that may contain duplicates.

Sample Input: nums = [1,1,2]

Sample Output: [[1,1,2],[1,2,1],[2,1,1]]

// Permutations II with duplicate handling
function permuteUnique(nums: number[]): number[][] {
  nums.sort((a,b)=>a-b);
  const res: number[][] = [];
  const used = Array(nums.length).fill(false);
  const cur: number[] = [];
  function dfs() {
    if (cur.length === nums.length) { res.push([...cur]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i] || (i>0 && nums[i] === nums[i-1] && !used[i-1])) continue;
      used[i] = true;
      cur.push(nums[i]);
      dfs();
      cur.pop();
      used[i] = false;
    }
  }
  dfs();
  return res;
}
// Example:
console.log(permuteUnique([1,1,2]));

Combination Sum

Given candidates (no duplicates) and target, return unique combinations where numbers sum to target. Numbers may be used unlimited times.

Sample Input: candidates = [2,3,6,7], target = 7

Sample Output: [[7],[2,2,3]]

// Combination Sum (unlimited reuse)
function combinationSum(candidates: number[], target: number): number[][] {
  candidates.sort((a,b)=>a-b);
  const res: number[][] = [];
  const comb: number[] = [];
  function dfs(start:number, sum:number) {
    if (sum === target) { res.push([...comb]); return; }
    if (sum > target) return;
    for (let i = start; i < candidates.length; i++) {
      comb.push(candidates[i]);
      dfs(i, sum + candidates[i]);
      comb.pop();
    }
  }
  dfs(0,0);
  return res;
}
// Example:
console.log(combinationSum([2,3,6,7],7));

Combination Sum II

Given candidates (may contain duplicates) and target, return unique combinations where numbers sum to target. Each number may be used once.

Sample Input: candidates = [10,1,2,7,6,1,5], target = 8

Sample Output: [[1,7],[1,2,5],[2,6],[1,1,6]]

// Combination Sum II (each number used once, handle duplicates)
function combinationSum2(candidates: number[], target: number): number[][] {
  candidates.sort((a,b)=>a-b);
  const res: number[][] = [];
  const comb: number[] = [];
  function dfs(start:number, sum:number) {
    if (sum === target) { res.push([...comb]); return; }
    if (sum > target) return;
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] === candidates[i-1]) continue;
      comb.push(candidates[i]);
      dfs(i+1, sum + candidates[i]);
      comb.pop();
    }
  }
  dfs(0,0);
  return res;
}
// Example:
console.log(combinationSum2([10,1,2,7,6,1,5], 8));

Word Search

Given a 2D board and a word, find if the word exists in the grid. (Backtracking — covered previously under DFS/BFS but included here as well.)

Sample Input: board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = 'SEE'

Sample Output: true

// Word Search via backtracking (same as DFS implementation)
function exist(board: string[][], word: string): boolean {
  const m = board.length, n = board[0].length;
  const dfs = (i:number,j:number,k:number): boolean => {
    if (k === word.length) return true;
    if (i<0||j<0||i>=m||j>=n||board[i][j] !== word[k]) return false;
    const tmp = board[i][j];
    board[i][j] = '#';
    const found = dfs(i+1,j,k+1) || dfs(i-1,j,k+1) || dfs(i,j+1,k+1) || dfs(i,j-1,k+1);
    board[i][j] = tmp;
    return found;
  };
  for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (dfs(i,j,0)) return true;
  return false;
}
// Example:
console.log(exist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], 'SEE')); // true

N-Queens

Place N queens on an N×N chessboard so that no two queens attack each other. Return all distinct solutions.

Sample Input: n = 4

Sample Output: [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]

// N-Queens backtracking
function solveNQueens(n: number): string[][] {
  const res: string[][] = [];
  const cols = new Set<number>(), diag1 = new Set<number>(), diag2 = new Set<number>();
  const board: string[] = Array.from({length:n}, ()=>'.'.repeat(n));
  function dfs(row:number) {
    if (row === n) { res.push([...board]); return; }
    for (let col=0; col<n; col++) {
      if (cols.has(col) || diag1.has(row-col) || diag2.has(row+col)) continue;
      cols.add(col); diag1.add(row-col); diag2.add(row+col);
      board[row] = board[row].substr(0,col) + 'Q' + board[row].substr(col+1);
      dfs(row+1);
      board[row] = board[row].substr(0,col) + '.' + board[row].substr(col+1);
      cols.delete(col); diag1.delete(row-col); diag2.delete(row+col);
    }
  }
  dfs(0);
  return res;
}
// Example:
console.log(solveNQueens(4));

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Sample Input: s = "aab"

Sample Output: [["a","a","b"],["aa","b"]]

// Palindrome partitioning via backtracking
function partition(s: string): string[][] {
  const res: string[][] = [];
  const cur: string[] = [];
  function isPal(l:number, r:number) {
    while (l < r) { if (s[l++] !== s[r--]) return false; } return true;
  }
  function dfs(start:number) {
    if (start === s.length) { res.push([...cur]); return; }
    for (let end = start; end < s.length; end++) {
      if (!isPal(start,end)) continue;
      cur.push(s.slice(start,end+1));
      dfs(end+1);
      cur.pop();
    }
  }
  dfs(0);
  return res;
}
// Example:
console.log(partition("aab"));

Generate Parentheses

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Sample Input: n = 3

Sample Output: [("((()))","(()())","(())()","()(())","()()()")]

// Generate parentheses using backtracking
function generateParenthesis(n: number): string[] {
  const res: string[] = [];
  function dfs(open:number, close:number, cur:string) {
    if (cur.length === 2*n) { res.push(cur); return; }
    if (open < n) dfs(open+1, close, cur + '(');
    if (close < open) dfs(open, close+1, cur + ')');
  }
  dfs(0,0,'');
  return res;
}
// Example:
console.log(generateParenthesis(3));

Dynamic Programming (DP)

Climbing Stairs
House Robber
House Robber II
Coin Change
Coin Change II
Knapsack Problem
Longest Increasing Subsequence
Longest Common Subsequence
Edit Distance
Unique Paths

Dynamic Programming (DP) — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each DP example.

Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Sample Input: n = 3

Sample Output: 3

// Climbing Stairs (DP - fibonacci)
function climbStairs(n: number): number {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    const c = a + b;
    a = b; b = c;
  }
  return b;
}
// Example:
console.log(climbStairs(3)); // 3

House Robber

House Robber: Given non-negative integers representing amount of money of each house, determine max amount you can rob without alert (no two adjacent houses).

Sample Input: nums = [1,2,3,1]

Sample Output: 4

// House Robber (linear DP)
function rob(nums: number[]): number {
  let prev = 0, curr = 0;
  for (const n of nums) {
    const tmp = Math.max(curr, prev + n);
    prev = curr; curr = tmp;
  }
  return curr;
}
// Example:
console.log(rob([1,2,3,1])); // 4

House Robber II

House Robber II: Houses are in a circle. Max amount you can rob without triggering alarm (no two adjacent houses).

Sample Input: nums = [2,3,2]

Sample Output: 3

// House Robber II (circular houses): run linear twice excluding first or last
function robLinear(nums: number[], l:number, r:number): number {
  let prev = 0, curr = 0;
  for (let i = l; i <= r; i++) {
    const temp = Math.max(curr, prev + nums[i]);
    prev = curr; curr = temp;
  }
  return curr;
}
function rob(nums: number[]): number {
  if (!nums.length) return 0;
  if (nums.length === 1) return nums[0];
  return Math.max(robLinear(nums, 0, nums.length-2), robLinear(nums, 1, nums.length-1));
}
// Example:
console.log(rob([2,3,2])); // 3

Coin Change

Given coins of different denominations and a total amount, compute the fewest number of coins needed to make up that amount. If that amount cannot be made up, return -1.

Sample Input: coins = [1,2,5], amount = 11

Sample Output: 3 (5+5+1)

// Coin Change (min coins) - unbounded knapsack DP
function coinChange(coins: number[], amount: number): number {
  const dp = Array(amount+1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a - c >= 0) dp[a] = Math.min(dp[a], dp[a-c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
// Example:
console.log(coinChange([1,2,5], 11)); // 3

Coin Change II

Given coins and amount, compute the number of combinations that make up that amount. Order doesn't matter.

Sample Input: amount = 5, coins = [1,2,5]

Sample Output: 4

// Coin Change II - count combinations
function change(amount: number, coins: number[]): number {
  const dp = Array(amount+1).fill(0);
  dp[0] = 1;
  for (const c of coins) {
    for (let a = c; a <= amount; a++) dp[a] += dp[a-c];
  }
  return dp[amount];
}
// Example:
console.log(change(5, [1,2,5])); // 4

Knapsack Problem

0/1 Knapsack: Given weights and values, and capacity W, maximize total value without exceeding capacity.

Sample Input: weights=[1,3,4], values=[15,20,30], W=4

Sample Output: 35 (pick items 1 and 3)

// 0/1 Knapsack DP (classic)
function knapsack(values: number[], weights: number[], W: number): number {
  const n = values.length;
  const dp = Array(W+1).fill(0);
  for (let i = 0; i < n; i++) {
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}
// Example:
console.log(knapsack([15,20,30],[1,3,4],4)); // 35

Longest Increasing Subsequence

Given an integer array, return the length of the longest strictly increasing subsequence.

Sample Input: nums = [10,9,2,5,3,7,101,18]

Sample Output: 4 (2,3,7,101)

// Longest Increasing Subsequence (n log n method)
function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    let l = 0, r = tails.length;
    while (l < r) {
      const m = Math.floor((l + r) / 2);
      if (tails[m] < x) l = m + 1; else r = m;
    }
    tails[l] = x;
    if (l === tails.length) tails.push(x);
  }
  return tails.length;
}
// Example:
console.log(lengthOfLIS([10,9,2,5,3,7,101,18])); // 4

Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

Sample Input: text1 = "abcde", text2 = "ace"

Sample Output: 3

// Longest Common Subsequence (2D DP)
function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = Array.from({length:m+1}, ()=>Array(n+1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i-1] === text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}
// Example:
console.log(longestCommonSubsequence("abcde", "ace")); // 3

Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2 (insert, delete, replace).

Sample Input: word1 = "horse", word2 = "ros"

Sample Output: 3

// Edit Distance (Levenshtein) - 2D DP
function minDistance(word1: string, word2: string): number {
  const m = word1.length, n = word2.length;
  const dp = Array.from({length:m+1}, ()=>Array(n+1).fill(0));
  for (let i=0;i<=m;i++) dp[i][0]=i;
  for (let j=0;j<=n;j++) dp[0][j]=j;
  for (let i=1;i<=m;i++) {
    for (let j=1;j<=n;j++) {
      if (word1[i-1] === word2[j-1]) dp[i][j]=dp[i-1][j-1];
      else dp[i][j] = 1 + Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}
// Example:
console.log(minDistance("horse","ros")); // 3

Unique Paths

A robot is at top-left corner of an m x n grid. It can only move either down or right. How many possible unique paths to reach bottom-right?

Sample Input: m = 3, n = 7

Sample Output: 28

// Unique Paths using combinatorics or DP
function uniquePaths(m: number, n: number): number {
  const dp = Array(n).fill(1);
  for (let i=1;i<m;i++) {
    for (let j=1;j<n;j++) dp[j] += dp[j-1];
  }
  return dp[n-1];
}
// Example:
console.log(uniquePaths(3,7)); // 28

Greedy

Activity Selection Problem
Fractional Knapsack
Jump Game
Jump Game II
Gas Station
Candy Distribution
Non-overlapping Intervals
Assign Cookies
Minimum Number of Platforms
Huffman Encoding

Greedy — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Greedy example.

Activity Selection Problem

Given start and finish times of activities, select the maximum number of activities that don't overlap.

Sample Input: [(1,3),(2,4),(3,5)]

Sample Output: [(1,3),(3,5)] (2 activities)

// Activity selection (greedy by finish time)
function selectActivities(intervals: number[][]): number[][] {
  intervals.sort((a,b)=>a[1]-b[1]);
  const res: number[][] = [];
  let lastEnd = -Infinity;
  for (const [s,e] of intervals) {
    if (s >= lastEnd) { res.push([s,e]); lastEnd = e; }
  }
  return res;
}
// Example:
console.log(selectActivities([[1,3],[2,4],[3,5]])); // [[1,3],[3,5]]

Fractional Knapsack

Given items with value and weight and a capacity, maximize value by taking fractions of items.

Sample Input: items = [[60,10],[100,20],[120,30]], capacity = 50

Sample Output: 240.0

// Fractional Knapsack (greedy by value/weight ratio)
function fractionalKnapsack(items: number[][], capacity: number): number {
  items.sort((a,b)=> (b[0]/b[1]) - (a[0]/a[1]));
  let total = 0, cap = capacity;
  for (const [value, weight] of items) {
    if (cap === 0) break;
    const take = Math.min(weight, cap);
    total += (value/weight) * take;
    cap -= take;
  }
  return total;
}
// Example:
console.log(fractionalKnapsack([[60,10],[100,20],[120,30]], 50)); // 240

Jump Game

Given an array of non-negative integers where each element represents max jump length at that position, determine if you can reach the last index.

Sample Input: nums = [2,3,1,1,4]

Sample Output: true

// Jump Game (greedy)
function canJump(nums: number[]): boolean {
  let far = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > far) return false;
    far = Math.max(far, i + nums[i]);
  }
  return true;
}
// Example:
console.log(canJump([2,3,1,1,4])); // true

Jump Game II

Given an array of non-negative integers where each element represents max jump length, return minimum number of jumps to reach the last index.

Sample Input: nums = [2,3,1,1,4]

Sample Output: 2

// Jump Game II (greedy BFS-like)
function jump(nums: number[]): number {
  let jumps = 0, currentEnd = 0, far = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    far = Math.max(far, i + nums[i]);
    if (i === currentEnd) {
      jumps++;
      currentEnd = far;
    }
  }
  return jumps;
}
// Example:
console.log(jump([2,3,1,1,4])); // 2

Gas Station

Given gas at stations and cost to travel to next station, return starting gas station index if you can complete circuit, else -1.

Sample Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Sample Output: 3

// Gas Station (greedy)
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i];
    tank += gas[i] - cost[i];
    if (tank < 0) { start = i + 1; tank = 0; }
  }
  return total >= 0 ? start : -1;
}
// Example:
console.log(canCompleteCircuit([1,2,3,4,5],[3,4,5,1,2])); // 3

Candy Distribution

Distribute candies to children standing in a line based on ratings. Each child must have at least one candy, and children with higher rating than neighbors get more candies. Return minimum candies.

Sample Input: ratings = [1,0,2]

Sample Output: 5 (candies = [2,1,2])

// Candy (greedy two-pass)
function candy(ratings: number[]): number {
  const n = ratings.length;
  const candies = Array(n).fill(1);
  for (let i = 1; i < n; i++) if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
  for (let i = n-2; i >= 0; i--) if (ratings[i] > ratings[i+1]) candies[i] = Math.max(candies[i], candies[i+1] + 1);
  return candies.reduce((a,b)=>a+b,0);
}
// Example:
console.log(candy([1,0,2])); // 5

Non-overlapping Intervals

Given intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping.

Sample Input: [[1,2],[2,3],[3,4],[1,3]]

Sample Output: 1

// Erase overlap intervals (greedy by end time)
function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals.sort((a,b)=>a[1]-b[1]);
  let count = 0, prevEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < prevEnd) count++;
    else prevEnd = intervals[i][1];
  }
  return count;
}
// Example:
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])); // 1

Assign Cookies

Given children with greed factors and cookies with sizes, assign cookies to maximize number of content children (cookie size >= greed).

Sample Input: g = [1,2,3], s = [1,1]

Sample Output: 1

// Assign cookies (greedy sort both)
function findContentChildren(g: number[], s: number[]): number {
  g.sort((a,b)=>a-b); s.sort((a,b)=>a-b);
  let i=0,j=0;
  while (i<g.length && j<s.length) {
    if (s[j] >= g[i]) { i++; j++; }
    else j++;
  }
  return i;
}
// Example:
console.log(findContentChildren([1,2,3],[1,1])); // 1

Minimum Number of Platforms

Given arrival and departure times, find minimum number of platforms required so that no train waits.

Sample Input: arr = [900,940,950,1100,1500,1800], dep = [910,1200,1120,1130,1900,2000]

Sample Output: 3

// Minimum platforms (greedy using sorting of times)
function minPlatforms(arr: number[], dep: number[]): number {
  arr.sort((a,b)=>a-b); dep.sort((a,b)=>a-b);
  let i=0,j=0,plat=0,res=0;
  while (i < arr.length && j < dep.length) {
    if (arr[i] <= dep[j]) { plat++; res = Math.max(res, plat); i++; }
    else { plat--; j++; }
  }
  return res;
}
// Example:
console.log(minPlatforms([900,940,950,1100,1500,1800],[910,1200,1120,1130,1900,2000])); // 3

Huffman Encoding

Given characters and frequencies, build a Huffman tree and compute the minimum weighted path length (sum of freq * depth).

Sample Input: chars = ['a','b','c','d'], freq = [5,9,12,13]

Sample Output: ... (implementation returns total cost)

// Huffman encoding (simulate min-heap with array)
function huffmanCost(freq: number[]): number {
  const heap = [...freq];
  let cost = 0;
  while (heap.length > 1) {
    heap.sort((a,b)=>a-b);
    const a = heap.shift()!, b = heap.shift()!;
    cost += a + b;
    heap.push(a+b);
  }
  return cost;
}
// Example:
console.log(huffmanCost([5,9,12,13])); // 39 (example cost)

Heap Priority Queue

Kth Largest Element in an Array
Kth Smallest Element in a Sorted Matrix
Top K Frequent Elements
Find Median from Data Stream
Merge k Sorted Lists
Ugly Number II
Meeting Rooms II
Reorganize String
Task Scheduler
Sliding Window Maximum

Heap / Priority Queue — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Heap/PQ example.

Kth Largest Element in an Array

Find the k-th largest element in an unsorted array.

Sample Input: nums = [3,2,1,5,6,4], k = 2

Sample Output: 5

// Kth largest using min-heap simulation
function findKthLargest(nums: number[], k: number): number {
  const heap: number[] = [];
  for (const n of nums) {
    heap.push(n);
    heap.sort((a,b)=>a-b);
    if (heap.length > k) heap.shift();
  }
  return heap[0];
}
// Example:
console.log(findKthLargest([3,2,1,5,6,4], 2)); // 5

Kth Smallest Element in a Sorted Matrix

Find the k-th smallest element in a sorted matrix (each row and column sorted).

Sample Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

Sample Output: 13

// Kth smallest in sorted matrix using min-heap (flattened approach)
function kthSmallest(matrix: number[][], k: number): number {
  const heap: number[] = [];
  for (const row of matrix) for (const v of row) {
    heap.push(v);
    heap.sort((a,b)=>a-b);
    if (heap.length > k) heap.pop();
  }
  return heap[heap.length-1];
}
// Example:
console.log(kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8)); // 13

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Sample Input: nums = [1,1,1,2,2,3], k = 2

Sample Output: [1,2]

// Top K frequent elements using frequency map + heap simulation
function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number,number>();
  for (const n of nums) freq.set(n, (freq.get(n)||0)+1);
  const arr = Array.from(freq.entries());
  arr.sort((a,b)=>b[1]-a[1]);
  return arr.slice(0,k).map(x=>x[0]);
}
// Example:
console.log(topKFrequent([1,1,1,2,2,3], 2)); // [1,2]

Find Median from Data Stream

Design a data structure that supports adding numbers and finding the median of current numbers.

Sample Input/Operations: add(1), add(2), findMedian() -> 1.5

Sample Output: 1.5

// Median from data stream using two heaps (simulate with arrays)
class MedianFinder {
  small: number[] = []; // max-heap (store as negatives)
  large: number[] = []; // min-heap
  addNum(num: number) {
    this.small.push(-num); this.small.sort((a,b)=>a-b);
    if (this.small.length && this.large.length && -this.small[0] > this.large[0]) {
      const v = -this.small.shift()!;
      this.large.push(v); this.large.sort((a,b)=>a-b);
    }
    if (this.small.length > this.large.length + 1) {
      this.large.push(-this.small.shift()!); this.large.sort((a,b)=>a-b);
    } else if (this.large.length > this.small.length + 1) {
      this.small.push(-this.large.shift()!); this.small.sort((a,b)=>a-b);
    }
  }
  findMedian(): number {
    if (this.small.length === this.large.length) return ((-this.small[0]) + this.large[0]) / 2;
    return this.small.length > this.large.length ? -this.small[0] : this.large[0];
  }
}
// Example:
const mf = new MedianFinder();
mf.addNum(1); mf.addNum(2); console.log(mf.findMedian()); // 1.5

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list.

Sample Input: [[1,4,5],[1,3,4],[2,6]]

Sample Output: [1,1,2,3,4,4,5,6]

// Merge k sorted lists using a heap (simple merge by collecting values)
function mergeKLists(lists: number[][]): number[] {
  const heap: number[] = [];
  for (const lst of lists) for (const v of lst) heap.push(v);
  heap.sort((a,b)=>a-b);
  return heap;
}
// Example:
console.log(mergeKLists([[1,4,5],[1,3,4],[2,6]])); // [1,1,2,3,4,4,5,6]

Ugly Number II

Return the n-th ugly number (numbers whose prime factors are only 2,3,5).

Sample Input: n = 10

Sample Output: 12

// Ugly Number II using min-heap like DP (three pointers is better but heap approach shown)
function nthUglyNumber(n: number): number {
  const heap = [1];
  const seen = new Set<number>([1]);
  const primes = [2,3,5];
  let val = 1;
  for (let i=0;i<n;i++) {
    heap.sort((a,b)=>a-b);
    val = heap.shift()!;
    for (const p of primes) {
      const nx = val * p;
      if (!seen.has(nx)) { seen.add(nx); heap.push(nx); }
    }
  }
  return val;
}
// Example:
console.log(nthUglyNumber(10)); // 12

Meeting Rooms II

Given an array of meeting time intervals, return the minimum number of conference rooms required.

Sample Input: [[0,30],[5,10],[15,20]]

Sample Output: 2

// Meeting Rooms II using min-heap simulation
function minMeetingRooms(intervals: number[][]): number {
  if (!intervals.length) return 0;
  intervals.sort((a,b)=>a[0]-b[0]);
  const heap: number[] = [];
  for (const [s,e] of intervals) {
    heap.sort((a,b)=>a-b);
    if (heap.length && heap[0] <= s) heap.shift();
    heap.push(e);
  }
  return heap.length;
}
// Example:
console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2

Reorganize String

Given a string, rearrange the characters so that any two adjacent characters are not the same. Return any valid rearrangement or empty string if not possible.

Sample Input: s = "aab"

Sample Output: "aba"

// Reorganize string using greedy with frequency sort (heap simulation)
function reorganizeString(s: string): string {
  const freq = new Map<string, number>();
  for (const c of s) freq.set(c, (freq.get(c)||0)+1);
  const arr = Array.from(freq.entries());
  arr.sort((a,b)=>b[1]-a[1]);
  let res = "";
  while (arr.length && arr[0][1] > (s.length+1)/2) return "";
  while (arr.length) {
    arr.sort((a,b)=>b[1]-a[1]);
    const [c1, f1] = arr.shift()!;
    res += c1;
    if (arr.length) {
      const [c2, f2] = arr.shift()!;
      res += c2;
      if (f2-1 > 0) arr.push([c2, f2-1]);
    }
    if (f1-1 > 0) arr.push([c1, f1-1]);
  }
  return res;
}
// Example:
console.log(reorganizeString("aab")); // "aba"

Task Scheduler

Given tasks represented by characters and a cooldown n, find least interval needed to finish all tasks with cooldown.

Sample Input: tasks = ['A','A','A','B','B','B'], n = 2

Sample Output: 8

// Task Scheduler using greedy freq + idle calculation
function leastInterval(tasks: string[], n: number): number {
  const freq = Object.values(tasks.reduce((acc:any,c)=>{acc[c]=(acc[c]||0)+1;return acc;},{}));
  freq.sort((a,b)=>b-a);
  const max = freq[0];
  let idle = (max-1)*n;
  for (let i=1;i<freq.length;i++) idle -= Math.min(freq[i], max-1);
  return Math.max(tasks.length, max + idle + (max-1));
}
// Example:
console.log(leastInterval(['A','A','A','B','B','B'], 2)); // 8

Sliding Window Maximum

Given an array and sliding window size k, return max for each window.

Sample Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

Sample Output: [3,3,5,5,6,7]

// Sliding window maximum using deque (here simple approach)
function maxSlidingWindow(nums: number[], k: number): number[] {
  const res: number[] = [];
  for (let i=0;i<=nums.length-k;i++) {
    res.push(Math.max(...nums.slice(i,i+k)));
  }
  return res;
}
// Example:
console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7],3)); // [3,3,5,5,6,7]

Union Find

Redundant Connection
Number of Connected Components in an Undirected Graph
Friend Circles
Accounts Merge
Graph Valid Tree
Satisfiability of Equality Equations
Kruskal’s MST
Checking Existence of Edge Length Limited Paths
Earliest Moment When Everyone Become Friends
Couples Holding Hands

Union Find (Disjoint Set Union - DSU) — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Union Find example.

Redundant Connection

In a graph of n nodes with n edges where one edge creates a cycle, return the edge that can be removed to make the graph a tree.

Sample Input: [[1,2],[1,3],[2,3]]

Sample Output: [2,3]

// Union-Find implementation for Redundant Connection
class DSU {
  parent: number[];
  rank: number[];
  constructor(n: number) { this.parent = Array.from({length:n+1}, (_,i)=>i); this.rank = Array(n+1).fill(0); }
  find(x: number): number { return this.parent[x] === x ? x : (this.parent[x] = this.find(this.parent[x])); }
  union(x: number, y: number): boolean {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;
    if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
    else if (this.rank[ry] < this.rank[rx]) this.parent[ry] = rx;
    else { this.parent[ry] = rx; this.rank[rx]++; }
    return true;
  }
}
function findRedundantConnection(edges: number[][]): number[] | null {
  const n = edges.length;
  const dsu = new DSU(n);
  for (const [u,v] of edges) {
    if (!dsu.union(u,v)) return [u,v];
  }
  return null;
}
// Example:
console.log(findRedundantConnection([[1,2],[1,3],[2,3]])); // [2,3]

Number of Connected Components in an Undirected Graph

Given n nodes and edges, return the number of connected components in the undirected graph.

Sample Input: n = 5, edges = [[0,1],[1,2],[3,4]]

Sample Output: 2

// Count connected components using DSU
function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({length:n}, (_,i)=>i);
  function find(x:number):number { return parent[x]===x?x:(parent[x]=find(parent[x])); }
  function union(a:number,b:number){ parent[find(a)]=find(b); }
  for (const [u,v] of edges) union(u,v);
  const seen = new Set<number>();
  for (let i=0;i<n;i++) seen.add(find(i));
  return seen.size;
}
// Example:
console.log(countComponents(5, [[0,1],[1,2],[3,4]])); // 2

Friend Circles

Given a friendship adjacency matrix, return number of friend circles (connected components).

Sample Input: [[1,1,0],[1,1,0],[0,0,1]]

Sample Output: 2

// Friend circles using DSU
function findCircleNum(M: number[][]): number {
  const n = M.length;
  const parent = Array.from({length:n}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  function union(a:number,b:number){ parent[find(a)]=find(b); }
  for (let i=0;i<n;i++) for (let j=i+1;j<n;j++) if (M[i][j]===1) union(i,j);
  const s = new Set<number>(); for (let i=0;i<n;i++) s.add(find(i)); return s.size;
}
// Example:
console.log(findCircleNum([[1,1,0],[1,1,0],[0,0,1]])); // 2

Accounts Merge

Given a list of accounts where each account has a name and emails, merge accounts that have common emails and return the merged accounts.

Sample Input: [['John',['a','b'] ], ['John',['b','c']]]

Sample Output: [['John',['a','b','c']]]

// Accounts Merge using DSU on emails
function accountsMerge(accounts: any[]): any[] {
  const emailToId = new Map<string, number>();
  const emailToName = new Map<string, string>();
  let id = 0;
  for (const acc of accounts) {
    const name = acc[0] as string;
    const emails = acc[1] as string[];
    for (const e of emails) {
      if (!emailToId.has(e)) { emailToId.set(e, id++); emailToName.set(e, name); }
    }
  }
  const parent = Array.from({length:id}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  function union(a:number,b:number){ parent[find(a)]=find(b); }
  for (const acc of accounts) {
    const emails = acc[1] as string[];
    for (let i=1;i<emails.length;i++) union(emailToId.get(emails[0])!, emailToId.get(emails[i])!);
  }
  const groups = new Map<number, string[]>();
  for (const [email, eid] of emailToId) {
    const root = find(eid);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root)!.push(email);
  }
  const res: any[] = [];
  for (const [root, emails] of groups) {
    emails.sort();
    res.push([emailToName.get(emails[0])!, emails]);
  }
  return res;
}
// Note: For simple demo input format, adapt parsing. Example not run here.

Graph Valid Tree

Given n nodes and edges, return true if edges make a valid tree (connected and no cycles).

Sample Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Sample Output: true

// Graph valid tree using DSU: ensure no cycle and single component
function validTree(n:number, edges:number[][]): boolean {
  const parent = Array.from({length:n}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  for (const [u,v] of edges) {
    const pu = find(u), pv = find(v);
    if (pu === pv) return false;
    parent[pu] = pv;
  }
  const roots = new Set<number>(); for (let i=0;i<n;i++) roots.add(find(i));
  return roots.size === 1;
}
// Example:
console.log(validTree(5, [[0,1],[0,2],[0,3],[1,4]])); // true

Satisfiability of Equality Equations

Given equations like a==b or a!=b, determine if they can all be satisfied.

Sample Input: ['a==b','b==c','a==c']

Sample Output: true

// Satisfiability of equality equations using DSU for equalities
function equationsPossible(equations: string[]): boolean {
  const parent = Array.from({length:26}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  function union(a:number,b:number){ parent[find(a)]=find(b); }
  for (const eq of equations) {
    if (eq[1] === '=') union(eq.charCodeAt(0)-97, eq.charCodeAt(3)-97);
  }
  for (const eq of equations) {
    if (eq[1] === '!' && find(eq.charCodeAt(0)-97) === find(eq.charCodeAt(3)-97)) return false;
  }
  return true;
}
// Example:
console.log(equationsPossible(['a==b','b==c','a==c'])); // true

Kruskal’s MST

Given edges of weighted undirected graph, compute Minimum Spanning Tree (Kruskal) and return total weight.

Sample Input: edges with weights (u,v,w)

Sample Output: total cost

// Kruskal's MST using DSU (return total weight)
function kruskalMST(n:number, edges:number[][]): number {
  edges.sort((a,b)=>a[2]-b[2]);
  const parent = Array.from({length:n}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  let cost = 0, count = 0;
  for (const [u,v,w] of edges) {
    const pu = find(u), pv = find(v);
    if (pu !== pv) { parent[pu]=pv; cost+=w; count++; if (count === n-1) break; }
  }
  return cost;
}
// Example usage requires edges format [[u,v,w],...]

Checking Existence of Edge Length Limited Paths

Given queries asking whether there exists a path between u and v where all edges have weight < limit, answer true/false for each.

Sample Input: graph edges and queries

Sample Output: boolean answers

// Offline queries: sort edges and queries, union as we go
function distanceLimitedPathsExist(n:number, edgeList:number[][], queries:number[][]): boolean[] {
  const sortedEdges = [...edgeList].sort((a,b)=>a[2]-b[2]);
  const q = queries.map((qt,i)=>[qt[0],qt[1],qt[2],i]);
  q.sort((a,b)=>a[2]-b[2]);
  const parent = Array.from({length:n}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  function union(a:number,b:number){ parent[find(a)]=find(b); }
  const res = Array(q.length).fill(false);
  let ei = 0;
  for (const [u,v,limit,qi] of q) {
    while (ei < sortedEdges.length && sortedEdges[ei][2] < limit) { union(sortedEdges[ei][0], sortedEdges[ei][1]); ei++; }
    res[qi] = find(u) === find(v);
  }
  return res;
}
// Example: adapt inputs for testing

Earliest Moment When Everyone Become Friends

Given logs [timestamp, x, y] and n people, find earliest timestamp when all are connected (friend circles merge). Return -1 if never.

Sample Input: logs = [[20190101,0,1],[20190104,3,4],[20190102,1,2],[20190103,2,3]] , n = 5

Sample Output: 20190103

// Earliest moment everyone becomes friends using DSU
function earliestAcq(logs:number[][], n:number): number {
  logs.sort((a,b)=>a[0]-b[0]);
  const parent = Array.from({length:n}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  let groups = n;
  for (const [t,u,v] of logs) {
    const pu = find(u), pv = find(v);
    if (pu !== pv) { parent[pu]=pv; groups--; if (groups === 1) return t; }
  }
  return -1;
}
// Example:
console.log(earliestAcq([[20190101,0,1],[20190104,3,4],[20190102,1,2],[20190103,2,3]], 5)); // 20190103

Couples Holding Hands

Couples sit in row; minimize swaps so that each couple sits together. Return minimum swaps needed.

Sample Input: row = [0,2,1,3] (couples: (0,1),(2,3))

Sample Output: 1

// Couples Holding Hands using DSU on partners
function minSwapsCouples(row: number[]): number {
  const n = row.length/2;
  const parent = Array.from({length:n}, (_,i)=>i);
  function find(x:number){ return parent[x]===x?x:(parent[x]=find(parent[x])); }
  function union(a:number,b:number){ parent[find(a)]=find(b); }
  for (let i=0;i<row.length;i+=2) {
    const a = Math.floor(row[i]/2), b = Math.floor(row[i+1]/2);
    union(a,b);
  }
  let comps = 0;
  for (let i=0;i<n;i++) if (find(i)===i) comps++;
  return n - comps;
}
// Example:
console.log(minSwapsCouples([0,2,1,3])); // 1

Topological Sort

Course Schedule
Course Schedule II
Alien Dictionary
Minimum Height Trees
Parallel Courses
Find Eventual Safe States
Sort Items by Groups Respecting Dependencies
Task Scheduling
Build Order
Sequence Reconstruction

Topological Sort — Questions & TypeScript Solutions

Below are sample problem statements (with sample input/output) and TypeScript solutions for each Topological Sort example.

Course Schedule

There are numCourses and prerequisites pairs. Return true if you can finish all courses (i.e., no cycles in prerequisites).

Sample Input: numCourses = 2, prerequisites = [[1,0]]

Sample Output: true

// Course Schedule using Kahn's algorithm (topological sort)
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const indeg = Array(numCourses).fill(0);
  const adj: number[][] = Array.from({length:numCourses}, ()=>[]);
  for (const [a,b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q: number[] = [];
  for (let i=0;i<numCourses;i++) if (indeg[i]===0) q.push(i);
  let cnt = 0;
  while (q.length) {
    const u = q.shift()!; cnt++;
    for (const v of adj[u]) { indeg[v]--; if (indeg[v]===0) q.push(v); }
  }
  return cnt === numCourses;
}
// Example:
console.log(canFinish(2, [[1,0]])); // true

Course Schedule II

Return ordering of courses you should take to finish all courses. If impossible, return empty array.

Sample Input: numCourses = 2, prerequisites = [[1,0]]

Sample Output: [0,1]

// Course Schedule II - return topological order
function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const indeg = Array(numCourses).fill(0);
  const adj: number[][] = Array.from({length:numCourses}, ()=>[]);
  for (const [a,b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q: number[] = [];
  for (let i=0;i<numCourses;i++) if (indeg[i]===0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!; order.push(u);
    for (const v of adj[u]) { indeg[v]--; if (indeg[v]===0) q.push(v); }
  }
  return order.length === numCourses ? order : [];
}
// Example:
console.log(findOrder(2, [[1,0]])); // [0,1]

Alien Dictionary

Given a list of words sorted lexicographically in an alien language, derive the order of characters in the language.

Sample Input: ['wrt','wrf','er','ett','rftt']

Sample Output: 'wertf'

// Alien Dictionary using graph + topo sort
function alienOrder(words: string[]): string {
  const adj = new Map<string, Set<string>>();
  const indeg = new Map<string, number>();
  for (const w of words) for (const c of w) { if (!adj.has(c)) adj.set(c, new Set()); if (!indeg.has(c)) indeg.set(c,0); }
  for (let i=0;i<words.length-1;i++) {
    const a = words[i], b = words[i+1];
    const len = Math.min(a.length, b.length);
    let found = false;
    for (let j=0;j<len;j++) {
      if (a[j] !== b[j]) { if (!adj.get(a[j])!.has(b[j])) { adj.get(a[j])!.add(b[j]); indeg.set(b[j], indeg.get(b[j])!+1); } found = true; break; }
    }
    if (!found && a.length > b.length) return "";
  }
  const q: string[] = [];
  for (const [c,d] of indeg) if (d===0) q.push(c);
  const res: string[] = [];
  while (q.length) {
    const c = q.shift()!; res.push(c);
    for (const nei of adj.get(c)!) {
      indeg.set(nei, indeg.get(nei)!-1);
      if (indeg.get(nei)===0) q.push(nei);
    }
  }
  return res.length === indeg.size ? res.join('') : "";
}
// Example:
console.log(alienOrder(['wrt','wrf','er','ett','rftt'])); // "wertf"

Minimum Height Trees

For an undirected tree, find all root labels that produce minimum height trees.

Sample Input: n = 4, edges = [[1,0],[1,2],[1,3]]

Sample Output: [1]

// Minimum Height Trees via trimming leaves (topological idea)
function findMinHeightTrees(n: number, edges: number[][]): number[] {
  if (n <= 1) return [0];
  const adj: number[][] = Array.from({length:n}, ()=>[]);
  const degree = Array(n).fill(0);
  for (const [u,v] of edges) { adj[u].push(v); adj[v].push(u); degree[u]++; degree[v]++; }
  let leaves = [];
  for (let i=0;i<n;i++) if (degree[i]===1) leaves.push(i);
  let remaining = n;
  while (remaining > 2) {
    remaining -= leaves.length;
    const newLeaves: number[] = [];
    for (const leaf of leaves) {
      for (const nei of adj[leaf]) {
        degree[nei]--;
        if (degree[nei]===1) newLeaves.push(nei);
      }
    }
    leaves = newLeaves;
  }
  return leaves;
}
// Example:
console.log(findMinHeightTrees(4, [[1,0],[1,2],[1,3]])); // [1]

Parallel Courses

Given n courses and prerequisites, find minimum number of semesters to finish all courses if you can take any number of courses per semester as long as prerequisites are met.

Sample Input: n = 3, prerequisites = [[1,0],[2,1]]

Sample Output: 3

// Parallel courses: BFS layers on DAG
function minNumberOfSemesters(n: number, prerequisites: number[][]): number {
  const indeg = Array(n).fill(0);
  const adj: number[][] = Array.from({length:n}, ()=>[]);
  for (const [a,b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const q: number[] = [];
  for (let i=0;i<n;i++) if (indeg[i]===0) q.push(i);
  let semesters = 0, taken = 0;
  while (q.length) {
    const size = q.length; semesters++;
    for (let i=0;i<size;i++) {
      const u = q.shift()!; taken++;
      for (const v of adj[u]) { indeg[v]--; if (indeg[v]===0) q.push(v); }
    }
  }
  return taken === n ? semesters : -1;
}
// Example:
console.log(minNumberOfSemesters(3, [[1,0],[2,1]])); // 3

Find Eventual Safe States

Given a directed graph, return nodes that are eventually safe (no cycle reachable).

Sample Input: adjacency list

Sample Output: list of safe nodes

// Find eventual safe states using reverse graph + topo sort
function eventualSafeNodes(graph: number[][]): number[] {
  const n = graph.length;
  const outdeg = Array(n).fill(0);
  const rev: number[][] = Array.from({length:n}, ()=>[]);
  for (let u=0;u<n;u++) {
    outdeg[u] = graph[u].length;
    for (const v of graph[u]) rev[v].push(u);
  }
  const q: number[] = [];
  for (let i=0;i<n;i++) if (outdeg[i]===0) q.push(i);
  const safe = Array(n).fill(false);
  while (q.length) {
    const u = q.shift()!; safe[u]=true;
    for (const p of rev[u]) { outdeg[p]--; if (outdeg[p]===0) q.push(p); }
  }
  const res: number[] = [];
  for (let i=0;i<n;i++) if (safe[i]) res.push(i);
  return res;
}

Sort Items by Groups Respecting Dependencies

Sort items by groups respecting dependencies (complex topo combining groups and items). Return order or empty if impossible.

Sample Input: items, groups and dependencies

Sample Output: ordering

// Placeholder: this is a longer problem; provide a concise approach (topo on groups then items)
// Full implementation omitted for brevity in this cheat-sheet.
function sortItems(n:number, m:number, group:number[], beforeItems:number[][]): number[] {
  // Approach: assign unique groups to ungrouped items, build graphs for groups and items, topo sort groups then items.
  return []; // placeholder
}

Task Scheduling

Given tasks with prerequisites, return a valid order to finish all tasks (topological order) or empty if impossible.

Sample Input: tasks and prerequisites

Sample Output: ordering

// Task scheduling -> topological order (same as Course Schedule II)
function taskOrder(numTasks:number, prerequisites:number[][]): number[] {
  return findOrder(numTasks, prerequisites);
}

Build Order

Given projects and dependencies, return a build order that will allow the projects to be built.

Sample Input: projects and dependencies

Sample Output: ordering

// Build order (topological sort) - reuse findOrder implementation
function buildOrder(projects:number[], deps:number[][]): number[] {
  const idx = new Map<number, number>();
  for (let i=0;i<projects.length;i++) idx.set(projects[i], i);
  // Transform deps to indices and reuse findOrder logic...
  return []; // placeholder concise answer
}

Sequence Reconstruction

Check whether the original sequence can be uniquely reconstructed from the sequences in a list.

Sample Input: org = [1,2,3], seqs = [[1,2],[1,3]]

Sample Output: false

// Sequence Reconstruction using topological uniqueness check
function sequenceReconstruction(org: number[], seqs: number[][]): boolean {
  const n = org.length;
  const indeg = Array(n+1).fill(0);
  const adj: Map<number, Set<number>> = new Map();
  let nodes = new Set<number>();
  for (const s of seqs) for (const x of s) { nodes.add(x); if (!adj.has(x)) adj.set(x, new Set()); }
  for (const s of seqs) {
    for (let i=1;i<s.length;i++) {
      const a = s[i-1], b = s[i];
      if (!adj.get(a)!.has(b)) { adj.get(a)!.add(b); indeg[b]++; }
    }
  }
  const q: number[] = [];
  for (const x of nodes) if (indeg[x]===0) q.push(x);
  const order: number[] = [];
  while (q.length) {
    if (q.length > 1) return false;
    const u = q.shift()!; order.push(u);
    for (const v of (adj.get(u) || [])) { indeg[v]--; if (indeg[v]===0) q.push(v); }
  }
  return order.length === org.length && order.every((v,i)=>v===org[i]);
}
// Example:
console.log(sequenceReconstruction([1,2,3], [[1,2],[1,3]])); // false

Learn Python from JS/TS

Bhuvaneswari Shanker — Thu, 11 Sep 2025 13:32:37 +0000

This post is designed to help developers familiar with TypeScript/JavaScript transition to Python (v3.10).

Variables
Data Types
Functions
Control Flow
Loops
Classes & OOP
Inheritance
Modules / Imports
Exception Handling
Async / Await
Spread & Rest Operators
Object Destructuring / Sequence Unpacking
Interfaces
Hoisting & Scopes
Closures
Coroutines
Futures & Concurrency
Decorators
Special Methods / Dunder Methods
Iterators & Generators

Cheat sheet - Frequently used helper methods

1. Variables

Python doesn’t require let/const/var. Types are optional in python.

TypeScript

let x: number = 5;
const y = "hello";
var z = true;

Python

x: int = 5
y: str = "hello"
z = True

2. Data types

TypeScript	Python
`number`	`int`, `float`
`string`	`str`
`boolean`	`bool`
`any`	`Any` (from `typing`)
`array: number[]`	`list[int]`
`tuple: [string, number]`	`tuple[str, int]`
`object`	`dict`

Typescript Example:

let arr: number[] = [1, 2, 3];
let tup: [string, number] = ["a", 1];
let obj: {name: string, age: number} = {name: "Alice", age: 25};

Python Example:

arr: list[int] = [1, 2, 3]
tup: tuple[str, int] = ("a", 1)
obj: dict[str, int] = {"name": "Alice", "age": 25}

Object Type	Mutable?	Behavior when passed to function
`list`, `dict`	✅	Passed by reference → changes affect original
Custom objects	✅	Passed by reference → changes affect original
`int`, `float`	❌	Passed by value → cannot mutate original
`str`, `tuple`	❌	Passed by value → cannot mutate original

3. Functions

Typescript

function add(a: number, b: number): number { return a + b; }

(a,b) => a+b // Arrow functions

Python

def add(a: int, b: int) -> int: return a + b

add = lambda a, b: a + b

Feature	JS Arrow Function	Python Lambda
Syntax	`(a, b) => a + b`	`lambda a, b: a + b`
Anonymous	Yes	Yes
Implicit return	✅ (expression only)	✅ (expression only)
Multiple statements	❌ (unless wrapped in `{}`)	❌ (expression only)
`this` binding	Lexical (inherits outer this)	❌ Not applicable; uses `self` in methods
Scope	Block scope	Uses normal Python scoping rules

4. Control Flow

No braces {}, indentation defines blocks.

Typescript

if (x > 5) { console.log("yes"); 
} else { 
console.log("no"); 
}

Python

if x > 5:
    print("yes")
else:
    print("no")

5. Loops

No parentheses or braces or semicolon, indentation defines the block.
Python uses range(n) for 0…n-1.
Python doesn’t have a forEach method for lists; a normal for loop is used.

TypeScript

for (let i = 0; i < 5; i++) {
    console.log(i);
}

let i = 0;
while (i < 5) {
    console.log(i);
    i++;
}

const arr = [10, 20, 30];
arr.forEach((num) => {
    console.log(num);
});

Python

for i in range(5):
    print(i)
//or
arr = [10, 20, 30]
for num in arr:
    print(num)


i = 0
while i < 5:
    print(i)
    i += 1

for index, value in enumerate(arr):
    print(index, value)

6. Classes & OOP

this(ts/js) → self(py)

No public/private keywords; use _name for private convention.

Python doesn't need 'new' keyword to create objects for a class.

Unlike TS, Python lets you add attributes dynamically to objects

Typescript class

class Person {
    name: string;
    constructor(name: string) { this.name = name; }
    greet() { console.log("Hello " + this.name); }
}

const p1 = new Person("Alice");

console.log(p1.name);   // Output: Alice

p1.greet();  // Hello Alice

Python class

class Person:
    def __init__(self, name: str):
        self.name = name
    def greet(self):
        print("Hello " + self.name)

p1 = Person("Alice")

print(p1.name)  # Output: Alice

p1.greet()   # Hello Alice

# Unlike TS, Python lets you add attributes dynamically to objects:
p1.age = 25
print(p1.age)  # 25

Inheritance

TypeScript class Child extends Parent {}

Python class Child(ParentClassName)

TypeScript super()

Python super().__init__()

TypeScript allows only single class inheritance, multi-level inheritance, doesn't support multiple inheritance by default but can be implemented using interfaces and mixins.

Python allows all types of inheritance, including multiple and hybrid inheritance.
Python resolves method conflicts using MRO (Method Resolution Order), which is left-to-right (class C(A, B) → A before B).

Typescript Example for inheritance

class Animal {
    name: string;

    constructor(name: string) {
        this.name = name;
    }

    speak() {
        console.log(this.name + " makes a sound");
    }
}


class Dog extends Animal {
    constructor(name: string) {
        super(name); // Call parent constructor
    }

    speak() {
        console.log(this.name + " barks");
    }
}

const d = new Dog("Buddy");
d.speak();  // Buddy barks

Python example for inheritance

class Animal:
    def __init__(self, name: str):
        self.name = name

    def speak(self):
        print(self.name + " makes a sound")


class Dog(Animal):
    def __init__(self, name: str):
        super().__init__(name)  # Call parent constructor

    def speak(self):
        print(self.name + " barks")

d = Dog("Buddy")
d.speak()   # Buddy barks

7. Modules / Imports

TS/JS → Must export explicitly.

Python → Everything is importable by default (unless private name or restricted by `all).all_ = ["Person"] # only Person is exportable from this file.py`

Typescript

import { readFile } from 'fs';

export function something(){...}

Python

from os import read

8. Exception Handling

ts -> try, catch, finally
py -> try, except, finally

Typescript Example

try {
    riskyOperation();
} catch (err) {
    console.error(err);
} finally {
    cleanup();
}

Python Example

try:
    risky_operation()
except Exception as err:
    print(err)
finally:
    cleanup()

9. Async/Await

typescript

async function fetchData() { await fetch(url); }

python

import asyncio, aiohttp

async def fetch_data():
    async with aiohttp.ClientSession() as session:
        async with session.get(url) as resp:
            return await resp.text()

10. Spread & Rest Operators - Unpacking & Variadic Operators

JS/TS ...spread → Python * (for lists/tuples) and ** (for dicts).

JS/TS ...rest in functions → Python *args (positional) and **kwargs (keyword args).

Typescript examples

const arr1 = [1, 2, 3];
const arr2 = [0, ...arr1, 4];
console.log(arr2); // [0, 1, 2, 3, 4]

const obj1 = {a: 1, b: 2};
const obj2 = {...obj1, c: 3};
console.log(obj2); // {a: 1, b: 2, c: 3}

function sum(...nums: number[]): number {
    return nums.reduce((a, b) => a + b, 0);
}
console.log(sum(1, 2, 3, 4)); // 10

function printUser({name, age}: {name: string; age: number}) {
    console.log(name, age);
}
printUser({name: "Alice", age: 25});

Python Examples

arr1 = [1, 2, 3]
arr2 = [0, *arr1, 4]
print(arr2)  # [0, 1, 2, 3, 4]


obj1 = {"a": 1, "b": 2}
obj2 = {**obj1, "c": 3}
print(obj2)  # {'a': 1, 'b': 2, 'c': 3}

def sum_all(*nums: int) -> int:
    return sum(nums)

print(sum_all(1, 2, 3, 4))  # 10

def print_user(**kwargs):
    print(kwargs["name"], kwargs["age"])

print_user(name="Alice", age=25)

11. No object destructuring, only sequence unpacking.

Python examples

a, b, c = 1, 2, 3
print(a, b, c)  # 1 2 3

a, *rest = [1, 2, 3, 4, 5]
print(a)      # 1
print(rest)   # [2, 3, 4, 5]


user = {"name": "Alice", "age": 25}
name, age = user["name"], user["age"]
print(name, age)  # Alice 25

12. No interfaces in python

Python has no explicit interface keyword.

Use Abstract Base Classes (ABC) or Protocols if you want strict contracts.

Python mostly relies on duck typing → “if it walks like a duck and quacks like a duck, it’s a duck.”

Example:

# 1. ABC
from abc import ABC, abstractmethod

class Person(ABC):
    @abstractmethod
    def greet(self):
        pass

class Student(Person):
    def __init__(self, name: str):
        self.name = name

    def greet(self):
        print("Hello " + self.name)

#Protocols
from typing import Protocol

class Greeter(Protocol):
    name: str
    def greet(self) -> None: ...

class Student:
    def __init__(self, name: str):
        self.name = name
    def greet(self) -> None:
        print("Hello " + self.name)

def welcome(g: Greeter):
    g.greet()

welcome(Student("Alice"))


#Duck typing
class Student:
    def __init__(self, name):
        self.name = name
    def greet(self):
        print("Hello " + self.name)

def welcome(person):
    person.greet()   # no interface needed!

welcome(Student("Alice"))

13. No hoisting, uses function/global/nonlocal scopes

Hoisting → Not in Python.

Block scope → Not in Python (if/for/while don’t create scopes).

Function scope → Yes, like JS.

Global scope → Yes, but must declare global to modify.

Nonlocal → Python-only (for nested functions).

Examples:

print(a)   # NameError - no hoisting
a = 5


if True:
    x = 10
print(x)   #  10 (still accessible, variables leaks out from if,while,for)


def foo():
    x = 10
    print(x)
foo()
print(x)  #  NameError x is function scoped

x = 5
def foo():
    global x 
    x = 10

foo()
print(x)  # 10

def outer():
    x = "outer"
    def inner():
        nonlocal x
        x = "inner"
    inner()
    print(x)

outer()  # inner

Feature	JS / TS Closures	Python Closures
Captures outer variables	✅	✅
Modify outer variables	✅ directly	✅ need `nonlocal`
Syntax	`function` or arrow functions	`def` functions
Lexical scope	✅	✅

16. Coroutines

A coroutine is like a function that can pause and resume.

Example:

import asyncio

async def fetch_data():
    print("start")
    await asyncio.sleep(1)   # pauses here, gives control back to event loop
    print("end")

asyncio.run(fetch_data())

async def → defines a coroutine.

await → suspends coroutine until the awaited task is done.

The event loop runs coroutines, switching between them when they pause.

Multitasking example

import asyncio

async def task(name):
    for i in range(3):
        print(f"{name} {i}")
        await asyncio.sleep(0.5)

async def main():
    await asyncio.gather(task("A"), task("B"))

asyncio.run(main())

Output

A 0
B 0
A 1
B 1
A 2
B 2

15. Futures in Python

A Future represents a placeholder for a result that is not yet available — like a JS Promise.

Used in asyncio and concurrent.futures.

Lets you schedule work and get the result later.

Example:

import asyncio

async def task():
    await asyncio.sleep(1)
    return "done"

async def main():
    future = asyncio.create_task(task())  # returns a Future
    result = await future                  # wait for completion
    print(result)

asyncio.run(main())

output:

done

16. JS Event loop vs Python asyncio Event loop

Feature	JavaScript Event Loop	Python asyncio Event Loop
Threads	Single-threaded (libuv)	Single-threaded (unless threads/multiprocessing)
Microtasks	Yes (Promises run before timers)	No explicit microtask queue
Async Syntax	`async/await` built on Promises	`async/await` built on coroutines
Scheduling	Microtasks, macrotasks, timers, I/O	Tasks, Futures, coroutines, callbacks
Parallel CPU work	Worker threads / child_process	Multiprocessing (bypasses GIL)

17. Concurrency in Python

Concurrency = handling multiple tasks at the same time, but not necessarily in parallel.

Tasks may interleave on a single thread.
Parallelism = tasks truly run at the same time (requires multiple CPU cores).

1. Threading

Uses threading.Thread.

Multiple threads share memory.

GIL limits CPU-bound parallelism, but threads are great for I/O-bound tasks.

import threading
import time

def worker(n):
    time.sleep(1)
    print(f"Worker {n} done")

threads = [threading.Thread(target=worker, args=(i,)) for i in range(3)]
[t.start() for t in threads]
[t.join() for t in threads]

2. Process

Uses multiprocessing.Process.

Each process has its own memory → bypasses GIL.

Ideal for CPU-heavy tasks.

from multiprocessing import Process

def worker(n):
    print(f"Worker {n} done")

processes = [Process(target=worker, args=(i,)) for i in range(3)]
[p.start() for p in processes]
[p.join() for p in processes]

3. asyncio

Single-threaded, event-loop-driven.

Use async def + await + asyncio.run()

Efficient for network requests, file I/O, or any wait-based operations.

import asyncio

async def task(n):
    await asyncio.sleep(1)
    print(f"Task {n} done")

async def main():
    await asyncio.gather(*(task(i) for i in range(3)))

asyncio.run(main())

Model	Thread	Process	Asyncio
Use case	I/O	CPU	I/O
True parallelism	❌ GIL limits CPU	✅ separate memory	❌ single-threaded
Syntax	threading.Thread	multiprocessing.Process	async/await
Shared memory	✅	❌	✅

GIL = Global Interpreter Lock

It’s a mutex (lock) in CPython (the standard Python interpreter).

Purpose: Ensure that only one thread executes Python bytecode at a time.

How GIL Works Internally

Every CPython interpreter has a single global lock (the GIL).

When a thread wants to execute Python code:

It acquires the GIL.

Executes some bytecode instructions.

Releases the GIL (or periodically checks if another thread should run).

CPython switches threads periodically, typically every 5 milliseconds (or after PyEval_Threadslice ticks).

C extensions can temporarily release the GIL if they perform long-running C operations, allowing other threads to run.

I/O-bound tasks

→ GIL is released when threads wait on I/O, allowing other threads to run.

CPU-bound tasks

→ threads compete for GIL → no real speedup on multiple cores.

IPC

Feature	Threads	Processes
Memory shared	✅ Yes	❌ No
Communication channel	Optional (direct vars)	Required IPC (Queue, Pipe, SharedMemory)
Race condition risk	✅ Yes (use locks)	✅ Minimal (processes isolated)
Use case	I/O-bound concurrency	CPU-bound parallelism

18. Decorators

A decorator is a function that wraps another function, method, or class, modifying its behavior without changing its code.

TS decorator Example

Must enable experimentalDecorators in tsconfig.json.

Can decorate classes, methods, properties, or parameters.

function log(target: any, propertyKey: string, descriptor: PropertyDescriptor) {
    const original = descriptor.value;
    descriptor.value = function(...args: any[]) {
        console.log(`Calling ${propertyKey} with`, args);
        return original.apply(this, args);
    }
}

class Example {
    @log
    greet(name: string) {
        console.log("Hello " + name);
    }
}

const ex = new Example();
ex.greet("Alice");
// Output:
// Calling greet with ['Alice']
// Hello Alice

Python decorators Example

Decorators can wrap functions, methods, or classes.

Use @decorator_name syntax.

def log(func):
    def wrapper(*args, **kwargs):
        print(f"Calling {func.__name__} with {args}")
        return func(*args, **kwargs)
    return wrapper

class Example:
    @log
    def greet(self, name):
        print("Hello", name)

ex = Example()
ex.greet("Alice")
# Output:
# Calling greet with (<__main__.Example object at 0x...>, 'Alice')
# Hello Alice

Feature	TypeScript Decorator	Python Decorator
Syntax	`@decorator`	`@decorator`
Targets	Class, method, property, parameter	Function, method, class
Arguments	target, propertyKey, descriptor	function (or class)
Returns	descriptor / modified function	wrapped function or class
Requires setup	`experimentalDecorators: true`	Built-in
Meta-programming power	Limited to TS metadata + reflection	Full access to function/class objects

@property - Property decorator

Decorator that turns a method into a “readable attribute”

Allows custom behavior when getting, setting, or deleting an attribute

Lets you encapsulate logic without changing the external API

class Person:
    def __init__(self, name):
        self._name = name  # convention: _name = private

    @property
    def name(self):
        """Getter for name"""
        return self._name

    @name.setter
    def name(self, value):
        """Setter for name"""
        if not value:
            raise ValueError("Name cannot be empty")
        self._name = value

p = Person("Alice")
print(p.name)   # Alice (calls getter)
p.name = "Bob"  # calls setter
print(p.name)   # Bob
# p.name = ""   # raises ValueError

19. Special method or dunner methods

Also called “dunder” methods (double underscore): method

Allow objects to behave like built-in types

Examples: string representation, comparison, arithmetic

Python Special Method	Purpose	TS Equivalent (approx)
`__str__`	Human-readable string	`toString()`
`__repr__`	Debug string	Custom method / JSON.stringify
`__eq__`	Equality operator	`==` / custom method
`__add__`	Addition operator	No direct equivalent
Others	`__sub__`, `__len__`, `__getitem__`	Methods / index access

20. Iterators & Generators

Iterable

An object you can loop over with for

Must implement iter() method that returns an iterator

Iterator

An object that produces items one at a time

Must implement next() method (Python 3: next() function)

Raises StopIteration when done

# Iterable example
numbers = [1, 2, 3]  # list is iterable
it = iter(numbers)   # creates iterator
print(next(it))  # 1
print(next(it))  # 2
print(next(it))  # 3
# next(it) -> StopIteration

Generator Functions

Functions that yield values one at a time using yield

Lazy evaluation → computes values on demand (memory efficient)

def count_up_to(n):
    i = 1
    while i <= n:
        yield i
        i += 1

for num in count_up_to(3):
    print(num)
# Output: 1 2 3

List comprehension vs Generators

Feature	List Comprehension	Generator Expression
Syntax	`[x*x for x in range(5)]`	`(x*x for x in range(5))`
Evaluation	Eager (creates full list)	Lazy (yields one item at a time)
Memory Usage	High for large lists	Low (good for large datasets)
Use Case	Small datasets / when all values are needed	Streaming / large datasets

# List comprehension (eager)
squares_list = [x*x for x in range(5)]
print(squares_list)  # [0, 1, 4, 9, 16]

# Generator expression (lazy)
squares_gen = (x*x for x in range(5))
for s in squares_gen:
    print(s)

Summary

Iterable: object you can loop over (list, tuple, dict)

Iterator: produces items one at a time (next)

Generator function: uses yield, lazy evaluation, memory efficient

Generator expression: lazy, similar to list comprehension, uses parentheses

Helper Methods

1. String helper methods

Operation / Method	Python Example	TypeScript/JS Equivalent	Notes
Lowercase	`"Hello".lower()`	`"Hello".toLowerCase()`	Returns new string
Uppercase	`"Hello".upper()`	`"Hello".toUpperCase()`	Returns new string
Strip / Trim	`" Hello ".strip()`	`" Hello ".trim()`	Removes leading/trailing whitespace
Left/Right Trim	`" Hello".lstrip()` / `"Hello ".rstrip()`	`" Hello".trimStart()` / `"Hello ".trimEnd()`	Python distinguishes left/right
Replace	`"Hello".replace("H","J")`	`"Hello".replace("H","J")`	Returns new string
Split	`"a,b,c".split(",")`	`"a,b,c".split(",")`	Returns list/array
Join	`",".join(["a","b","c"])`	`["a","b","c"].join(",")`	Concatenate with separator
StartsWith	`"Hello".startswith("He")`	`"Hello".startsWith("He")`	Returns bool
EndsWith	`"Hello".endswith("lo")`	`"Hello".endsWith("lo")`	Returns bool
Contains / Includes	`"Hello" in "Hello World"`	`"Hello World".includes("Hello")`	Python uses `in` operator
Find / Index	`"Hello".find("l")`	`"Hello".indexOf("l")`	Returns first index or -1 (`find`)
Count occurrences	`"Hello".count("l")`	N/A	Returns number of matches
Format / Interpolation	`f"Hello {name}"`	`Hello ${name}`	f-strings are equivalent to template literals

2. Array helper methods

Operation / Method	Python Example	TypeScript/JS Equivalent	Notes
Length	`len(arr)`	`arr.length`	Built-in function
IndexOf	`arr.index(2)`	`arr.indexOf(2)`	Raises `ValueError` if not found
Slice	`arr[1:3]`	`arr.slice(1,3)`	Returns a new list/array
Splice / Insert	`arr[1:1] = [10]` or `arr.insert(1, 10)`	`arr.splice(1,0,10)`	Insert at index
Append / Push	`arr.append(4)`	`arr.push(4)`	Adds single item at end
Extend / Concat	`arr.extend([4,5])`	`arr.concat([4,5])`	Add multiple items
Remove by value	`arr.remove(2)`	`arr.splice(arr.indexOf(2),1)`	Removes first occurrence
Pop	`arr.pop()`	`arr.pop()`	Remove last item
Shift / Pop first element	`arr.pop(0)`	`arr.shift()`	Remove first element
Unshift / Insert at start	`arr.insert(0, x)`	`arr.unshift(x)`	Insert at beginning
Includes / Membership	`2 in arr`	`arr.includes(2)`	Returns bool
Reverse	`arr.reverse()`	`arr.reverse()`	In-place
Sort	`arr.sort()`	`arr.sort()`	In-place
List Comprehension / Map	`[x*2 for x in arr]`	`arr.map(x => x*2)`	Returns new list/array
Filter	`[x for x in arr if x>2]`	`arr.filter(x => x>2)`	Returns new list/array
Reduce	`from functools import reduce; reduce(func, arr)`	`arr.reduce(func)`	Aggregate / accumulate values
Every	`all(x % 2 == 0 for x in arr)`	`arr.every(x => x % 2 === 0)`	Returns True if all elements satisfy condition
Some	`any(x % 2 == 0 for x in arr)`	`arr.some(x => x % 2 === 0)`	Returns True if any element satisfies condition
Find	`next((x for x in arr if x>2), None)`	`arr.find(x => x>2)`	Returns first match or None
ForEach / Loop	`for x in arr: ...`	`arr.forEach(x => ...)`	Iteration

3. Dictionary / Object helper methods

Operation / Method	Python Example	TypeScript/JS Equivalent	Notes
Get value	`d.get("key")`	`obj.key` / `obj["key"]`	Returns `None` if key not found
Set value	`d["key"] = value`	`obj.key = value`	Add/update key
Keys	`d.keys()`	`Object.keys(obj)`	Returns iterable
Values	`d.values()`	`Object.values(obj)`	Returns iterable
Items	`d.items()`	`Object.entries(obj)`	Returns key/value pairs
Pop	`d.pop("key")`	`delete obj.key`	Removes key