Problem: Find two numbers in the array that add up to a specific target.
Solution:
function twoSum(nums: number[], target: number): number[] {
const map = new Map<number, number>(); // Value to index map
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement)!, i];
}
map.set(nums[i], i);
}
return [];
}Problem: Maximize profit by choosing one day to buy and another to sell. Solution:
function maxProfit(prices: number[]): number {
let minPrice = Number.MAX_SAFE_INTEGER;
let maxProfit = 0;
for (const price of prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}Problem: Merge two sorted arrays into one sorted array. Solution:
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
let i = m - 1;
let j = n - 1;
let k = m + n - 1;
while (i >= 0 && j >= 0) {
nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}Problem: Check if an array contains duplicates. Solution:
function containsDuplicate(nums: number[]): boolean {
const set = new Set<number>();
for (const num of nums) {
if (set.has(num)) return true;
set.add(num);
}
return false;
}Problem: Return an array where each element is the product of all other elements. Solution:
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const res: number[] = new Array(n).fill(1);
let left = 1;
let right = 1;
for (let i = 0; i < n; i++) {
res[i] *= left;
left *= nums[i];
res[n - 1 - i] *= right;
right *= nums[n - 1 - i];
}
return res;
}Problem: Find the contiguous subarray with the largest sum.
Solution:
function maxSubArray(nums: number[]): number {
let maxSum = nums[0];
let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}Problem: Find all unique triplets in the array which gives the sum of zero. Solution:
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;
let 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;
}Problem: Merge overlapping intervals.
Solution:
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
const merged: number[][] = [];
for (const interval of intervals) {
if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
merged.push(interval);
} else {
merged[merged.length - 1][1] = Math.max(
merged[merged.length - 1][1],
interval[1]
);
}
}
return merged;
}Problem: Find the maximum water that can be trapped between two lines.
Solution:
function maxArea(height: number[]): number {
let left = 0;
let right = height.length - 1;
let maxWater = 0;
while (left < right) {
maxWater = Math.max(
maxWater,
Math.min(height[left], height[right]) * (right - left)
);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}Problem: Rotate a matrix 90 degrees clockwise.
Solution:
function rotate(matrix: number[][]): void {
const n = matrix.length;
// Transpose the matrix
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
// Reverse each row
for (const row of matrix) {
row.reverse();
}
}function isValid(s: string): boolean {
const stack: string[] = [];
const map = new Map<string, string>([
[")", "("],
["}", "{"],
["]", "["],
]);
for (const c of s) {
if (map.has(c)) {
if (stack.length === 0 || stack.pop() !== map.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.length === 0;
}function isPalindrome(s: string): boolean {
let left = 0;
let right = s.length - 1;
while (left < right) {
while (left < right && !isAlphaNumeric(s[left])) left++;
while (left < right && !isAlphaNumeric(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left++;
right--;
}
return true;
}
function isAlphaNumeric(char: string): boolean {
return /[a-zA-Z0-9]/.test(char);
}function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false;
const count: number[] = new Array(26).fill(0);
for (const c of s) {
count[c.charCodeAt(0) - "a".charCodeAt(0)]++;
}
for (const c of t) {
if (--count[c.charCodeAt(0) - "a".charCodeAt(0)] < 0) {
return false;
}
}
return true;
}function groupAnagrams(strs: string[]): string[][] {
const map = new Map<string, string[]>();
for (const s of strs) {
const sorted = s.split("").sort().join("");
if (!map.has(sorted)) {
map.set(sorted, []);
}
map.get(sorted)!.push(s);
}
const result: string[][] = [];
for (const group of map.values()) {
result.push(group);
}
return result;
}function longestPalindrome(s: string): string {
const n = s.length;
let start = 0;
let maxLength = 1;
const dp: boolean[][] = Array(n)
.fill(null)
.map(() => Array(n).fill(false));
// Every single character is a palindrome
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
// Check for all possible substrings
for (let i = n - 1; i >= 0; i--) {
for (let j = i + 1; j < n; j++) {
if (s[i] === s[j] && (j - i === 1 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (j - i + 1 > maxLength) {
start = i;
maxLength = j - i + 1;
}
}
}
}
return s.substring(start, start + maxLength);
}function minWindow(s: string, t: string): string {
const freq = new Map<string, number>();
for (const c of t) {
freq.set(c, (freq.get(c) || 0) + 1);
}
let left = 0;
let minLen = Number.MAX_SAFE_INTEGER;
let count = 0;
let start = 0;
for (let right = 0; right < s.length; right++) {
const rightChar = s[right];
if (freq.has(rightChar)) {
freq.set(rightChar, freq.get(rightChar)! - 1);
if (freq.get(rightChar)! >= 0) count++;
}
while (count === t.length) {
if (minLen > right - left + 1) {
minLen = right - left + 1;
start = left;
}
const leftChar = s[left];
if (freq.has(leftChar)) {
freq.set(leftChar, freq.get(leftChar)! + 1);
if (freq.get(leftChar)! > 0) count--;
}
left++;
}
}
return minLen === Number.MAX_SAFE_INTEGER
? ""
: s.substring(start, start + minLen);
}function strStr(haystack: string, needle: string): number {
const m = haystack.length;
const n = needle.length;
for (let i = 0; i <= m - n; i++) {
if (haystack.substring(i, i + n) === needle) {
return i;
}
}
return -1;
}function compress(chars: string[]): number {
let index = 0;
const n = chars.length;
let i = 0;
while (i < n) {
const c = chars[i];
let count = 0;
while (i < n && chars[i] === c) {
i++;
count++;
}
chars[index++] = c;
if (count > 1) {
for (const digit of count.toString()) {
chars[index++] = digit;
}
}
}
return index;
}function longestCommonPrefix(strs: string[]): string {
if (strs.length === 0) return "";
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.substring(0, prefix.length - 1);
if (prefix === "") return "";
}
}
return prefix;
}function repeatedSubstringPattern(s: string): boolean {
const doubled = s + s;
return doubled.substring(1, doubled.length - 1).indexOf(s) !== -1;
}// Definition for singly-linked list
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
while (head) {
const nextNode = head.next;
head.next = prev;
prev = head;
head = nextNode;
}
return prev;
}function mergeTwoLists(
list1: ListNode | null,
list2: ListNode | null
): ListNode | null {
if (!list1) return list2;
if (!list2) return list1;
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
const dummy = new ListNode(0, head);
let slow: ListNode | null = dummy;
let fast: ListNode | null = dummy;
for (let i = 0; i <= n; i++) {
fast = fast!.next;
}
while (fast) {
slow = slow!.next;
fast = fast.next;
}
slow!.next = slow!.next!.next;
return dummy.next;
}function hasCycle(head: ListNode | null): boolean {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}function addTwoNumbers(
l1: ListNode | null,
l2: ListNode | null
): ListNode | null {
const dummy = new ListNode();
let current = dummy;
let carry = 0;
while (l1 || l2 || carry) {
let sum = carry;
if (l1) {
sum += l1.val;
l1 = l1.next;
}
if (l2) {
sum += l2.val;
l2 = l2.next;
}
carry = Math.floor(sum / 10);
current.next = new ListNode(sum % 10);
current = current.next;
}
return dummy.next;
}function getIntersectionNode(
headA: ListNode | null,
headB: ListNode | null
): ListNode | null {
let a = headA;
let b = headB;
while (a !== b) {
a = a ? a.next : headB;
b = b ? b.next : headA;
}
return a;
}function isPalindrome(head: ListNode | null): boolean {
let slow = head;
let fast = head;
let prev: ListNode | null = null;
// Find middle and reverse first half
while (fast && fast.next) {
fast = fast.next.next;
const temp = slow!.next;
slow!.next = prev;
prev = slow;
slow = temp;
}
// If odd number of nodes, skip the middle node
if (fast) slow = slow!.next;
// Compare the two halves
while (slow) {
if (slow.val !== prev!.val) return false;
slow = slow.next;
prev = prev!.next;
}
return true;
}function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
let temp = head;
for (let i = 0; i < k; i++) {
if (!temp) return head;
temp = temp.next;
}
let prev: ListNode | null = null;
let current = head;
let next: ListNode | null = null;
for (let i = 0; i < k; i++) {
next = current!.next;
current!.next = prev;
prev = current;
current = next;
}
head!.next = reverseKGroup(next, k);
return prev;
}
# Stacks and Queues (6 Questions)
### 1. Implement Queue Using Stacks (LeetCode 232)
```typescript
class MyQueue {
private s1: number[] = [];
private s2: number[] = [];
push(x: number): void {
this.s1.push(x);
}
pop(): number {
this.peek();
return this.s2.pop()!;
}
peek(): number {
if (this.s2.length === 0) {
while (this.s1.length > 0) {
this.s2.push(this.s1.pop()!);
}
}
return this.s2[this.s2.length - 1];
}
empty(): boolean {
return this.s1.length === 0 && this.s2.length === 0;
}
}class MyStack {
private q1: number[] = [];
private q2: number[] = [];
push(x: number): void {
this.q2.push(x);
while (this.q1.length > 0) {
this.q2.push(this.q1.shift()!);
}
[this.q1, this.q2] = [this.q2, this.q1];
}
pop(): number {
return this.q1.shift()!;
}
top(): number {
return this.q1[0];
}
empty(): boolean {
return this.q1.length === 0;
}
}class MinStack {
private s: number[] = [];
private minS: number[] = [];
push(val: number): void {
this.s.push(val);
if (this.minS.length === 0 || val <= this.minS[this.minS.length - 1]) {
this.minS.push(val);
}
}
pop(): void {
if (this.s[this.s.length - 1] === this.minS[this.minS.length - 1]) {
this.minS.pop();
}
this.s.pop();
}
top(): number {
return this.s[this.s.length - 1];
}
getMin(): number {
return this.minS[this.minS.length - 1];
}
}function dailyTemperatures(temperatures: number[]): number[] {
const stack: number[] = [];
const res: number[] = new Array(temperatures.length).fill(0);
for (let i = 0; i < temperatures.length; i++) {
while (
stack.length > 0 &&
temperatures[i] > temperatures[stack[stack.length - 1]]
) {
const index = stack.pop()!;
res[index] = i - index;
}
stack.push(i);
}
return res;
}function evalRPN(tokens: string[]): number {
const stack: number[] = [];
for (const token of tokens) {
if (["+", "-", "*", "/"].includes(token)) {
const b = stack.pop()!;
const a = stack.pop()!;
if (token === "+") stack.push(a + b);
else if (token === "-") stack.push(a - b);
else if (token === "*") stack.push(a * b);
else stack.push(Math.trunc(a / b));
} else {
stack.push(parseInt(token));
}
}
return stack[0];
}function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
const map = new Map<number, number>();
const stack: number[] = [];
for (const num of nums2) {
while (stack.length > 0 && stack[stack.length - 1] < num) {
map.set(stack.pop()!, num);
}
stack.push(num);
}
const res: number[] = [];
for (const num of nums1) {
res.push(map.has(num) ? map.get(num)! : -1);
}
return res;
}function nextGreaterElements(nums: number[]): number[] {
const n = nums.length;
const res: number[] = new Array(n).fill(-1);
const stack: number[] = [];
for (let i = 0; i < 2 * n; i++) {
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i % n]) {
res[stack.pop()!] = nums[i % n];
}
if (i < n) stack.push(i);
}
return res;
}class MyCircularQueue {
private q: number[];
private head: number = -1;
private tail: number = -1;
private size: number;
constructor(k: number) {
this.q = new Array(k);
this.size = k;
}
enQueue(value: number): boolean {
if (this.isFull()) return false;
if (this.isEmpty()) this.head = 0;
this.tail = (this.tail + 1) % this.size;
this.q[this.tail] = value;
return true;
}
deQueue(): boolean {
if (this.isEmpty()) return false;
if (this.head === this.tail) {
this.head = this.tail = -1;
} else {
this.head = (this.head + 1) % this.size;
}
return true;
}
Front(): number {
return this.isEmpty() ? -1 : this.q[this.head];
}
Rear(): number {
return this.isEmpty() ? -1 : this.q[this.tail];
}
isEmpty(): boolean {
return this.head === -1;
}
isFull(): boolean {
return (this.tail + 1) % this.size === this.head;
}
}function search(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}function searchRange(nums: number[], target: number): number[] {
let left = 0;
let right = nums.length - 1;
const result: number[] = [-1, -1];
// Find the first position
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
if (nums[mid] === target) result[0] = mid;
}
left = 0;
right = nums.length - 1;
// Find the last position
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] <= target) left = mid + 1;
else right = mid - 1;
if (nums[mid] === target) result[1] = mid;
}
return result;
}function searchMatrix(matrix: number[][], target: number): boolean {
const rows = matrix.length;
const cols = matrix[0].length;
let left = 0;
let right = rows * cols - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
const midElement = matrix[Math.floor(mid / cols)][mid % cols];
if (midElement === target) return true;
if (midElement < target) left = mid + 1;
else right = mid - 1;
}
return false;
}function search(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
// Check which side is sorted
if (nums[left] <= nums[mid]) {
// Left side is sorted
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
// Right side is sorted
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}function search(nums: number[], target: number): boolean {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return true;
// Handle duplicates
if (nums[left] === nums[mid] && nums[right] === nums[mid]) {
left++;
right--;
} else if (nums[left] <= nums[mid]) {
// Left side is sorted
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
// Right side is sorted
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return false;
}function findPeakElement(nums: number[]): number {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}// Definition for a binary tree node
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}function maxDepth(root: TreeNode | null): number {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
if (!t1 && !t2) return true;
if (!t1 || !t2 || t1.val !== t2.val) return false;
return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}
function isSymmetric(root: TreeNode | null): boolean {
return isMirror(root, root);
}function preorderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
if (root) stack.push(root);
while (stack.length > 0) {
const curr = stack.pop()!;
result.push(curr.val);
if (curr.right) stack.push(curr.right);
if (curr.left) stack.push(curr.left);
}
return result;
}function inorderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
let curr = root;
while (curr || stack.length > 0) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop()!;
result.push(curr.val);
curr = curr.right;
}
return result;
}function postorderTraversal(root: TreeNode | null): number[] {
const result: number[] = [];
const stack: TreeNode[] = [];
let lastVisited: TreeNode | null = null;
while (root || stack.length > 0) {
if (root) {
stack.push(root);
root = root.left;
} else {
const node = stack[stack.length - 1];
if (node.right && node.right !== lastVisited) {
root = node.right;
} else {
result.push(node.val);
lastVisited = node;
stack.pop();
}
}
}
return result;
}function levelOrder(root: TreeNode | null): number[][] {
const result: number[][] = [];
if (!root) return result;
const queue: TreeNode[] = [root];
while (queue.length > 0) {
const size = queue.length;
const level: number[] = [];
for (let i = 0; i < size; i++) {
const curr = queue.shift()!;
level.push(curr.val);
if (curr.left) queue.push(curr.left);
if (curr.right) queue.push(curr.right);
}
result.push(level);
}
return result;
}function height(root: TreeNode | null): number {
if (!root) return 0;
const leftHeight = height(root.left);
const rightHeight = height(root.right);
if (
leftHeight === -1 ||
rightHeight === -1 ||
Math.abs(leftHeight - rightHeight) > 1
) {
return -1;
}
return 1 + Math.max(leftHeight, rightHeight);
}
function isBalanced(root: TreeNode | null): boolean {
return height(root) !== -1;
}function backtrack(
candidates: number[],
target: number,
start: number,
current: number[],
result: number[][]
): void {
if (target === 0) {
result.push([...current]);
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > target) continue;
current.push(candidates[i]);
backtrack(candidates, target - candidates[i], i, current, result);
current.pop();
}
}
function combinationSum(candidates: number[], target: number): number[][] {
const result: number[][] = [];
const current: number[] = [];
backtrack(candidates, target, 0, current, result);
return result;
}function permuteHelper(
nums: number[],
start: number,
result: number[][]
): void {
if (start === nums.length) {
result.push([...nums]);
return;
}
for (let i = start; i < nums.length; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]]; // swap
permuteHelper(nums, start + 1, result);
[nums[start], nums[i]] = [nums[i], nums[start]]; // swap back
}
}
function permute(nums: number[]): number[][] {
const result: number[][] = [];
permuteHelper(nums, 0, result);
return result;
}function backtrack(
nums: number[],
start: number,
current: number[],
result: number[][]
): void {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
current.push(nums[i]);
backtrack(nums, i + 1, current, result);
current.pop();
}
}
function subsets(nums: number[]): number[][] {
const result: number[][] = [];
const current: number[] = [];
backtrack(nums, 0, current, result);
return result;
}function isSafe(board: string[], row: number, col: number, n: number): boolean {
for (let i = 0; i < row; i++) {
if (board[i][col] === "Q") return false;
}
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === "Q") return false;
}
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === "Q") return false;
}
return true;
}
function solve(
row: number,
board: string[],
result: string[][],
n: number
): void {
if (row === n) {
result.push([...board]);
return;
}
for (let col = 0; col < n; col++) {
if (isSafe(board, row, col, n)) {
board[row] =
board[row].substring(0, col) + "Q" + board[row].substring(col + 1);
solve(row + 1, board, result, n);
board[row] =
board[row].substring(0, col) + "." + board[row].substring(col + 1);
}
}
}
function solveNQueens(n: number): string[][] {
const result: string[][] = [];
const board: string[] = new Array(n).fill(".".repeat(n));
solve(0, board, result, n);
return result;
}function backtrack(
digits: string,
index: number,
current: string,
result: string[],
mapping: string[]
): void {
if (index === digits.length) {
result.push(current);
return;
}
for (const ch of mapping[parseInt(digits[index])]) {
backtrack(digits, index + 1, current + ch, result, mapping);
}
}
function letterCombinations(digits: string): string[] {
if (digits === "") return [];
const mapping = [
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
];
const result: string[] = [];
backtrack(digits, 0, "", result, mapping);
return result;
}function backtrack(
nums: number[],
start: number,
current: number[],
result: number[][]
): void {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue;
current.push(nums[i]);
backtrack(nums, i + 1, current, result);
current.pop();
}
}
function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const result: number[][] = [];
const current: number[] = [];
backtrack(nums, 0, current, result);
return result;
}function isValid(
board: string[][],
row: number,
col: number,
c: string
): boolean {
for (let i = 0; i < 9; i++) {
if (
board[i][col] === c ||
board[row][i] === c ||
board[Math.floor(row / 3) * 3 + Math.floor(i / 3)][
Math.floor(col / 3) * 3 + (i % 3)
] === c
) {
return false;
}
}
return true;
}
function solve(board: string[][]): boolean {
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] === ".") {
for (
let c = "1";
c <= "9";
c = String.fromCharCode(c.charCodeAt(0) + 1)
) {
if (isValid(board, i, j, c)) {
board[i][j] = c;
if (solve(board)) return true;
board[i][j] = ".";
}
}
return false;
}
}
}
return true;
}
function solveSudoku(board: string[][]): void {
solve(board);
}function climbStairs(n: number): number {
if (n <= 2) return n;
let a = 1;
let b = 2;
for (let i = 3; i <= n; i++) {
const c = a + b;
a = b;
b = c;
}
return b;
}function rob(nums: number[]): number {
let prev1 = 0;
let prev2 = 0;
for (const num of nums) {
const temp = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = temp;
}
return prev1;
}function coinChange(coins: number[], amount: number): number {
const dp: number[] = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (const coin of coins) {
for (let j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}function lengthOfLIS(nums: number[]): number {
const dp: number[] = new Array(nums.length).fill(1);
let maxLength = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}function longestCommonSubsequence(text1: string, text2: string): number {
const m = text1.length;
const n = text2.length;
const dp: number[][] = Array(m + 1)
.fill(null)
.map(() => 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];
}function uniquePaths(m: number, n: number): number {
const dp: number[][] = Array(m)
.fill(null)
.map(() => Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}function longestPalindrome(s: string): string {
const n = s.length;
const dp: boolean[][] = Array(n)
.fill(null)
.map(() => Array(n).fill(false));
let maxLength = 1;
let start = 0;
// Every single character is a palindrome
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
// Check for all possible substrings
for (let len = 2; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (s[i] === s[j] && (len === 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (len > maxLength) {
maxLength = len;
start = i;
}
}
}
}
return s.substring(start, start + maxLength);
}function findLength(nums1: number[], nums2: number[]): number {
const m = nums1.length;
const n = nums2.length;
const dp: number[][] = Array(m + 1)
.fill(null)
.map(() => Array(n + 1).fill(0));
let maxLength = 0;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}function canPartition(nums: number[]): boolean {
const sum = nums.reduce((acc, num) => acc + num, 0);
if (sum % 2 !== 0) return false;
const target = sum / 2;
const dp: boolean[] = new Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
for (let j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}function maxSubArray(nums: number[]): number {
let maxSum = nums[0];
let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}// Definition for graph node
class Node {
val: number;
neighbors: Node[];
constructor(val?: number, neighbors?: Node[]) {
this.val = val === undefined ? 0 : val;
this.neighbors = neighbors === undefined ? [] : neighbors;
}
}function cloneGraph(node: Node | null): Node | null {
if (!node) return null;
const visited = new Map<Node, Node>();
const queue: Node[] = [node];
visited.set(node, new Node(node.val));
while (queue.length > 0) {
const curr = queue.shift()!;
for (const neighbor of curr.neighbors) {
if (!visited.has(neighbor)) {
visited.set(neighbor, new Node(neighbor.val));
queue.push(neighbor);
}
visited.get(curr)!.neighbors.push(visited.get(neighbor)!);
}
}
return visited.get(node)!;
}function dfs(grid: string[][], i: number, j: number): void {
if (
i < 0 ||
j < 0 ||
i >= grid.length ||
j >= grid[0].length ||
grid[i][j] === "0"
)
return;
grid[i][j] = "0";
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
function numIslands(grid: string[][]): number {
let count = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === "1") {
count++;
dfs(grid, i, j);
}
}
}
return count;
}function canFinish(numCourses: number, prerequisites: number[][]): boolean {
const graph: number[][] = Array(numCourses)
.fill(null)
.map(() => []);
const inDegree: number[] = new Array(numCourses).fill(0);
for (const pre of prerequisites) {
graph[pre[1]].push(pre[0]);
inDegree[pre[0]]++;
}
const queue: number[] = [];
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) queue.push(i);
}
let count = 0;
while (queue.length > 0) {
const course = queue.shift()!;
count++;
for (const neighbor of graph[course]) {
if (--inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return count === numCourses;
}function isBipartite(graph: number[][]): boolean {
const n = graph.length;
const color: number[] = new Array(n).fill(-1);
for (let i = 0; i < n; i++) {
if (color[i] !== -1) continue;
const queue: number[] = [];
queue.push(i);
color[i] = 0;
while (queue.length > 0) {
const node = queue.shift()!;
for (const neighbor of graph[node]) {
if (color[neighbor] === -1) {
color[neighbor] = 1 - color[node];
queue.push(neighbor);
} else if (color[neighbor] === color[node]) {
return false;
}
}
}
}
return true;
}function orangesRotting(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const queue: [number, number][] = [];
let fresh = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) queue.push([i, j]);
if (grid[i][j] === 1) fresh++;
}
}
let minutes = 0;
const directions: [number, number][] = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];
while (queue.length > 0 && fresh > 0) {
const size = queue.length;
for (let i = 0; i < size; i++) {
const [x, y] = queue.shift()!;
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] === 1) {
grid[nx][ny] = 2;
queue.push([nx, ny]);
fresh--;
}
}
}
minutes++;
}
return fresh === 0 ? minutes : -1;
}function dfs(graph: number[][], visited: boolean[], node: number): void {
visited[node] = true;
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
dfs(graph, visited, neighbor);
}
}
}
function countComponents(n: number, edges: number[][]): number {
const graph: number[][] = Array(n)
.fill(null)
.map(() => []);
for (const edge of edges) {
graph[edge[0]].push(edge[1]);
graph[edge[1]].push(edge[0]);
}
const visited: boolean[] = new Array(n).fill(false);
let count = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
count++;
dfs(graph, visited, i);
}
}
return count;
}function singleNumber(nums: number[]): number {
let result = 0;
for (const num of nums) {
result ^= num;
}
return result;
}
// Explanation: XOR operation cancels out numbers that appear twice, leaving only the number that appears once.function reverseBits(n: number): number {
let result = 0;
for (let i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>>= 1; // Unsigned right shift
}
return result >>> 0; // Convert to unsigned 32-bit integer
}
// Explanation: Process each bit of the number, shifting the result left and appending the current bit of n to the result.function hammingWeight(n: number): number {
let count = 0;
while (n !== 0) {
count += n & 1;
n >>>= 1; // Unsigned right shift
}
return count;
}
// Explanation: Count the number of set bits (1s) by repeatedly masking the least significant bit and shifting the number right.function missingNumber(nums: number[]): number {
const n = nums.length;
let totalXOR = 0;
let arrayXOR = 0;
for (let i = 0; i <= n; i++) {
totalXOR ^= i;
}
for (const num of nums) {
arrayXOR ^= num;
}
return totalXOR ^ arrayXOR;
}