Blind 75 LeetCode Problems

A comprehensive collection of 75 essential LeetCode problems for coding interviews, organized by category with JavaScript solutions and test cases.

Progress Tracking

Quick Reference

Array Problems (10/10)

Problem 1: Two Sum (Array)

Difficulty: Easy
LeetCode: Link

Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
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 [];
}

Test Cases

// Test Case 1
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

// Test Case 2
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

// Test Case 3
console.log(twoSum([3, 3], 6)); // [0, 1]

Time Complexity: O(n)
Space Complexity: O(n)

Problem 2: Contains Duplicate (Array)

Difficulty: Easy
LeetCode: Link

Description

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function containsDuplicate(nums) {
  const set = new Set(nums);
  return set.size !== nums.length;
}

Test Cases

// Test Case 1
console.log(containsDuplicate([1, 2, 3, 1])); // true

// Test Case 2
console.log(containsDuplicate([1, 2, 3, 4])); // false

// Test Case 3
console.log(containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2])); // true

Time Complexity: O(n)
Space Complexity: O(n)

Problem 3: Best Time to Buy and Sell Stock (Array)

Difficulty: Easy
LeetCode: Link

Description

You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete at most one transaction.

JavaScript Solution

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;

  for (const price of prices) {
    minPrice = Math.min(minPrice, price);
    maxProfit = Math.max(maxProfit, price - minPrice);
  }

  return maxProfit;
}

Test Cases

// Test Case 1
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5

// Test Case 2
console.log(maxProfit([7, 6, 4, 3, 1])); // 0

// Test Case 3
console.log(maxProfit([1, 2, 3, 4, 5])); // 4

Time Complexity: O(n)
Space Complexity: O(1)

Problem 4: Product of Array Except Self (Array)

Difficulty: Medium
LeetCode: Link

Description

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all elements of nums except nums[i]. The solution must be O(n) time and without division.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

  // Calculate left products
  let left = 1;
  for (let i = 0; i < n; i++) {
    result[i] = left;
    left *= nums[i];
  }

  // Calculate right products
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= right;
    right *= nums[i];
  }

  return result;
}

Test Cases

// Test Case 1
console.log(productExceptSelf([1, 2, 3, 4])); // [24, 12, 8, 6]

// Test Case 2
console.log(productExceptSelf([-1, 1, 0, -3, 3])); // [0, 0, 9, 0, 0]

// Test Case 3
console.log(productExceptSelf([1, 2, 3, 4, 5])); // [120, 60, 40, 30, 24]

Time Complexity: O(n)
Space Complexity: O(1) (excluding output array)

Problem 5: Maximum Subarray (Array)

Difficulty: Easy
LeetCode: Link

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
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;
}

Test Cases

// Test Case 1
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6

// Test Case 2
console.log(maxSubArray([1])); // 1

// Test Case 3
console.log(maxSubArray([5, 4, -1, 7, 8])); // 23

Time Complexity: O(n)
Space Complexity: O(1)

Problem 6: Maximum Product Subarray (Array)

Difficulty: Medium
LeetCode: Link

Description

Given an integer array nums, find a contiguous subarray that has the largest product, and return the product.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function maxProduct(nums) {
  let maxSoFar = nums[0];
  let minSoFar = nums[0];
  let result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const current = nums[i];
    const temp = maxSoFar;

    maxSoFar = Math.max(current, current * maxSoFar, current * minSoFar);
    minSoFar = Math.min(current, current * temp, current * minSoFar);

    result = Math.max(result, maxSoFar);
  }

  return result;
}

Test Cases

// Test Case 1
console.log(maxProduct([2, 3, -2, 4])); // 6

// Test Case 2
console.log(maxProduct([-2, 0, -1])); // 0

// Test Case 3
console.log(maxProduct([-2, 3, -4])); // 24

Time Complexity: O(n)
Space Complexity: O(1)

Problem 7: Search in Rotated Sorted Array (Array)

Difficulty: Medium
LeetCode: Link

Description

Given the sorted array nums that is rotated at an unknown pivot, and a target value, return the index if found, otherwise -1.

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
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;
    }

    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

Test Cases

// Test Case 1
console.log(search([4, 5, 6, 7, 0, 1, 2], 0)); // 4

// Test Case 2
console.log(search([4, 5, 6, 7, 0, 1, 2], 3)); // -1

// Test Case 3
console.log(search([1], 0)); // -1

Time Complexity: O(log n)
Space Complexity: O(1)

Problem 8: Find Minimum in Rotated Sorted Array (Array)

Difficulty: Medium
LeetCode: Link

Description

Given the sorted rotated array nums of distinct elements, return the minimum element.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
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];
}

Test Cases

// Test Case 1
console.log(findMin([3, 4, 5, 1, 2])); // 1

// Test Case 2
console.log(findMin([4, 5, 6, 7, 0, 1, 2])); // 0

// Test Case 3
console.log(findMin([11, 13, 15, 17])); // 11

Time Complexity: O(log n)
Space Complexity: O(1)

Problem 9: 3Sum (Array)

Difficulty: Medium
LeetCode: Link

Description

Given integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];

  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;
}

Test Cases

// Test Case 1
console.log(threeSum([-1, 0, 1, 2, -1, -4])); // [[-1, -1, 2], [-1, 0, 1]]

// Test Case 2
console.log(threeSum([0, 1, 1])); // []

// Test Case 3
console.log(threeSum([0, 0, 0, 0])); // [[0, 0, 0]]

Time Complexity: O(n^2)
Space Complexity: O(1) (excluding output)

Problem 10: Container With Most Water (Array)

Difficulty: Medium
LeetCode: Link

Description

Given array height where each element represents the height of a vertical line, find two lines that, together with the x-axis, form a container that holds the most water.

JavaScript Solution

/**
 * @param {number[]} height
 * @return {number}
 */
function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let maxArea = 0;

  while (left < right) {
    const width = right - left;
    const currentHeight = Math.min(height[left], height[right]);
    const currentArea = width * currentHeight;

    maxArea = Math.max(maxArea, currentArea);

    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return maxArea;
}

Test Cases

// Test Case 1
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49

// Test Case 2
console.log(maxArea([1, 1])); // 1

// Test Case 3
console.log(maxArea([4, 3, 2, 1, 4])); // 16

Time Complexity: O(n)
Space Complexity: O(1)

Binary Problems (5/5)

Problem 11: Sum of Two Integers (Binary)

Difficulty: Medium
LeetCode: Link

Description

Given two integers a and b, return the sum of the two integers without using the + operator.

JavaScript Solution

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
function getSum(a, b) {
  while (b !== 0) {
    const carry = a & b;
    a = a ^ b;
    b = carry << 1;
  }
  return a;
}

Test Cases

// Test Case 1
console.log(getSum(1, 2)); // 3

// Test Case 2
console.log(getSum(2, 3)); // 5

// Test Case 3
console.log(getSum(-2, 3)); // 1

Time Complexity: O(1)
Space Complexity: O(1)

Problem 12: Number of 1 Bits (Binary)

Difficulty: Easy
LeetCode: Link

Description

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has.

JavaScript Solution

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
function hammingWeight(n) {
  let count = 0;
  while (n > 0) {
    count += n & 1;
    n = n >>> 1;
  }
  return count;
}

Test Cases

// Test Case 1
console.log(hammingWeight(11)); // 3 (binary: 1011)

// Test Case 2
console.log(hammingWeight(128)); // 1 (binary: 10000000)

// Test Case 3
console.log(hammingWeight(0)); // 0

Time Complexity: O(log n)
Space Complexity: O(1)

Problem 13: Counting Bits (Binary)

Difficulty: Easy
LeetCode: Link

Description

Given a non-negative integer num, for every number i in the range 0 ≤ i ≤ num, calculate the number of 1’s in their binary representation and return them as an array.

JavaScript Solution

/**
 * @param {number} num
 * @return {number[]}
 */
function countBits(num) {
  const result = new Array(num + 1).fill(0);

  for (let i = 1; i <= num; i++) {
    result[i] = result[i >> 1] + (i & 1);
  }

  return result;
}

Test Cases

// Test Case 1
console.log(countBits(2)); // [0, 1, 1]

// Test Case 2
console.log(countBits(5)); // [0, 1, 1, 2, 1, 2]

// Test Case 3
console.log(countBits(0)); // [0]

Time Complexity: O(n)
Space Complexity: O(n)

Problem 14: Missing Number (Binary)

Difficulty: Easy
LeetCode: Link

Description

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function missingNumber(nums) {
  let missing = nums.length;

  for (let i = 0; i < nums.length; i++) {
    missing ^= i ^ nums[i];
  }

  return missing;
}

Test Cases

// Test Case 1
console.log(missingNumber([3, 0, 1])); // 2

// Test Case 2
console.log(missingNumber([0, 1])); // 2

// Test Case 3
console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8

Time Complexity: O(n)
Space Complexity: O(1)

Problem 15: Reverse Bits (Binary)

Difficulty: Easy
LeetCode: Link

Description

Reverse bits of a given 32-bit unsigned integer.

JavaScript Solution

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
function reverseBits(n) {
  let result = 0;

  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n = n >>> 1;
  }

  return result >>> 0;
}

Test Cases

// Test Case 1
console.log(reverseBits(0b00000010100101000001111010011100).toString(2)); // reversed binary

// Test Case 2
console.log(reverseBits(0b11111111111111111111111111111101)); // 3221225471

// Test Case 3
console.log(reverseBits(0)); // 0

Time Complexity: O(1)
Space Complexity: O(1)

Dynamic Programming Problems (11/11)

Problem 16: Climbing Stairs (Dynamic Programming)

Difficulty: Easy
LeetCode: Link

Description

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

JavaScript Solution

/**
 * @param {number} n
 * @return {number}
 */
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;
}

Test Cases

// Test Case 1
console.log(climbStairs(2)); // 2

// Test Case 2
console.log(climbStairs(3)); // 3

// Test Case 3
console.log(climbStairs(4)); // 5

Time Complexity: O(n)
Space Complexity: O(1)

Problem 17: Coin Change (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

Given an integer array coins representing coins of different denominations and an integer amount, return the fewest number of coins that you need to make up that amount. If impossible, return -1.

JavaScript Solution

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

Test Cases

// Test Case 1
console.log(coinChange([1, 2, 5], 11)); // 3 (5+5+1)

// Test Case 2
console.log(coinChange([2], 3)); // -1

// Test Case 3
console.log(coinChange([1], 0)); // 0

Time Complexity: O(amount × coins.length)
Space Complexity: O(amount)

Problem 18: Longest Increasing Subsequence (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

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

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
  const tails = [];

  for (const num of nums) {
    let left = 0;
    let right = tails.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < num) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    if (left === tails.length) {
      tails.push(num);
    } else {
      tails[left] = num;
    }
  }

  return tails.length;
}

Test Cases

// Test Case 1
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4

// Test Case 2
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])); // 4

// Test Case 3
console.log(lengthOfLIS([7, 7, 7, 7, 7, 7, 7])); // 1

Time Complexity: O(n log n)
Space Complexity: O(n)

Problem 19: Combination Sum IV (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

Given an integer array nums and an integer target, return the number of possible combinations that add up to target.

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function combinationSum4(nums, target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;

  for (let i = 1; i <= target; i++) {
    for (const num of nums) {
      if (i - num >= 0) {
        dp[i] += dp[i - num];
      }
    }
  }

  return dp[target];
}

Test Cases

// Test Case 1
console.log(combinationSum4([1, 2, 3], 4)); // 7

// Test Case 2
console.log(combinationSum4([2], 3)); // 0

// Test Case 3
console.log(combinationSum4([1], 0)); // 1

Time Complexity: O(target × nums.length)
Space Complexity: O(target)

Problem 20: House Robber (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1]);

  for (let i = 2; i < nums.length; i++) {
    const current = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Test Cases

// Test Case 1
console.log(rob([1, 2, 3, 1])); // 4

// Test Case 2
console.log(rob([2, 7, 9, 3, 1])); // 12

// Test Case 3
console.log(rob([2, 1, 1, 2])); // 4

Time Complexity: O(n)
Space Complexity: O(1)

Problem 21: House Robber II (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

Houses are arranged in a circle. The first house is the neighbor of the last house. Return the maximum amount of money you can rob.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function robII(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  const robRange = (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(robRange(0, nums.length - 1), robRange(1, nums.length));
}

Test Cases

// Test Case 1
console.log(robII([2, 3, 2])); // 3

// Test Case 2
console.log(robII([1, 2, 3, 1])); // 4

// Test Case 3
console.log(robII([1, 2, 3])); // 3

Time Complexity: O(n)
Space Complexity: O(1)

Problem 22: Decode Ways (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

Given a string s containing only digits, return the number of ways to decode it.

JavaScript Solution

/**
 * @param {string} s
 * @return {number}
 */
function numDecodings(s) {
  if (s[0] === "0") return 0;

  let prev2 = 1;
  let prev1 = 1;

  for (let i = 1; i < s.length; i++) {
    let current = 0;

    if (s[i] !== "0") {
      current += prev1;
    }

    const twoDigit = parseInt(s.substring(i - 1, i + 1));
    if (twoDigit >= 10 && twoDigit <= 26) {
      current += prev2;
    }

    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Test Cases

// Test Case 1
console.log(numDecodings("12")); // 2

// Test Case 2
console.log(numDecodings("226")); // 3

// Test Case 3
console.log(numDecodings("0")); // 0

Time Complexity: O(n)
Space Complexity: O(1)

Problem 23: Unique Paths (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

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

JavaScript Solution

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
function uniquePaths(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];
}

Test Cases

// Test Case 1
console.log(uniquePaths(3, 7)); // 28

// Test Case 2
console.log(uniquePaths(3, 2)); // 3

// Test Case 3
console.log(uniquePaths(1, 1)); // 1

Time Complexity: O(m × n)
Space Complexity: O(n)

Problem 24: Jump Game (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

Given an array of non-negative integers nums, where nums[i] represents maximum jump length from position i, determine if you can reach the last index.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
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;
}

Test Cases

// Test Case 1
console.log(canJump([2, 3, 1, 1, 4])); // true

// Test Case 2
console.log(canJump([3, 2, 1, 0, 4])); // false

// Test Case 3
console.log(canJump([0])); // true

Time Complexity: O(n)
Space Complexity: O(1)

Problem 25: Word Break (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

JavaScript Solution

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
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];
}

Test Cases

// Test Case 1
console.log(wordBreak("leetcode", ["leet", "code"])); // true

// Test Case 2
console.log(wordBreak("applepenapple", ["apple", "pen"])); // true

// Test Case 3
console.log(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false

Time Complexity: O(n^2)
Space Complexity: O(n)

Problem 26: Longest Common Subsequence (Dynamic Programming)

Difficulty: Medium
LeetCode: Link

Description

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

JavaScript Solution

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const dp = new Array(m + 1).fill(0).map(() => new 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];
}

Test Cases

// Test Case 1
console.log(longestCommonSubsequence("abcde", "ace")); // 3

// Test Case 2
console.log(longestCommonSubsequence("abc", "abc")); // 3

// Test Case 3
console.log(longestCommonSubsequence("abc", "def")); // 0

Time Complexity: O(m × n)
Space Complexity: O(m × n)

Graph Problems (8/8)

Problem 27: Clone Graph (Graph)

Difficulty: Medium
LeetCode: Link

Description

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node contains a value (val) and a list of its neighbors.

JavaScript Solution

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
function cloneGraph(node) {
  if (!node) return null;

  const visited = new Map();

  const dfs = originalNode => {
    if (visited.has(originalNode)) {
      return visited.get(originalNode);
    }

    const newNode = new Node(originalNode.val);
    visited.set(originalNode, newNode);

    for (const neighbor of originalNode.neighbors) {
      newNode.neighbors.push(dfs(neighbor));
    }

    return newNode;
  };

  return dfs(node);
}

Test Cases

// Test case setup - simplified structure representation
const adjList = [
  [2, 4],
  [1, 3],
  [2, 4],
  [1, 3],
];
// Note: Actual testing would require building the Node objects
console.log("Clone Graph test requires Node object setup");

Time Complexity: O(V + E)
Space Complexity: O(V)

Problem 28: Course Schedule (Graph)

Difficulty: Medium
LeetCode: Link

Description

There are numCourses courses labeled from 0 to numCourses - 1. prerequisites[i] = [ai, bi] means you must take course bi before ai. Return true if you can finish all courses, otherwise false.

JavaScript Solution

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
function canFinish(numCourses, prerequisites) {
  const graph = new Array(numCourses).fill(0).map(() => []);
  const inDegree = new Array(numCourses).fill(0);

  // Build graph and in-degree
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }

  // Queue for courses with no prerequisites
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }

  let completed = 0;
  while (queue.length > 0) {
    const course = queue.shift();
    completed++;

    for (const nextCourse of graph[course]) {
      inDegree[nextCourse]--;
      if (inDegree[nextCourse] === 0) {
        queue.push(nextCourse);
      }
    }
  }

  return completed === numCourses;
}

Test Cases

// Test Case 1
console.log(canFinish(2, [[1, 0]])); // true

// Test Case 2
console.log(
  canFinish(2, [
    [1, 0],
    [0, 1],
  ])
); // false

// Test Case 3
console.log(
  canFinish(5, [
    [1, 0],
    [2, 0],
    [3, 1],
    [3, 2],
  ])
); // true

Time Complexity: O(V + E)
Space Complexity: O(V + E)

Problem 29: Pacific Atlantic Water Flow (Graph)

Difficulty: Medium
LeetCode: Link

Description

Given an m x n matrix of heights, find locations where water can flow to both Pacific and Atlantic oceans. Water can flow from a cell to neighboring cells (horizontally/vertically) if the neighbor’s height is less than or equal.

JavaScript Solution

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
function pacificAtlantic(matrix) {
  if (!matrix || matrix.length === 0 || matrix[0].length === 0) return [];

  const rows = matrix.length;
  const cols = matrix[0].length;
  const pacific = new Array(rows)
    .fill(0)
    .map(() => new Array(cols).fill(false));
  const atlantic = new Array(rows)
    .fill(0)
    .map(() => new Array(cols).fill(false));

  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  const dfs = (row, col, visited) => {
    visited[row][col] = true;

    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;

      if (
        newRow >= 0 &&
        newRow < rows &&
        newCol >= 0 &&
        newCol < cols &&
        !visited[newRow][newCol] &&
        matrix[newRow][newCol] >= matrix[row][col]
      ) {
        dfs(newRow, newCol, visited);
      }
    }
  };

  // Start from Pacific border (top and left)
  for (let col = 0; col < cols; col++) {
    dfs(0, col, pacific);
  }
  for (let row = 0; row < rows; row++) {
    dfs(row, 0, pacific);
  }

  // Start from Atlantic border (bottom and right)
  for (let col = 0; col < cols; col++) {
    dfs(rows - 1, col, atlantic);
  }
  for (let row = 0; row < rows; row++) {
    dfs(row, cols - 1, atlantic);
  }

  // Find cells reachable from both oceans
  const result = [];
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (pacific[row][col] && atlantic[row][col]) {
        result.push([row, col]);
      }
    }
  }

  return result;
}

Test Cases

// Test Case 1
console.log(
  pacificAtlantic([
    [1, 2, 2, 3, 5],
    [3, 2, 3, 4, 4],
    [2, 4, 5, 3, 1],
    [6, 7, 1, 4, 5],
    [5, 1, 1, 2, 4],
  ])
);
// [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

// Test Case 2
console.log(pacificAtlantic([[1]])); // [[0,0]]

// Test Case 3
console.log(
  pacificAtlantic([
    [1, 2, 3],
    [8, 9, 4],
    [7, 6, 5],
  ])
);
// [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

Time Complexity: O(m × n)
Space Complexity: O(m × n)

Problem 30: Number of Islands (Graph)

Difficulty: Medium
LeetCode: Link

Description

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

JavaScript Solution

/**
 * @param {character[][]} grid
 * @return {number}
 */
function numIslands(grid) {
  if (!grid || grid.length === 0 || grid[0].length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  const dfs = (row, col) => {
    if (
      row < 0 ||
      row >= rows ||
      col < 0 ||
      col >= cols ||
      grid[row][col] !== "1"
    ) {
      return;
    }

    grid[row][col] = "0"; // Mark as visited

    dfs(row + 1, col);
    dfs(row - 1, col);
    dfs(row, col + 1);
    dfs(row, col - 1);
  };

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === "1") {
        count++;
        dfs(row, col);
      }
    }
  }

  return count;
}

Test Cases

// Test Case 1
const grid1 = [
  ["1", "1", "1", "1", "0"],
  ["1", "1", "0", "1", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "0", "0", "0"],
];
console.log(numIslands(grid1)); // 1

// Test Case 2
const grid2 = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"],
];
console.log(numIslands(grid2)); // 3

// Test Case 3
console.log(numIslands([["0"]])); // 0

Time Complexity: O(m × n)
Space Complexity: O(m × n) (due to recursion stack)

Problem 31: Longest Consecutive Sequence (Graph)

Difficulty: Medium
LeetCode: Link

Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function longestConsecutive(nums) {
  const numSet = new Set(nums);
  let longest = 0;

  for (const num of numSet) {
    // Only start counting from beginning of sequence
    if (!numSet.has(num - 1)) {
      let current = num;
      let length = 1;

      while (numSet.has(current + 1)) {
        current++;
        length++;
      }

      longest = Math.max(longest, length);
    }
  }

  return longest;
}

Test Cases

// Test Case 1
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // 4

// Test Case 2
console.log(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1])); // 9

// Test Case 3
console.log(longestConsecutive([])); // 0

Time Complexity: O(n)
Space Complexity: O(n)

Interval Problems (6/6)

Problem 32: Insert Interval (Interval)

Difficulty: Medium
LeetCode: Link

Description

Given a set of non-overlapping intervals, insert a new interval into intervals (merge if necessary).

JavaScript Solution

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
function insert(intervals, newInterval) {
  const result = [];
  let i = 0;

  // Add 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;
}

Test Cases

// Test Case 1
console.log(
  insert(
    [
      [1, 3],
      [6, 9],
    ],
    [2, 5]
  )
); // [[1,5],[6,9]]

// Test Case 2
console.log(
  insert(
    [
      [1, 2],
      [3, 5],
      [6, 7],
      [8, 10],
      [12, 16],
    ],
    [4, 8]
  )
);
// [[1,2],[3,10],[12,16]]

// Test Case 3
console.log(insert([], [5, 7])); // [[5,7]]

Time Complexity: O(n)
Space Complexity: O(1)

Problem 33: Merge Intervals (Interval)

Difficulty: Medium
LeetCode: Link

Description

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals.

JavaScript Solution

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
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]) {
      // Overlapping, merge them
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push(current);
    }
  }

  return merged;
}

Test Cases

// Test Case 1
console.log(
  merge([
    [1, 3],
    [2, 6],
    [8, 10],
    [15, 18],
  ])
);
// [[1,6],[8,10],[15,18]]

// Test Case 2
console.log(
  merge([
    [1, 4],
    [4, 5],
  ])
); // [[1,5]]

// Test Case 3
console.log(
  merge([
    [1, 3],
    [2, 4],
    [5, 7],
    [6, 8],
  ])
); // [[1,4],[5,8]]

Time Complexity: O(n log n)
Space Complexity: O(1)

Problem 34: Non-overlapping Intervals (Interval)

Difficulty: Medium
LeetCode: Link

Description

Given an array of intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

JavaScript Solution

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function eraseOverlapIntervals(intervals) {
  if (intervals.length <= 1) return 0;

  intervals.sort((a, b) => a[1] - b[1]);

  let count = 0;
  let prevEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];

    if (current[0] < prevEnd) {
      count++;
      prevEnd = Math.min(prevEnd, current[1]);
    } else {
      prevEnd = current[1];
    }
  }

  return count;
}