- Two Sum
- Best Time to Buy and Sell Stock
- Contains Duplicate
- Product of Array Except Self
- Maximum Subarray
- Maximum Product Subarray
- Find Minimum in Rotated Sorted Array
- Search in Rotated Sorted Array
- 3 Sum
- Container With Most Water
- Climbing Stairs
- Coin Change
- Longest Increasing Subsequence
- Longest Common Subsequence
- Word Break Problem
- Combination Sum
- House Robber
- House Robber II
- Decode Ways
- Unique Paths
- Jump Game
- Clone Graph
- Course Schedule
- Pacific Atlantic Water Flow
- Number of Islands
- Longest Consecutive Sequence
- Alien Dictionary
- Graph Valid Tree
- Number of Connected Components in an Undirected Graph
- Reverse a Linked List
- Detect Cycle in a Linked List
- Merge Two Sorted Lists
- Merge K Sorted Lists
- Remove Nth Node From End Of List
- Reorder List
- Longest Substring Without Repeating Characters
- Longest Repeating Character Replacement
- Minimum Window Substring
- Valid Anagram
- Group Anagrams
- Valid Parentheses
- Valid Palindrome
- Longest Palindromic Substring
- Palindromic Substrings
- Encode and Decode Strings
- Maximum Depth of Binary Tree
- Same Tree
- Invert/Flip Binary Tree
- Binary Tree Maximum Path Sum
- Binary Tree Level Order Traversal
- Serialize and Deserialize Binary Tree
- Subtree of Another Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Lowest Common Ancestor of BST
- Implement Trie (Prefix Tree)
- Add and Search Word
- Word Search II
Problem: Given an array of integers nums and an integer target, return indices of the two numbers that add up to target.
Brute Force Solution:
// Time: O(n²), Space: O(1)
function twoSumBrute(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}Optimal Solution:
// Time: O(n), Space: O(n)
function twoSum(nums, target) {
const map = new 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: Find the maximum profit from buying and selling a stock once.
Brute Force Solution:
// Time: O(n²), Space: O(1)
function maxProfitBrute(prices) {
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
}
}
return maxProfit;
}Optimal Solution:
// Time: O(n), Space: O(1)
function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (let price of prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}Problem: Check if array contains any duplicates.
Brute Force Solution:
// Time: O(n²), Space: O(1)
function containsDuplicateBrute(nums) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) return true;
}
}
return false;
}Optimal Solution:
// Time: O(n), Space: O(n)
function containsDuplicate(nums) {
const set = new Set(nums);
return set.size !== nums.length;
}Problem: Return array where each element is the product of all elements except itself (without division).
Brute Force Solution:
// Time: O(n²), Space: O(n)
function productExceptSelfBrute(nums) {
const result = [];
for (let i = 0; i < nums.length; i++) {
let product = 1;
for (let j = 0; j < nums.length; j++) {
if (i !== j) {
product *= nums[j];
}
}
result.push(product);
}
return result;
}Optimal Solution:
// Time: O(n), Space: O(1) - output array doesn't count
function productExceptSelf(nums) {
const n = nums.length;
const result = new Array(n);
// Calculate left products
result[0] = 1;
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
// Calculate right products and multiply
let right = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}
return result;
}Problem: Find the contiguous subarray with the largest sum (Kadane's Algorithm).
Brute Force Solution:
// Time: O(n²), Space: O(1)
function maxSubArrayBrute(nums) {
let maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
let currentSum = 0;
for (let j = i; j < nums.length; j++) {
currentSum += nums[j];
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}Optimal Solution:
// Time: O(n), Space: O(1)
function maxSubArray(nums) {
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 the contiguous subarray with the largest product.
Brute Force Solution:
// Time: O(n²), Space: O(1)
function maxProductBrute(nums) {
let maxProd = -Infinity;
for (let i = 0; i < nums.length; i++) {
let currentProd = 1;
for (let j = i; j < nums.length; j++) {
currentProd *= nums[j];
maxProd = Math.max(maxProd, currentProd);
}
}
return maxProd;
}Optimal Solution:
// Time: O(n), Space: O(1)
function maxProduct(nums) {
let maxProd = nums[0];
let currentMax = nums[0];
let currentMin = nums[0];
for (let i = 1; i < nums.length; i++) {
const temp = currentMax;
currentMax = Math.max(nums[i], currentMax * nums[i], currentMin * nums[i]);
currentMin = Math.min(nums[i], temp * nums[i], currentMin * nums[i]);
maxProd = Math.max(maxProd, currentMax);
}
return maxProd;
}Problem: Find the minimum element in a rotated sorted array.
Brute Force Solution:
// Time: O(n), Space: O(1)
function findMinBrute(nums) {
let min = nums[0];
for (let num of nums) {
min = Math.min(min, num);
}
return min;
}Optimal Solution:
// Time: O(log n), Space: O(1)
function findMin(nums) {
let left = 0;
let 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];
}Problem: Search for a target value in a rotated sorted array.
Brute Force Solution:
// Time: O(n), Space: O(1)
function searchBrute(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i;
}
return -1;
}Optimal Solution:
// Time: O(log n), Space: O(1)
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
// Left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}Problem: Find all unique triplets that sum to zero.
Brute Force Solution:
// Time: O(n³), Space: O(n)
function threeSumBrute(nums) {
const result = [];
const n = nums.length;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
const key = triplet.join(',');
if (!result.some(r => r.join(',') === key)) {
result.push(triplet);
}
}
}
}
}
return result;
}Optimal Solution:
// Time: O(n²), Space: O(n)
function threeSum(nums) {
const result = [];
nums.sort((a, b) => a - b);
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) {
result.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 result;
}Problem: Find two lines that together with x-axis form a container with most water.
Brute Force Solution:
// Time: O(n²), Space: O(1)
function maxAreaBrute(height) {
let maxArea = 0;
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
const area = Math.min(height[i], height[j]) * (j - i);
maxArea = Math.max(maxArea, area);
}
}
return maxArea;
}Optimal Solution:
// Time: O(n), Space: O(1)
function maxArea(height) {
let maxArea = 0;
let left = 0;
let right = height.length - 1;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}Problem: Add two integers without using + or - operators.
Brute Force Solution:
// Using built-in operators (not allowed)
function getSumBrute(a, b) {
return a + b;
}Optimal Solution:
// Time: O(1), Space: O(1)
function getSum(a, b) {
while (b !== 0) {
const carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}Problem: Count the number of 1 bits in an integer.
Brute Force Solution:
// Time: O(32), Space: O(1)
function hammingWeightBrute(n) {
let count = 0;
for (let i = 0; i < 32; i++) {
if ((n & (1 << i)) !== 0) {
count++;
}
}
return count;
}Problem: Design an algorithm to encode and decode a list of strings (Premium).
Optimal Solution:
// Time: O(n), Space: O(1)
function encode(strs) {
let result = "";
for (let str of strs) {
result += str.length + "#" + str;
}
return result;
}
function decode(s) {
const result = [];
let i = 0;
while (i < s.length) {
let j = i;
while (s[j] !== '#') j++;
const length = parseInt(s.substring(i, j));
const str = s.substring(j + 1, j + 1 + length);
result.push(str);
i = j + 1 + length;
}
return result;
}Problem: Find the maximum depth of a binary tree.
Brute Force Solution:
// Time: O(n), Space: O(n)
function maxDepthBrute(root) {
if (!root) return 0;
const queue = [[root, 1]];
let maxDepth = 0;
while (queue.length > 0) {
const [node, depth] = queue.shift();
maxDepth = Math.max(maxDepth, depth);
if (node.left) queue.push([node.left, depth + 1]);
if (node.right) queue.push([node.right, depth + 1]);
}
return maxDepth;
}Optimal Solution:
// Time: O(n), Space: O(h)
function maxDepth(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}Problem: Check if two binary trees are identical.
Brute Force Solution:
// Time: O(n), Space: O(n)
function isSameTreeBrute(p, q) {
const queue = [[p, q]];
while (queue.length > 0) {
const [node1, node2] = queue.shift();
if (!node1 && !node2) continue;
if (!node1 || !node2) return false;
if (node1.val !== node2.val) return false;
queue.push([node1.left, node2.left]);
queue.push([node1.right, node2.right]);
}
return true;
}Optimal Solution:
// Time: O(n), Space: O(h)
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}Problem: Invert a binary tree.
Brute Force Solution:
// Time: O(n), Space: O(n)
function invertTreeBrute(root) {
if (!root) return null;
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
[node.left, node.right] = [node.right, node.left];
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return root;
}Optimal Solution:
// Time: O(n), Space: O(h)
function invertTree(root) {
if (!root) return null;
[root.left, root.right] = [root.right, root.left];
invertTree(root.left);
invertTree(root.right);
return root;
}Problem: Find the maximum path sum in a binary tree.
Brute Force Solution:
// Time: O(n²), Space: O(h)
function maxPathSumBrute(root) {
let maxSum = -Infinity;
function allPaths(node, path, sum) {
if (!node) return;
sum += node.val;
maxSum = Math.max(maxSum, sum);
allPaths(node.left, path + 'L', sum);
allPaths(node.right, path + 'R', sum);
}
function helper(node) {
if (!node) return;
allPaths(node, '', 0);
helper(node.left);
helper(node.right);
}
helper(root);
return maxSum;
}Optimal Solution:
// Time: O(n), Space: O(h)
function maxPathSum(root) {
let maxSum = -Infinity;
function dfs(node) {
if (!node) return 0;
const left = Math.max(0, dfs(node.left));
const right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left, right);
}
dfs(root);
return maxSum;
}Problem: Return level order traversal of a binary tree.
Brute Force Solution:
// Time: O(n), Space: O(n)
function levelOrderBrute(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const level = [];
const size = queue.length;
for (let i = 0; i < size; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}Optimal Solution:
// Time: O(n), Space: O(n)
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length > 0) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}Problem: Serialize and deserialize a binary tree.
Brute Force Solution:
// Time: O(n), Space: O(n)
function serializeBrute(root) {
if (!root) return "null";
const result = [];
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
if (node) {
result.push(node.val);
queue.push(node.left);
queue.push(node.right);
} else {
result.push("null");
}
}
return result.join(",");
}
function deserializeBrute(data) {
const values = data.split(",");
if (values[0] === "null") return null;
const root = new TreeNode(parseInt(values[0]));
const queue = [root];
let i = 1;
while (queue.length > 0 && i < values.length) {
const node = queue.shift();
if (values[i] !== "null") {
node.left = new TreeNode(parseInt(values[i]));
queue.push(node.left);
}
i++;
if (i < values.length && values[i] !== "null") {
node.right = new TreeNode(parseInt(values[i]));
queue.push(node.right);
}
i++;
}
return root;
}Optimal Solution:
// Time: O(n), Space: O(n)
function serialize(root) {
const result = [];
function dfs(node) {
if (!node) {
result.push("null");
return;
}
result.push(node.val);
dfs(node.left);
dfs(node.right);
}
dfs(root);
return result.join(",");
}
function deserialize(data) {
const values = data.split(",");
let i = 0;
function dfs() {
if (values[i] === "null") {
i++;
return null;
}
const node = new TreeNode(parseInt(values[i]));
i++;
node.left = dfs();
node.right = dfs();
return node;
}
return dfs();
}Problem: Check if a tree is a subtree of another tree.
Brute Force Solution:
// Time: O(m * n), Space: O(h)
function isSubtreeBrute(root, subRoot) {
if (!root) return false;
function isSame(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p.val === q.val && isSame(p.left, q.left) && isSame(p.right, q.right);
}
if (isSame(root, subRoot)) return true;
return isSubtreeBrute(root.left, subRoot) || isSubtreeBrute(root.right, subRoot);
}Optimal Solution:
// Time: O(m * n), Space: O(h)
function isSubtree(root, subRoot) {
if (!subRoot) return true;
if (!root) return false;
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
return p.val === q.val &&
isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
}
return isSameTree(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
}Problem: Build tree from preorder and inorder arrays.
Brute Force Solution:
// Time: O(n²), Space: O(n)
function buildTreeBrute(preorder, inorder) {
if (preorder.length === 0) return null;
const rootVal = preorder[0];
const root = new TreeNode(rootVal);
const rootIndex = inorder.indexOf(rootVal);
const leftInorder = inorder.slice(0, rootIndex);
const rightInorder = inorder.slice(rootIndex + 1);
const leftPreorder = preorder.slice(1, 1 + leftInorder.length);
const rightPreorder = preorder.slice(1 + leftInorder.length);
root.left = buildTreeBrute(leftPreorder, leftInorder);
root.right = buildTreeBrute(rightPreorder, rightInorder);
return root;
}Optimal Solution:
// Time: O(n), Space: O(n)
function buildTree(preorder, inorder) {
const inorderMap = new Map();
for (let i = 0; i < inorder.length; i++) {
inorderMap.set(inorder[i], i);
}
let preIndex = 0;
function helper(left, right) {
if (left > right) return null;
const rootVal = preorder[preIndex++];
const root = new TreeNode(rootVal);
const inIndex = inorderMap.get(rootVal);
root.left = helper(left, inIndex - 1);
root.right = helper(inIndex + 1, right);
return root;
}
return helper(0, inorder.length - 1);
}Problem: Check if a tree is a valid BST.
Brute Force Solution:
// Time: O(n²), Space: O(h)
function isValidBSTBrute(root) {
function getMax(node) {
if (!node) return -Infinity;
return Math.max(node.val, getMax(node.left), getMax(node.right));
}
function getMin(node) {
if (!node) return Infinity;
return Math.min(node.val, getMin(node.left), getMin(node.right));
}
function helper(node) {
if (!node) return true;
const leftMax = getMax(node.left);
const rightMin = getMin(node.right);
if (leftMax >= node.val || rightMin <= node.val) {
return false;
}
return helper(node.left) && helper(node.right);
}
return helper(root);
}Optimal Solution:
// Time: O(n), Space: O(h)
function isValidBST(root) {
function validate(node, min, max) {
if (!node) return true;
if (node.val <= min || node.val >= max) {
return false;
}
return validate(node.left, min, node.val) &&
validate(node.right, node.val, max);
}
return validate(root, -Infinity, Infinity);
}Problem: Find the kth smallest element in a BST.
Brute Force Solution:
// Time: O(n), Space: O(n)
function kthSmallestBrute(root, k) {
const values = [];
function inorder(node) {
if (!node) return;
inorder(node.left);
values.push(node.val);
inorder(node.right);
}
inorder(root);
return values[k - 1];
}Optimal Solution:
// Time: O(h + k), Space: O(h)
function kthSmallest(root, k) {
let count = 0;
let result = null;
function inorder(node) {
if (!node || result !== null) return;
inorder(node.left);
count++;
if (count === k) {
result = node.val;
return;
}
inorder(node.right);
}
inorder(root);
return result;
}Problem: Find the lowest common ancestor in a BST.
Brute Force Solution:
// Time: O(n), Space: O(n)
function lowestCommonAncestorBrute(root, p, q) {
function findPath(node, target, path) {
if (!node) return false;
path.push(node);
if (node === target) return true;
if (findPath(node.left, target, path) ||
findPath(node.right, target, path)) {
return true;
}
path.pop();
return false;
}
const pathP = [];
const pathQ = [];
findPath(root, p, pathP);
findPath(root, q, pathQ);
let lca = null;
for (let i = 0; i < Math.min(pathP.length, pathQ.length); i++) {
if (pathP[i] === pathQ[i]) {
lca = pathP[i];
} else {
break;
}
}
return lca;
}Optimal Solution:
// Time: O(h), Space: O(1)
function lowestCommonAncestor(root, p, q) {
let current = root;
while (current) {
if (p.val < current.val && q.val < current.val) {
current = current.left;
} else if (p.val > current.val && q.val > current.val) {
current = current.right;
} else {
return current;
}
}
return null;
}Problem: Implement a trie with insert, search, and startsWith methods.
Optimal Solution:
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// Time: O(m), Space: O(m) where m is key length
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEndOfWord = true;
}
// Time: O(m), Space: O(1)
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return node.isEndOfWord;
}
// Time: O(m), Space: O(1)
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children[char]) {
return false;
}
node = node.children[char];
}
return true;
}
}Problem: Design a data structure that supports adding words and searching with '.' wildcard.
Optimal Solution:
class WordDictionary {
constructor() {
this.root = {};
}
// Time: O(m), Space: O(m)
addWord(word) {
let node = this.root;
for (let char of word) {
if (!node[char]) {
node[char] = {};
}
node = node[char];
}
node.isEnd = true;
}
// Time: O(m * 26^k) worst case, Space: O(m)
search(word) {
function dfs(index, node) {
if (index === word.length) {
return node.isEnd === true;
}
const char = word[index];
if (char === '.') {
for (let key in node) {
if (key !== 'isEnd' && dfs(index + 1, node[key])) {
return true;
}
}
return false;
} else {
if (!node[char]) return false;
return dfs(index + 1, node[char]);
}
}
return dfs(0, this.root);
}
}Problem: Find all words from a dictionary in a 2D board.
Brute Force Solution:
// Time: O(m * n * 4^L * k), Space: O(L)
function findWordsBrute(board, words) {
const result = new Set();
function exist(word) {
const m = board.length;
const n = board[0].length;
function dfs(i, j, index) {
if (index === word.length) return true;
if (i < 0 || j < 0 || i >= m || j >= n ||
board[i][j] !== word[index]) {
return false;
}
const temp = board[i][j];
board[i][j] = '#';
const found = dfs(i + 1, j, index + 1) ||
dfs(i - 1, j, index + 1) ||
dfs(i, j + 1, index + 1) ||
dfs(i, j - 1, index + 1);
board[i][j] = temp;
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;
}
for (let word of words) {
if (exist(word)) {
result.add(word);
}
}
return Array.from(result);
}Optimal Solution:
// Time: O(m * n * 4^L), Space: O(t) where t is trie size
function findWords(board, words) {
const result = new Set();
const m = board.length;
const n = board[0].length;
// Build Trie
const root = {};
for (let word of words) {
let node = root;
for (let char of word) {
if (!node[char]) {
node[char] = {};
}
node = node[char];
}
node.word = word;
}
function dfs(i, j, node) {
if (node.word) {
result.add(node.word);
}
if (i < 0 || j < 0 || i >= m || j >= n ||
board[i][j] === '#' || !node[board[i][j]]) {
return;
}
const char = board[i][j];
board[i][j] = '#';
dfs(i + 1, j, node[char]);
dfs(i - 1, j, node[char]);
dfs(i, j + 1, node[char]);
dfs(i, j - 1, node[char]);
board[i][j] = char;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
dfs(i, j, root);
}
}
return Array.from(result);
}Problem: Find the k most frequent elements.
Brute Force Solution:
// Time: O(n log n), Space: O(n)
function topKFrequentBrute(nums, k) {
const count = new Map();
for (let num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
const sorted = Array.from(count.entries())
.sort((a, b) => b[1] - a[1]);
return sorted.slice(0, k).map(x => x[0]);
}Optimal Solution:
// Time: O(n), Space: O(n)
function topKFrequent(nums, k) {
const count = new Map();
for (let num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
// Bucket sort
const buckets = Array(nums.length + 1).fill(0).map(() => []);
for (let [num, freq] of count) {
buckets[freq].push(num);
}
const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
result.push(...buckets[i]);
}
return result.slice(0, k);
}
// Alternative with Min Heap: O(n log k)
function topKFrequentHeap(nums, k) {
const count = new Map();
for (let num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
const heap = [];
for (let [num, freq] of count) {
heap.push([freq, num]);
if (heap.length > k) {
heap.sort((a, b) => a[0] - b[0]);
heap.shift();
}
}
return heap.map(x => x[1]);
}Problem: Design a data structure that supports adding numbers and finding the median.
Brute Force Solution:
// Time: addNum O(1), findMedian O(n log n), Space: O(n)
class MedianFinderBrute {
constructor() {
this.nums = [];
}
addNum(num) {
this.nums.push(num);
}
findMedian() {
const sorted = [...this.nums].sort((a, b) => a - b);
const n = sorted.length;
if (n % 2 === 1) {
return sorted[Math.floor(n / 2)];
} else {
return (sorted[n / 2 - 1] + sorted[n / 2]) / 2;
}
}
}Optimal Solution:
// Time: addNum O(log n), findMedian O(1), Space: O(n)
class MedianFinder {
constructor() {
this.small = []; // max heap (inverted min heap)
this.large = []; // min heap
}
addNum(num) {
// Add to small heap (max heap)
this.small.push(-num);
this.small.sort((a, b) => a - b);
// Balance: move largest from small to large
if (this.small.length > 0 && this.large.length > 0 &&
-this.small[0] > this.large[0]) {
this.large.push(-this.small.shift());
this.large.sort((a, b) => a - b);
}
// Ensure small has at most 1 more element than large
if (this.small.length > this.large.length + 1) {
this.large.push(-this.small.shift());
this.large.sort((a, b) => a - b);
}
if (this.large.length > this.small.length) {
this.small.push(-this.large.shift());
this.small.sort((a, b) => a - b);
}
}
findMedian() {
if (this.small.length > this.large.length) {
return -this.small[0];
}
return (-this.small[0] + this.large[0]) / 2;
}
}This comprehensive guide covers 75+ LeetCode problems organized by topic with both brute force and optimal solutions in JavaScript. Each solution includes:
- Time Complexity: Big O notation for time
- Space Complexity: Big O notation for space
- Clear Code: Well-commented JavaScript implementations
- Progressive Difficulty: From brute force to optimal approaches
Key Patterns Covered:
- Two Pointers
- Sliding Window
- Binary Search
- Dynamic Programming
- Backtracking
- BFS/DFS
- Trie
- Heap/Priority Queue
- Union Find
- Bit Manipulation
Practice Tips:
- Start with brute force to understand the problem
- Identify bottlenecks and optimize
- Practice explaining your approach
- Focus on edge cases
- Master the underlying patterns
Good luck with your interview preparation! 🚀 }
**Optimal Solution:**
```javascript
// Time: O(number of 1 bits), Space: O(1)
function hammingWeight(n) {
let count = 0;
while (n !== 0) {
n &= (n - 1); // Removes the rightmost 1 bit
count++;
}
return count;
}
Problem: For every number from 0 to n, count the number of 1's in their binary representation.
Brute Force Solution:
// Time: O(n * 32), Space: O(n)
function countBitsBrute(n) {
const result = [];
for (let i = 0; i <= n; i++) {
let count = 0;
let num = i;
while (num !== 0) {
count += num & 1;
num >>= 1;
}
result.push(count);
}
return result;
}Optimal Solution:
// Time: O(n), Space: O(n)
function countBits(n) {
const result = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
result[i] = result[i >> 1] + (i & 1);
}
return result;
}Problem: Find the missing number in an array containing n distinct numbers from 0 to n.
Brute Force Solution:
// Time: O(n²), Space: O(1)
function missingNumberBrute(nums) {
const n = nums.length;
for (let i = 0; i <= n; i++) {
let found = false;
for (let num of nums) {
if (num === i) {
found = true;
break;
}
}
if (!found) return i;
}
return -1;
}Optimal Solution:
// Time: O(n), Space: O(1)
function missingNumber(nums) {
const n = nums.length;
let expectedSum = (n * (n + 1)) / 2;
let actualSum = nums.reduce((sum, num) => sum + num, 0);
return expectedSum - actualSum;
}
// Alternative using XOR
function missingNumberXOR(nums) {
let result = nums.length;
for (let i = 0; i < nums.length; i++) {
result ^= i ^ nums[i];
}
return result;
}Problem: Reverse bits of a 32-bit unsigned integer.
Brute Force Solution:
// Time: O(32), Space: O(1)
function reverseBitsBrute(n) {
let result = 0;
for (let i = 0; i < 32; i++) {
const bit = (n >> i) & 1;
result |= (bit << (31 - i));
}
return result >>> 0; // Unsigned right shift
}Optimal Solution:
// Time: O(32), Space: O(1)
function reverseBits(n) {
let result = 0;
for (let i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>= 1;
}
return result >>> 0;
}Problem: Count ways to climb n stairs (1 or 2 steps at a time).
Brute Force Solution (Recursion):
// Time: O(2^n), Space: O(n)
function climbStairsBrute(n) {
if (n <= 2) return n;
return climbStairsBrute(n - 1) + climbStairsBrute(n - 2);
}Optimal Solution:
// Time: O(n), Space: O(1)
function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1;
let prev1 = 2;
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}Problem: Find minimum number of coins to make amount.
Brute Force Solution (Recursion):
// Time: O(amount^n), Space: O(amount)
function coinChangeBrute(coins, amount) {
if (amount === 0) return 0;
if (amount < 0) return -1;
let minCoins = Infinity;
for (let coin of coins) {
const result = coinChangeBrute(coins, amount - coin);
if (result >= 0) {
minCoins = Math.min(minCoins, result + 1);
}
}
return minCoins === Infinity ? -1 : minCoins;
}Optimal Solution:
// Time: O(amount * n), Space: O(amount)
function coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (let coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}Problem: Find the length of the longest increasing subsequence.
Brute Force Solution:
// Time: O(2^n), Space: O(n)
function lengthOfLISBrute(nums) {
function helper(index, prev) {
if (index === nums.length) return 0;
let exclude = helper(index + 1, prev);
let include = 0;
if (prev === -1 || nums[index] > nums[prev]) {
include = 1 + helper(index + 1, index);
}
return Math.max(include, exclude);
}
return helper(0, -1);
}Optimal Solution:
// Time: O(n²), Space: O(n)
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length).fill(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);
}
}
}
return Math.max(...dp);
}
// More optimal with binary search: O(n log n)
function lengthOfLISOptimal(nums) {
const tails = [];
for (let num of nums) {
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
tails[left] = num;
}
return tails.length;
}Problem: Find the length of the longest common subsequence between two strings.
Brute Force Solution:
// Time: O(2^(m+n)), Space: O(m+n)
function longestCommonSubsequenceBrute(text1, text2) {
function helper(i, j) {
if (i === text1.length || j === text2.length) return 0;
if (text1[i] === text2[j]) {
return 1 + helper(i + 1, j + 1);
}
return Math.max(helper(i + 1, j), helper(i, j + 1));
}
return helper(0, 0);
}Optimal Solution:
// Time: O(m * n), Space: O(m * n)
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array(m + 1).fill(0).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] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}Problem: Determine if string can be segmented into words from dictionary.
Brute Force Solution:
// Time: O(2^n), Space: O(n)
function wordBreakBrute(s, wordDict) {
function helper(start) {
if (start === s.length) return true;
for (let end = start + 1; end <= s.length; end++) {
const word = s.substring(start, end);
if (wordDict.includes(word) && helper(end)) {
return true;
}
}
return false;
}
return helper(0);
}Optimal Solution:
// Time: O(n² * m), Space: O(n)
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
}Problem: Find all unique combinations that sum to target.
Brute Force Solution:
// Time: O(2^n), Space: O(target/min)
function combinationSumBrute(candidates, target) {
const result = [];
function backtrack(start, current, sum) {
if (sum === target) {
result.push([...current]);
return;
}
if (sum > target) return;
for (let i = start; i < candidates.length; i++) {
current.push(candidates[i]);
backtrack(i, current, sum + candidates[i]);
current.pop();
}
}
backtrack(0, [], 0);
return result;
}Optimal Solution:
// Time: O(2^(target/min)), Space: O(target/min)
function combinationSum(candidates, target) {
const result = [];
candidates.sort((a, b) => a - b);
function backtrack(start, current, sum) {
if (sum === target) {
result.push([...current]);
return;
}
if (sum > target) return;
for (let i = start; i < candidates.length; i++) {
if (sum + candidates[i] > target) break; // Optimization
current.push(candidates[i]);
backtrack(i, current, sum + candidates[i]);
current.pop();
}
}
backtrack(0, [], 0);
return result;
}Problem: Rob houses to maximize money without robbing adjacent houses.
Brute Force Solution:
// Time: O(2^n), Space: O(n)
function robBrute(nums) {
function helper(index) {
if (index >= nums.length) return 0;
// Rob current house or skip it
const rob = nums[index] + helper(index + 2);
const skip = helper(index + 1);
return Math.max(rob, skip);
}
return helper(0);
}Optimal Solution:
// Time: O(n), Space: O(1)
function rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
let prev2 = 0;
let prev1 = 0;
for (let num of nums) {
const current = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = current;
}
return prev1;
}Problem: Rob houses in a circle (first and last are adjacent).
Brute Force Solution:
// Time: O(2^n), Space: O(n)
function robIIBrute(nums) {
if (nums.length === 1) return nums[0];
function helper(start, end, index) {
if (index > end) return 0;
const rob = nums[index] + helper(start, end, index + 2);
const skip = helper(start, end, index + 1);
return Math.max(rob, skip);
}
// Either rob first house (skip last) or rob last house (skip first)
const robFirst = helper(0, nums.length - 2, 0);
const robLast = helper(1, nums.length - 1, 1);
return Math.max(robFirst, robLast);
}Optimal Solution:
// Time: O(n), Space: O(1)
function robII(nums) {
if (nums.length === 1) return nums[0];
if (nums.length === 2) return Math.max(nums[0], nums[1]);
function robLinear(start, end) {
let prev2 = 0;
let prev1 = 0;
for (let i = start; i <= end; i++) {
const current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
return Math.max(robLinear(0, nums.length - 2), robLinear(1, nums.length - 1));
}Problem: Count ways to decode a string of digits (A=1, B=2, ..., Z=26).
Brute Force Solution:
// Time: O(2^n), Space: O(n)
function numDecodingsBrute(s) {
function helper(index) {
if (index === s.length) return 1;
if (s[index] === '0') return 0;
let ways = helper(index + 1);
if (index + 1 < s.length) {
const twoDigit = parseInt(s.substring(index, index + 2));
if (twoDigit <= 26) {
ways += helper(index + 2);
}
}
return ways;
}
return helper(0);
}Optimal Solution:
// Time: O(n), Space: O(n)
function numDecodings(s) {
if (s[0] === '0') return 0;
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
const oneDigit = parseInt(s[i - 1]);
const twoDigits = parseInt(s.substring(i - 2, i));
if (oneDigit >= 1) {
dp[i] += dp[i - 1];
}
if (twoDigits >= 10 && twoDigits <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}Problem: Count paths from top-left to bottom-right in a grid (only move right or down).
Brute Force Solution:
// Time: O(2^(m+n)), Space: O(m+n)
function uniquePathsBrute(m, n) {
function helper(i, j) {
if (i === m - 1 && j === n - 1) return 1;
if (i >= m || j >= n) return 0;
return helper(i + 1, j) + helper(i, j + 1);
}
return helper(0, 0);
}Optimal Solution:
// Time: O(m * n), Space: O(m * n)
function uniquePaths(m, n) {
const dp = Array(m).fill(0).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];
}
// Space optimized: O(n)
function uniquePathsOptimal(m, n) {
const dp = new 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];
}Problem: Determine if you can reach the last index.
Brute Force Solution:
// Time: O(2^n), Space: O(n)
function canJumpBrute(nums) {
function helper(index) {
if (index === nums.length - 1) return true;
if (index >= nums.length) return false;
const maxJump = Math.min(index + nums[index], nums.length - 1);
for (let i = index + 1; i <= maxJump; i++) {
if (helper(i)) return true;
}
return false;
}
return helper(0);
}Optimal Solution:
// Time: O(n), Space: O(1)
function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}Problem: Deep clone an undirected graph.
Brute Force Solution:
// Time: O(n + e), Space: O(n)
function cloneGraphBrute(node) {
if (!node) return null;
const visited = new Map();
function clone(node) {
if (visited.has(node.val)) {
return visited.get(node.val);
}
const newNode = new Node(node.val);
visited.set(node.val, newNode);
for (let neighbor of node.neighbors) {
newNode.neighbors.push(clone(neighbor));
}
return newNode;
}
return clone(node);
}Optimal Solution:
// Time: O(n + e), Space: O(n)
function cloneGraph(node) {
if (!node) return null;
const visited = new Map();
function dfs(node) {
if (visited.has(node)) {
return visited.get(node);
}
const clone = new Node(node.val);
visited.set(node, clone);
for (let neighbor of node.neighbors) {
clone.neighbors.push(dfs(neighbor));
}
return clone;
}
return dfs(node);
}Problem: Determine if you can finish all courses (detect cycle in directed graph).
Brute Force Solution:
// Time: O(n * e), Space: O(n + e)
function canFinishBrute(numCourses, prerequisites) {
const graph = Array(numCourses).fill(0).map(() => []);
for (let [course, prereq] of prerequisites) {
graph[prereq].push(course);
}
function hasCycle(node, visited, path) {
if (path.has(node)) return true;
if (visited.has(node)) return false;
visited.add(node);
path.add(node);
for (let neighbor of graph[node]) {
if (hasCycle(neighbor, visited, path)) {
return true;
}
}
path.delete(node);
return false;
}
const visited = new Set();
for (let i = 0; i < numCourses; i++) {
if (hasCycle(i, visited, new Set())) {
return false;
}
}
return true;
}Optimal Solution:
// Time: O(n + e), Space: O(n + e)
function canFinish(numCourses, prerequisites) {
const graph = Array(numCourses).fill(0).map(() => []);
for (let [course, prereq] of prerequisites) {
graph[prereq].push(course);
}
const visiting = new Set();
const visited = new Set();
function hasCycle(node) {
if (visiting.has(node)) return true;
if (visited.has(node)) return false;
visiting.add(node);
for (let neighbor of graph[node]) {
if (hasCycle(neighbor)) return true;
}
visiting.delete(node);
visited.add(node);
return false;
}
for (let i = 0; i < numCourses; i++) {
if (hasCycle(i)) return false;
}
return true;
}Problem: Find cells where water can flow to both Pacific and Atlantic oceans.
Brute Force Solution:
// Time: O(m * n * m * n), Space: O(m * n)
function pacificAtlanticBrute(heights) {
const m = heights.length;
const n = heights[0].length;
const result = [];
function canReachOcean(i, j, ocean) {
const visited = new Set();
function dfs(r, c, prevHeight) {
const key = `${r},${c}`;
if (visited.has(key)) return false;
if (r < 0 || c < 0 || r >= m || c >= n) return false;
if (heights[r][c] > prevHeight) return false;
if (ocean === 'pacific' && (r === 0 || c === 0)) return true;
if (ocean === 'atlantic' && (r === m - 1 || c === n - 1)) return true;
visited.add(key);
return dfs(r + 1, c, heights[r][c]) ||
dfs(r - 1, c, heights[r][c]) ||
dfs(r, c + 1, heights[r][c]) ||
dfs(r, c - 1, heights[r][c]);
}
return dfs(i, j, Infinity);
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (canReachOcean(i, j, 'pacific') && canReachOcean(i, j, 'atlantic')) {
result.push([i, j]);
}
}
}
return result;
}Optimal Solution:
// Time: O(m * n), Space: O(m * n)
function pacificAtlantic(heights) {
const m = heights.length;
const n = heights[0].length;
const pacific = Array(m).fill(0).map(() => Array(n).fill(false));
const atlantic = Array(m).fill(0).map(() => Array(n).fill(false));
function dfs(r, c, ocean, prevHeight) {
if (r < 0 || c < 0 || r >= m || c >= n) return;
if (ocean[r][c]) return;
if (heights[r][c] < prevHeight) return;
ocean[r][c] = true;
dfs(r + 1, c, ocean, heights[r][c]);
dfs(r - 1, c, ocean, heights[r][c]);
dfs(r, c + 1, ocean, heights[r][c]);
dfs(r, c - 1, ocean, heights[r][c]);
}
// Start from Pacific edges
for (let i = 0; i < m; i++) {
dfs(i, 0, pacific, heights[i][0]);
dfs(i, n - 1, atlantic, heights[i][n - 1]);
}
for (let j = 0; j < n; j++) {
dfs(0, j, pacific, heights[0][j]);
dfs(m - 1, j, atlantic, heights[m - 1][j]);
}
const result = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.push([i, j]);
}
}
}
return result;
}Problem: Count the number of islands in a 2D grid.
Brute Force Solution:
// Time: O(m * n * m * n), Space: O(m * n)
function numIslandsBrute(grid) {
const m = grid.length;
const n = grid[0].length;
const visited = Array(m).fill(0).map(() => Array(n).fill(false));
let count = 0;
function bfs(i, j) {
const queue = [[i, j]];
visited[i][j] = true;
while (queue.length > 0) {
const [r, c] = queue.shift();
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
for (let [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nc >= 0 && nr < m && nc < n &&
grid[nr][nc] === '1' && !visited[nr][nc]) {
visited[nr][nc] = true;
queue.push([nr, nc]);
}
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1' && !visited[i][j]) {
bfs(i, j);
count++;
}
}
}
return count;
}Optimal Solution:
// Time: O(m * n), Space: O(m * n)
function numIslands(grid) {
const m = grid.length;
const n = grid[0].length;
let count = 0;
function dfs(i, j) {
if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') {
return;
}
grid[i][j] = '0'; // Mark as visited
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') {
dfs(i, j);
count++;
}
}
}
return count;
}Problem: Find the length of the longest consecutive elements sequence.
Brute Force Solution:
// Time: O(n³), Space: O(1)
function longestConsecutiveBrute(nums) {
let maxLen = 0;
for (let num of nums) {
let currentNum = num;
let currentLen = 1;
while (nums.includes(currentNum + 1)) {
currentNum++;
currentLen++;
}
maxLen = Math.max(maxLen, currentLen);
}
return maxLen;
}Optimal Solution:
// Time: O(n), Space: O(n)
function longestConsecutive(nums) {
const numSet = new Set(nums);
let maxLen = 0;
for (let num of numSet) {
// Only start counting if it's the beginning of a sequence
if (!numSet.has(num - 1)) {
let currentNum = num;
let currentLen = 1;
while (numSet.has(currentNum + 1)) {
currentNum++;
currentLen++;
}
maxLen = Math.max(maxLen, currentLen);
}
}
return maxLen;
}Problem: Derive the order of characters in an alien language (Premium).
Optimal Solution:
// Time: O(C), Space: O(1) where C is total content in words
function alienOrder(words) {
const graph = new Map();
const inDegree = new Map();
// Initialize graph
for (let word of words) {
for (let char of word) {
graph.set(char, new Set());
inDegree.set(char, 0);
}
}
// Build graph
for (let i = 0; i < words.length - 1; i++) {
const word1 = words[i];
const word2 = words[i + 1];
const minLen = Math.min(word1.length, word2.length);
// Check for invalid case
if (word1.length > word2.length && word1.startsWith(word2)) {
return "";
}
for (let j = 0; j < minLen; j++) {
if (word1[j] !== word2[j]) {
if (!graph.get(word1[j]).has(word2[j])) {
graph.get(word1[j]).add(word2[j]);
inDegree.set(word2[j], inDegree.get(word2[j]) + 1);
}
break;
}
}
}
// Topological sort
const queue = [];
for (let [char, degree] of inDegree) {
if (degree === 0) queue.push(char);
}
let result = "";
while (queue.length > 0) {
const char = queue.shift();
result += char;
for (let neighbor of graph.get(char)) {
inDegree.set(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) === 0) {
queue.push(neighbor);
}
}
}
return result.length === inDegree.size ? result : "";
}Problem: Check if graph is a valid tree (Premium).
Optimal Solution:
// Time: O(n + e), Space: O(n + e)
function validTree(n, edges) {
if (edges.length !== n - 1) return false;
const graph = Array(n).fill(0).map(() => []);
for (let [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Set();
function dfs(node, parent) {
visited.add(node);
for (let neighbor of graph[node]) {
if (neighbor === parent) continue;
if (visited.has(neighbor)) return false;
if (!dfs(neighbor, node)) return false;
}
return true;
}
return dfs(0, -1) && visited.size === n;
}Problem: Count connected components (Premium).
Optimal Solution:
// Time: O(n + e), Space: O(n + e)
function countComponents(n, edges) {
const graph = Array(n).fill(0).map(() => []);
for (let [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
const visited = new Set();
let count = 0;
function dfs(node) {
visited.add(node);
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
dfs(neighbor);
}
}
}
for (let i = 0; i < n; i++) {
if (!visited.has(i)) {
dfs(i);
count++;
}
}
return count;
}Problem: Insert a new interval and merge if necessary.
Brute Force Solution:
// Time: O(n²), Space: O(n)
function insertBrute(intervals, newInterval) {
intervals.push(newInterval);
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
const current = intervals[i];
if (current[0] <= last[1]) {
last[1] = Math.max(last[1], current[1]);
} else {
merged.push(current);
}
}
return merged;
}Optimal Solution:
// Time: O(n), Space: O(n)
function insert(intervals, newInterval) {
const result = [];
let i = 0;
// Add all intervals before newInterval
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Merge overlapping intervals
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// Add remaining intervals
while (i < intervals.length) {
result.push(intervals[i]);
i++;
}
return result;
}Problem: Merge all overlapping intervals.
Brute Force Solution:
// Time: O(n² log n), Space: O(n)
function mergeBrute(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let changed = true;
while (changed) {
changed = false;
for (let i = 0; i < intervals.length - 1; i++) {
if (intervals[i][1] >= intervals[i + 1][0]) {
intervals[i][1] = Math.max(intervals[i][1], intervals[i + 1][1]);
intervals.splice(i + 1, 1);
changed = true;
break;
}
}
}
return intervals;
}Optimal Solution:
// Time: O(n log n), Space: O(n)
function merge(intervals) {
if (intervals.length <= 1) return intervals;
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
const current = intervals[i];
if (current[0] <= last[1]) {
last[1] = Math.max(last[1], current[1]);
} else {
merged.push(current);
}
}
return merged;
}Problem: Find minimum number of intervals to remove to make rest non-overlapping.
Brute Force Solution:
// Time: O(2^n), Space: O(n)
function eraseOverlapIntervalsBrute(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
function helper(index, prev) {
if (index === intervals.length) return 0;
// Remove current interval
let remove = 1 + helper(index + 1, prev);
// Keep current interval if it doesn't overlap
let keep = Infinity;
if (prev === -1 || intervals[index][0] >= intervals[prev][1]) {
keep = helper(index + 1, index);
}
return Math.min(remove, keep);
}
return helper(0, -1);
}Optimal Solution:
// Time: O(n log n), Space: O(1)
function eraseOverlapIntervals(intervals) {
if (intervals.length === 0) return 0;
intervals.sort((a, b) => a[1] - b[1]);
let count = 0;
let end = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) {
count++;
} else {
end = intervals[i][1];
}
}
return count;
}Problem: Check if person can attend all meetings (Premium).
Optimal Solution:
// Time: O(n log n), Space: O(1)
function canAttendMeetings(intervals) {
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;
}Problem: Find minimum number of conference rooms required (Premium).
Optimal Solution:
// Time: O(n log n), Space: O(n)
function minMeetingRooms(intervals) {
const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
let rooms = 0;
let maxRooms = 0;
let i = 0, j = 0;
while (i < starts.length) {
if (starts[i] < ends[j]) {
rooms++;
maxRooms = Math.max(maxRooms, rooms);
i++;
} else {
rooms--;
j++;
}
}
return maxRooms;
}Problem: Reverse a singly linked list.
Brute Force Solution:
// Time: O(n), Space: O(n)
function reverseListBrute(head) {
const values = [];
let current = head;
while (current) {
values.push(current.val);
current = current.next;
}
current = head;
while (current) {
current.val = values.pop();
current = current.next;
}
return head;
}Optimal Solution:
// Time: O(n), Space: O(1)
function reverseList(head) {
let prev = null;
let current = head;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}Problem: Detect if linked list has a cycle.
Brute Force Solution:
// Time: O(n), Space: O(n)
function hasCycleBrute(head) {
const seen = new Set();
let current = head;
while (current) {
if (seen.has(current)) return true;
seen.add(current);
current = current.next;
}
return false;
}Optimal Solution:
// Time: O(n), Space: O(1)
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}Problem: Merge two sorted linked lists.
Brute Force Solution:
// Time: O(n + m), Space: O(n + m)
function mergeTwoListsBrute(l1, l2) {
const values = [];
while (l1) {
values.push(l1.val);
l1 = l1.next;
}
while (l2) {
values.push(l2.val);
l2 = l2.next;
}
values.sort((a, b) => a - b);
const dummy = new ListNode(0);
let current = dummy;
for (let val of values) {
current.next = new ListNode(val);
current = current.next;
}
return dummy.next;
}Optimal Solution:
// Time: O(n + m), Space: O(1)
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}Problem: Merge k sorted linked lists.
Brute Force Solution:
// Time: O(nk log nk), Space: O(nk)
function mergeKListsBrute(lists) {
const values = [];
for (let list of lists) {
while (list) {
values.push(list.val);
list = list.next;
}
}
values.sort((a, b) => a - b);
const dummy = new ListNode(0);
let current = dummy;
for (let val of values) {
current.next = new ListNode(val);
current = current.next;
}
return dummy.next;
}Optimal Solution:
// Time: O(nk log k), Space: O(k)
function mergeKLists(lists) {
if (!lists || lists.length === 0) return null;
while (lists.length > 1) {
const mergedLists = [];
for (let i = 0; i < lists.length; i += 2) {
const l1 = lists[i];
const l2 = i + 1 < lists.length ? lists[i + 1] : null;
mergedLists.push(mergeTwoLists(l1, l2));
}
lists = mergedLists;
}
return lists[0];
}
function mergeTwoLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}Problem: Remove the nth node from the end of the list.
Brute Force Solution:
// Time: O(n), Space: O(1)
function removeNthFromEndBrute(head, n) {
// First pass: count nodes
let length = 0;
let current = head;
while (current) {
length++;
current = current.next;
}
// Edge case: remove first node
if (length === n) return head.next;
// Second pass: remove node
current = head;
for (let i = 0; i < length - n - 1; i++) {
current = current.next;
}
current.next = current.next.next;
return head;
}Optimal Solution:
// Time: O(n), Space: O(1)
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0);
dummy.next = head;
let slow = dummy;
let fast = dummy;
// Move fast n+1 steps ahead
for (let i = 0; i <= n; i++) {
fast = fast.next;
}
// Move both until fast reaches end
while (fast) {
slow = slow.next;
fast = fast.next;
}
// Remove node
slow.next = slow.next.next;
return dummy.next;
}Problem: Reorder list to L0→Ln→L1→Ln-1→L2→Ln-2→...
Brute Force Solution:
// Time: O(n), Space: O(n)
function reorderListBrute(head) {
const nodes = [];
let current = head;
while (current) {
nodes.push(current);
current = current.next;
}
let left = 0;
let right = nodes.length - 1;
while (left < right) {
nodes[left].next = nodes[right];
left++;
if (left === right) break;
nodes[right].next = nodes[left];
right--;
}
nodes[left].next = null;
}Optimal Solution:
// Time: O(n), Space: O(1)
function reorderList(head) {
if (!head || !head.next) return;
// Find middle
let slow = head;
let fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse second half
let prev = null;
let current = slow.next;
slow.next = null;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
// Merge two halves
let first = head;
let second = prev;
while (second) {
const temp1 = first.next;
const temp2 = second.next;
first.next = second;
second.next = temp1;
first = temp1;
second = temp2;
}
}Problem: Set entire row and column to 0 if element is 0.
Brute Force Solution:
// Time: O(m * n * (m + n)), Space: O(m * n)
function setZeroesBrute(matrix) {
const m = matrix.length;
const n = matrix[0].length;
const copy = matrix.map(row => [...row]);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (copy[i][j] === 0) {
for (let k = 0; k < n; k++) matrix[i][k] = 0;
for (let k = 0; k < m; k++) matrix[k][j] = 0;
}
}
}
}Optimal Solution:
// Time: O(m * n), Space: O(1)
function setZeroes(matrix) {
const m = matrix.length;
const n = matrix[0].length;
let firstRowZero = false;
let firstColZero = false;
// Check if first row/col should be zero
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) firstRowZero = true;
}
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) firstColZero = true;
}
// Use first row/col as markers
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Set zeros based on markers
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
// Handle first row/col
if (firstRowZero) {
for (let j = 0; j < n; j++) matrix[0][j] = 0;
}
if (firstColZero) {
for (let i = 0; i < m; i++) matrix[i][0] = 0;
}
}Problem: Return all elements in spiral order.
Brute Force Solution:
// Time: O(m * n), Space: O(m * n)
function spiralOrderBrute(matrix) {
const result = [];
const visited = Array(matrix.length).fill(0).map(() =>
Array(matrix[0].length).fill(false)
);
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
let dir = 0;
let r = 0, c = 0;
for (let i = 0; i < matrix.length * matrix[0].length; i++) {
result.push(matrix[r][c]);
visited[r][c] = true;
const nr = r + directions[dir][0];
const nc = c + directions[dir][1];
if (nr < 0 || nc < 0 || nr >= matrix.length ||
nc >= matrix[0].length || visited[nr][nc]) {
dir = (dir + 1) % 4;
}
r += directions[dir][0];
c += directions[dir][1];
}
return result;
}Optimal Solution:
// Time: O(m * n), Space: O(1)
function spiralOrder(matrix) {
const result = [];
let top = 0;
let bottom = matrix.length - 1;
let left = 0;
let right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// Traverse right
for (let j = left; j <= right; j++) {
result.push(matrix[top][j]);
}
top++;
// Traverse down
for (let i = top; i <= bottom; i++) {
result.push(matrix[i][right]);
}
right--;
// Traverse left
if (top <= bottom) {
for (let j = right; j >= left; j--) {
result.push(matrix[bottom][j]);
}
bottom--;
}
// Traverse up
if (left <= right) {
for (let i = bottom; i >= top; i--) {
result.push(matrix[i][left]);
}
left++;
}
}
return result;
}Problem: Rotate matrix 90 degrees clockwise in-place.
Brute Force Solution:
// Time: O(n²), Space: O(n²)
function rotateBrute(matrix) {
const n = matrix.length;
const copy = matrix.map(row => [...row]);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix[j][n - 1 - i] = copy[i][j];
}
}
}Optimal Solution:
// Time: O(n²), Space: O(1)
function rotate(matrix) {
const n = matrix.length;
// Transpose
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 (let i = 0; i < n; i++) {
matrix[i].reverse();
}
}Problem: Search for a word in a 2D board.
Brute Force Solution:
// Time: O(m * n * 4^L), Space: O(L)
function existBrute(board, word) {
const m = board.length;
const n = board[0].length;
function dfs(i, j, index) {
if (index === word.length) return true;
if (i < 0 || j < 0 || i >= m || j >= n) return false;
if (board[i][j] !== word[index]) return false;
const temp = board[i][j];
board[i][j] = '#';
const found = dfs(i + 1, j, index + 1) ||
dfs(i - 1, j, index + 1) ||
dfs(i, j + 1, index + 1) ||
dfs(i, j - 1, index + 1);
board[i][j] = temp;
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;
}Optimal Solution:
// Time: O(m * n * 4^L), Space: O(L)
function exist(board, word) {
const m = board.length;
const n = board[0].length;
function dfs(i, j, index) {
if (index === word.length) return true;
if (i < 0 || j < 0 || i >= m || j >= n ||
board[i][j] !== word[index]) {
return false;
}
const temp = board[i][j];
board[i][j] = '#';
const found = dfs(i + 1, j, index + 1) ||
dfs(i - 1, j, index + 1) ||
dfs(i, j + 1, index + 1) ||
dfs(i, j - 1, index + 1);
board[i][j] = temp;
return found;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === word[0] && dfs(i, j, 0)) {
return true;
}
}
}
return false;
}Problem: Find the length of the longest substring without repeating characters.
Brute Force Solution:
// Time: O(n³), Space: O(min(n, m))
function lengthOfLongestSubstringBrute(s) {
let maxLen = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const substring = s.substring(i, j + 1);
const set = new Set(substring);
if (set.size === substring.length) {
maxLen = Math.max(maxLen, substring.length);
} else {
break;
}
}
}
return maxLen;
}Optimal Solution:
// Time: O(n), Space: O(min(n, m))
function lengthOfLongestSubstring(s) {
const map = new Map();
let maxLen = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
if (map.has(s[right])) {
left = Math.max(left, map.get(s[right]) + 1);
}
map.set(s[right], right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Problem: Find longest substring with same characters after k replacements.
Brute Force Solution:
// Time: O(n²), Space: O(1)
function characterReplacementBrute(s, k) {
let maxLen = 0;
for (let i = 0; i < s.length; i++) {
const count = new Array(26).fill(0);
let maxCount = 0;
for (let j = i; j < s.length; j++) {
count[s.charCodeAt(j) - 65]++;
maxCount = Math.max(maxCount, count[s.charCodeAt(j) - 65]);
const len = j - i + 1;
if (len - maxCount <= k) {
maxLen = Math.max(maxLen, len);
}
}
}
return maxLen;
}Optimal Solution:
// Time: O(n), Space: O(1)
function characterReplacement(s, k) {
const count = new Map();
let maxLen = 0;
let maxCount = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
count.set(s[right], (count.get(s[right]) || 0) + 1);
maxCount = Math.max(maxCount, count.get(s[right]));
while (right - left + 1 - maxCount > k) {
count.set(s[left], count.get(s[left]) - 1);
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Problem: Find minimum window in s that contains all characters of t.
Brute Force Solution:
// Time: O(n²m), Space: O(m)
function minWindowBrute(s, t) {
let minLen = Infinity;
let result = "";
function containsAll(sub, target) {
const count = new Map();
for (let char of target) {
count.set(char, (count.get(char) || 0) + 1);
}
for (let char of sub) {
if (count.has(char)) {
count.set(char, count.get(char) - 1);
}
}
for (let val of count.values()) {
if (val > 0) return false;
}
return true;
}
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const substring = s.substring(i, j + 1);
if (containsAll(substring, t) && substring.length < minLen) {
minLen = substring.length;
result = substring;
}
}
}
return result;
}Optimal Solution:
// Time: O(n + m), Space: O(m)
function minWindow(s, t) {
if (s.length < t.length) return "";
const need = new Map();
const window = new Map();
for (let char of t) {
need.set(char, (need.get(char) || 0) + 1);
}
let left = 0;
let right = 0;
let valid = 0;
let start = 0;
let minLen = Infinity;
while (right < s.length) {
const char = s[right];
right++;
if (need.has(char)) {
window.set(char, (window.get(char) || 0) + 1);
if (window.get(char) === need.get(char)) {
valid++;
}
}
while (valid === need.size) {
if (right - left < minLen) {
start = left;
minLen = right - left;
}
const leftChar = s[left];
left++;
if (need.has(leftChar)) {
if (window.get(leftChar) === need.get(leftChar)) {
valid--;
}
window.set(leftChar, window.get(leftChar) - 1);
}
}
}
return minLen === Infinity ? "" : s.substring(start, start + minLen);
}Problem: Check if two strings are anagrams.
Brute Force Solution:
// Time: O(n log n), Space: O(n)
function isAnagramBrute(s, t) {
if (s.length !== t.length) return false;
const sortedS = s.split('').sort().join('');
const sortedT = t.split('').sort().join('');
return sortedS === sortedT;
}Optimal Solution:
// Time: O(n), Space: O(1)
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
count[t.charCodeAt(i) - 97]--;
}
return count.every(c => c === 0);
}Problem: Group anagrams together.
Brute Force Solution:
// Time: O(n² * k log k), Space: O(nk)
function groupAnagramsBrute(strs) {
const result = [];
const used = new Array(strs.length).fill(false);
for (let i = 0; i < strs.length; i++) {
if (used[i]) continue;
const group = [strs[i]];
used[i] = true;
const sortedI = strs[i].split('').sort().join('');
for (let j = i + 1; j < strs.length; j++) {
if (used[j]) continue;
const sortedJ = strs[j].split('').sort().join('');
if (sortedI === sortedJ) {
group.push(strs[j]);
used[j] = true;
}
}
result.push(group);
}
return result;
}Optimal Solution:
// Time: O(n * k log k), Space: O(nk)
function groupAnagrams(strs) {
const map = new Map();
for (let str of strs) {
const key = str.split('').sort().join('');
if (!map.has(key)) {
map.set(key, []);
}
map.get(key).push(str);
}
return Array.from(map.values());
}
// Alternative with character count
function groupAnagramsCount(strs) {
const map = new Map();
for (let str of strs) {
const count = new Array(26).fill(0);
for (let char of str) {
count[char.charCodeAt(0) - 97]++;
}
const key = count.join('#');
if (!map.has(key)) {
map.set(key, []);
}
map.get(key).push(str);
}
return Array.from(map.values());
}Problem: Check if parentheses string is valid.
Brute Force Solution:
// Time: O(n²), Space: O(n)
function isValidBrute(s) {
while (s.includes('()') || s.includes('{}') || s.includes('[]')) {
s = s.replace('()', '').replace('{}', '').replace('[]', '');
}
return s.length === 0;
}Optimal Solution:
// Time: O(n), Space: O(n)
function isValid(s) {
const stack = [];
const pairs = {
')': '(',
'}': '{',
']': '['
};
for (let char of s) {
if (char === '(' || char === '{' || char === '[') {
stack.push(char);
} else {
if (stack.length === 0 || stack.pop() !== pairs[char]) {
return false;
}
}
}
return stack.length === 0;
}Problem: Check if string is a palindrome (ignoring non-alphanumeric).
Brute Force Solution:
// Time: O(n), Space: O(n)
function isPalindromeBrute(s) {
const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
const reversed = cleaned.split('').reverse().join('');
return cleaned === reversed;
}Optimal Solution:
// Time: O(n), Space: O(1)
function isPalindrome(s) {
let left = 0;
let right = s.length - 1;
function isAlphanumeric(char) {
const code = char.charCodeAt(0);
return (code >= 48 && code <= 57) || // 0-9
(code >= 65 && code <= 90) || // A-Z
(code >= 97 && code <= 122); // a-z
}
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;
}Problem: Find the longest palindromic substring.
Brute Force Solution:
// Time: O(n³), Space: O(1)
function longestPalindromeBrute(s) {
let longest = "";
function isPalindrome(str) {
let left = 0;
let right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const substring = s.substring(i, j + 1);
if (isPalindrome(substring) && substring.length > longest.length) {
longest = substring;
}
}
}
return longest;
}Optimal Solution:
// Time: O(n²), Space: O(1)
function longestPalindrome(s) {
let start = 0;
let maxLen = 0;
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
for (let i = 0; i < s.length; i++) {
const len1 = expandAroundCenter(i, i);
const len2 = expandAroundCenter(i, i + 1);
const len = Math.max(len1, len2);
if (len > maxLen) {
maxLen = len;
start = i - Math.floor((len - 1) / 2);
}
}
return s.substring(start, start + maxLen);
}Problem: Count all palindromic substrings.
Brute Force Solution:
// Time: O(n³), Space: O(1)
function countSubstringsBrute(s) {
let count = 0;
function isPalindrome(str) {
let left = 0;
let right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
if (isPalindrome(s.substring(i, j + 1))) {
count++;
}
}
}
return count;
}Optimal Solution:
// Time: O(n²), Space: O(1)
function countSubstrings(s) {
let count = 0;
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
count++;
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
expandAroundCenter(i, i); // odd length
expandAroundCenter(i, i + 1); // even length
}
return count;