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
-
Use when checking pairs/subarrays in sorted data.
-
Great for substrings/subarrays with max/min/unique.
-
Fast & Slow Pointers (Cycle Detection)
Detect cycles or find middle in linked lists.
-
When working with overlapping intervals.
-
Perfect for finding missing/duplicate in 1..n arrays.
-
When data is sorted and you need to search quickly.
-
Traverse graphs/trees or explore grids.
-
Generate all combinations/permutations/choices.
-
Optimal for overlapping subproblems & recursion.
-
Pick local best to build global solution.
-
For top-k, scheduling, median, streaming data.
-
Union Find (Disjoint Set Union - DSU)
Check connectivity / detect cycles efficiently.
-
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
Top comments (0)