Lv.5 Flashcards
Lv.5 problems of Firecode.io (11 cards)
Longest Palindromic Substring
Given a string str, return the longest palindromic substring within str. A palindrome is a string that reads the same backward as forward. The substring should be contiguous, and if there are multiple palindromic substrings of the same maximum length, return any one of them.
/**
* Returns the longest palindromic substring in the input string.
* @param {string} str - The input string.
* @returns {string} - The longest palindromic substring.
*/
function longestPalindrome(str) {
// TODO: Implement the logic to find the longest palindromic substring
return "";
}
🪜 Stepper Hints
🪂 Hint 1:
What defines a palindrome? Start by writing a function that checks if a substring is a palindrome.
🧭 Hint 2:
Can you find all substrings and check each one? What’s the time complexity of doing that?
🔎 Hint 3:
Look at the string from each character and try to expand outwards to see how far a palindrome goes.
⛳ Hint 4:
There are two types of centers for palindromes:
* Odd-length (centered at a character)
* Even-length (centered between two characters)
Try expanding around both types of centers.
💡 Final Hint:
Use a helper function to expand around each center and update the longest palindrome found so far.
// --- Test Cases ---
function testLongestPalindrome() {
const testCases = [
{ input: "", expected: "" }, // empty string
{ input: "a", expected: "a" },
{ input: "ab", expected: "a" }, // or "b"
{ input: "racecar", expected: "racecar" },
{ input: "babad", expected: "bab" }, // or "aba"
{ input: "cbbd", expected: "bb" },
{ input: "forgeeksskeegfor", expected: "geeksskeeg" },
{ input: "aacabdkacaa", expected: "aca" },
{ input: "abcde", expected: "a" }, // or "b", "c", etc.
{ input: "aaaa", expected: "aaaa" },
];
testCases.forEach(({ input, expected }, index) => {
const result = longestPalindrome(input);
const passed = expected.length === result.length && isPalindrome(result);
console.log(`Test Case ${index + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Input: "${input}"`);
console.log(` Expected length: ${expected.length}`);
console.log(` Got: "${result}"`);
}
});
}
// --- Helper to check if a string is a palindrome ---
function isPalindrome(s) {
return s === s.split('').reverse().join('');
}
// Run tests
testLongestPalindrome();
📚 Related LeetCode Problems
https://leetcode.com/problems/longest-palindromic-substring/
https://leetcode.com/problems/palindromic-substrings/
https://leetcode.com/problems/longest-palindromic-subsequence/
https://leetcode.com/problems/longest-common-subsequence/
https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
✅ JavaScript Solution
/**
* Returns the longest palindromic substring from the input string.
* @param {string} str
* @return {string}
*/
function longestPalindrome(str) {
if (str.length <= 1) return str;
let start = 0;
let end = 0;
// Helper function to expand around center and return palindrome bounds
const expandAroundCenter = (left, right) => {
while (left >= 0 && right < str.length && str[left] === str[right]) {
left--;
right++;
}
return [left + 1, right - 1];
};
for (let i = 0; i < str.length; i++) {
// Odd-length palindrome
let [left1, right1] = expandAroundCenter(i, i);
// Even-length palindrome
let [left2, right2] = expandAroundCenter(i, i + 1);
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return str.slice(start, end + 1);
}
🧪 Example Usage
console.log(longestPalindrome("babad")); // Output: "bab" or "aba"
console.log(longestPalindrome("cbbd")); // Output: "bb"
console.log(longestPalindrome("a")); // Output: "a"
console.log(longestPalindrome("ac")); // Output: "a" or "c"
🔁 Alternative Approaches (for interest)
1. Dynamic Programming (DP)
* Use a 2D table to store whether s[i..j] is a palindrome.
* Time Complexity: O(n^2)
* Space Complexity: O(n^2)
* Less preferred in practice due to space usage.
- Manacher’s Algorithm (Advanced)
* Linear time O(n) algorithm to find the longest palindromic substring.
* Complex to implement, not ideal for first-time learners.
Subset Summation with Number Constraint
Given an array of integers arr, a target sum TARGET, and an integer MUST_HAVE, return true if there exists a subset of arr that sums up to TARGET and includes at least one occurrence of MUST_HAVE. Otherwise, return false.
A subset is a selection of zero or more elements from the array without reordering. The same element can only be used as many times as it appears in the input array.
/**
* Determines if a subset of arr adds up to TARGET and includes MUST_HAVE at least once.
* @param {number[]} arr - Array of integers (can include negatives and duplicates).
* @param {number} target - The target sum to find.
* @param {number} mustHave - The value that must be included at least once in the subset.
* @returns {boolean} - True if such a subset exists, otherwise false.
*/
function subsetSumWithMustHave(arr, target, mustHave) {
// TODO: Implement the logic to find a subset that includes MUST_HAVE and sums to target
return false;
}
🪜 Stepper Hints
🪂 Hint 1:
Have you tried solving the classic subset sum problem first? That’s when you try to check if any subset adds up to a target.
🔍 Hint 2:
How would you keep track of the total sum as you go through each element? Would recursion or iteration help?
🧱 Hint 3:
You’ll likely need to use dynamic programming or backtracking to explore possible subsets. Think of exploring subsets with and without the current element.
⛳ Hint 4:
What if you ensure the MUST_HAVE is used at least once during subset exploration? Can you pass a flag around in recursion that turns true when it’s used?
🧩 Final Hint:
Use recursion (or memoized DP) with three parameters:
* Current index
* Current sum
* Whether MUST_HAVE has been used
// --- Test Cases ---
function testSubsetSumWithMustHave() {
const testCases = [
{ arr: [2, 4, 6, 10], target: 16, mustHave: 6, expected: true }, // 6 + 10
{ arr: [2, 4, 6, 10], target: 16, mustHave: 5, expected: false }, // mustHave not present
{ arr: [1, 2, 3, 4], target: 6, mustHave: 3, expected: true }, // 3 + 2 + 1
{ arr: [1, 2, 3, 4], target: 6, mustHave: 4, expected: true }, // 4 + 2
{ arr: [1, 2, 3, 4], target: 6, mustHave: 5, expected: false }, // mustHave not in array
{ arr: [], target: 0, mustHave: 0, expected: false }, // empty array
{ arr: [5], target: 5, mustHave: 5, expected: true }, // trivial case
{ arr: [1, 1, 1, 1], target: 3, mustHave: 1, expected: true }, // includes mustHave
{ arr: [1, 2, 3, 4], target: 11, mustHave: 3, expected: false }, // exceeds sum
{ arr: [3, 34, 4, 12, 5, 2], target: 9, mustHave: 4, expected: true }, // 4 + 5
];
testCases.forEach(({ arr, target, mustHave, expected }, index) => {
const result = subsetSumWithMustHave(arr, target, mustHave);
const passed = result === expected;
console.log(`Test Case ${index + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Input: arr=[${arr}], target=${target}, mustHave=${mustHave}`);
console.log(` Expected: ${expected}`);
console.log(` Got: ${result}`);
}
});
}
// Run tests
testSubsetSumWithMustHave();
📚 Related LeetCode Problems
https://leetcode.com/problems/partition-equal-subset-sum/
https://leetcode.com/problems/target-sum/
✅ JavaScript Solution (Recursive with Memoization)
/**
* Determines if there's a subset that sums to target and includes MUST_HAVE.
* @param {number[]} arr
* @param {number} target
* @param {number} mustHave
* @return {boolean}
*/
function subsetSumWithMustHave(arr, target, mustHave) {
const memo = new Map();
const dfs = (index, currentSum, usedMustHave) => {
if (currentSum === target && usedMustHave) {
return true;
}
if (index === arr.length || currentSum > target) {
return false;
}
const key = `${index},${currentSum},${usedMustHave}`;
if (memo.has(key)) return memo.get(key);
// Option 1: Exclude current element
const exclude = dfs(index + 1, currentSum, usedMustHave);
// Option 2: Include current element
const include = dfs(
index + 1,
currentSum + arr[index],
usedMustHave || arr[index] === mustHave
);
const result = exclude || include;
memo.set(key, result);
return result;
};
return dfs(0, 0, false);
}
🧪 Example Usage
console.log(subsetSumWithMustHave([3, 4, 5, 2], 9, 5)); // true (5+4) console.log(subsetSumWithMustHave([1, 2, 3], 6, 2)); // true (1+2+3) console.log(subsetSumWithMustHave([1, 2, 3], 6, 4)); // false console.log(subsetSumWithMustHave([1, 2, 3], 5, 3)); // true (2+3)
⏱ Time and Space Complexity
Time Complexity: O(n * target * 2)
* n is number of elements
* target is the max possible sum
* 2 is for the usedMustHave flag
Space Complexity: O(n * target * 2) for memoization
🔄 Alternative Approaches
1. Bottom-Up Dynamic Programming
* Build a 2D DP table: dp[i][sum][usedMust]
* More complex to write, but avoids recursion stack.
- Bitmask DP (for smaller arrays)
* Fastest for sets with up to ~20 elements.
* Uses bitmask to represent used elements, more advanced.
Pascal’s Triangle
Given an integer NUM_ROWS, return the first NUM_ROWS of Pascal’s Triangle.
In Pascal’s Triangle:
* Each row starts and ends with 1.
* Each interior element is the sum of the two elements above it from the previous row.
/**
* Generates the first numRows of Pascal's Triangle.
* @param {number} numRows - Number of rows to generate.
* @returns {number[][]} - A 2D array representing Pascal's Triangle.
*/
function generatePascalsTriangle(numRows) {
// TODO: Implement logic to generate Pascal's Triangle
return [];
}
🪜 Stepper Hints
🪂 Hint 1:
Have you tried drawing the first few rows of Pascal’s Triangle by hand? Observe how each row is built from the previous one.
🧭 Hint 2:
Every row starts and ends with a 1. What do you think happens with the elements in between?
🔎 Hint 3:
The number at position j in row i (0-indexed) is the sum of the two numbers directly above it from row i - 1, positions j - 1 and j.
⚙️ Hint 4:
You’ll need a loop to build each row, starting from row 1 up to NUM_ROWS. Think of using a 2D array to store all rows.
💡 Final Hint:
Use nested loops:
* The outer loop runs from 0 to NUM_ROWS - 1.
* The inner loop constructs each row:
* Start with 1.
* Add sums of adjacent elements from the previous row.
* End with 1.
// --- Test Cases ---
function testGeneratePascalsTriangle() {
const testCases = [
{
input: 0,
expected: []
},
{
input: 1,
expected: [[1]]
},
{
input: 2,
expected: [[1], [1, 1]]
},
{
input: 5,
expected: [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1]
]
},
{
input: 6,
expected: [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1]
]
}
];
testCases.forEach(({ input, expected }, index) => {
const result = generatePascalsTriangle(input);
const passed = JSON.stringify(result) === JSON.stringify(expected);
console.log(`Test Case ${index + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Input: ${input}`);
console.log(` Expected: ${JSON.stringify(expected)}`);
console.log(` Got: ${JSON.stringify(result)}`);
}
});
}
// Run tests
testGeneratePascalsTriangle();
📚 Related LeetCode Problem
https://leetcode.com/problems/pascals-triangle/
✅ JavaScript Solution (Iterative Approach)
/**
* Generates the first numRows of Pascal's Triangle.
* @param {number} numRows
* @return {number[][]}
*/
function generatePascalTriangle(numRows) {
const triangle = [];
for (let i = 0; i < numRows; i++) {
const row = [];
for (let j = 0; j <= i; j++) {
if (j === 0 || j === i) {
row.push(1); // First and last elements are always 1
} else {
// Sum of two numbers from previous row
const prevRow = triangle[i - 1];
row.push(prevRow[j - 1] + prevRow[j]);
}
}
triangle.push(row);
}
return triangle;
}
🧪 Example Usage
console.log(generatePascalTriangle(5)); /* [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] */
⏱ Time and Space Complexity
Time Complexity: O(numRows^2)
Because the number of elements across all rows is 1 + 2 + 3 + … + numRows = O(numRows^2)
Space Complexity: O(numRows^2)
You’re storing all rows
🔄 Alternate Approaches
1. Recursive Pascal’s Triangle (Not Recommended)
* Builds triangle recursively
* Very inefficient for larger values due to repeated subproblem recomputation unless memoized.
Minimum Sum Path
You are given a 2D grid of non-negative integers. A robot is initially positioned at the top-left corner of the grid (cell [0][0]) and wants to reach the bottom-right corner (cell [m-1][n-1]).
The robot can only move either right or down at any point in time.
Your task is to find the path from top-left to bottom-right that minimizes the sum of all numbers along its path and return this minimum sum.
/**
* Calculates the minimum path sum from top-left to bottom-right of a 2D grid.
* The robot can only move right or down.
* @param {number[][]} grid - 2D array of non-negative integers.
* @returns {number} - Minimum sum along the path.
*/
function minPathSum(grid) {
// TODO: Implement logic to find the path with the minimum sum
return 0;
}
🪜 Stepper Hints
🪂 Hint 1:
Think of moving through the grid as a game. At each step, you can only go right or down. What would your total score be along a path?
🧭 Hint 2:
Try solving a smaller version of the grid on paper. What patterns do you notice about how to get the minimal sum to each cell?
🔎 Hint 3:
At any cell (i, j), the minimum path sum to get there is based on either:
* The cell above it (i-1, j)
* Or the cell to its left (i, j-1)
⚙️ Hint 4:
Use a 2D DP table (or reuse the input grid) where each cell stores the minimum path sum to reach that cell.
💡 Final Hint:
You’ll need to:
* Fill in the first row and first column separately (since they have only one path)
* Then fill the rest of the grid based on the rule:grid[i][j] += min(grid[i-1][j], grid[i][j-1])
// --- Test Cases ---
function testMinPathSum() {
const testCases = [
{
grid: [[1]],
expected: 1
},
{
grid: [[1, 2], [1, 1]],
expected: 3 // 1 → 1 → 1
},
{
grid: [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
],
expected: 7 // 1→3→1→1→1
},
{
grid: [
[5, 1, 0],
[2, 3, 1],
[4, 2, 1]
],
expected: 10 // 5→1→0→1→1→1
},
{
grid: [
[1, 2, 5],
[3, 2, 1]
],
expected: 6 // 1→2→2→1
},
{
grid: [
[1, 2],
[1, 100]
],
expected: 4 // 1→2→1
},
{
grid: [
[1, 1, 1],
[1, 1, 1],
[1, 1, 1]
],
expected: 5 // all ones, minimal path = right→right→down→down or similar
}
];
testCases.forEach(({ grid, expected }, index) => {
const result = minPathSum(grid);
const passed = result === expected;
console.log(`Test Case ${index + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Input grid: ${JSON.stringify(grid)}`);
console.log(` Expected: ${expected}`);
console.log(` Got: ${result}`);
}
});
}
// Run tests
testMinPathSum();
📚 Related LeetCode Problems
https://leetcode.com/problems/minimum-path-sum/
https://leetcode.com/problems/unique-paths/
https://leetcode.com/problems/unique-paths-ii/
https://leetcode.com/problems/triangle/
✅ JavaScript Solution (In-Place Dynamic Programming)
/**
* Finds the minimum path sum from top-left to bottom-right in a grid.
* @param {number[][]} grid
* @return {number}
*/
function minPathSum(grid) {
const rows = grid.length;
const cols = grid[0].length;
// Fill the first row
for (let j = 1; j < cols; j++) {
grid[0][j] += grid[0][j - 1];
}
// Fill the first column
for (let i = 1; i < rows; i++) {
grid[i][0] += grid[i - 1][0];
}
// Fill the rest of the grid
for (let i = 1; i < rows; i++) {
for (let j = 1; j < cols; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
// The bottom-right cell contains the result
return grid[rows - 1][cols - 1];
}
🧪 Example Usage
const grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ]; console.log(minPathSum(grid)); // Output: 7 (Path: 1→3→1→1→1)
⏱ Time and Space Complexity
Time Complexity: O(m * n)
Traverse each cell once
Space Complexity: O(1) (in-place)
If modifying grid. Otherwise O(m * n) if using a separate dp table.
🔄 Alternate Approaches
1. Recursive DFS (with memoization)
* Explore both directions at each cell and store results in a memo table.
* More intuitive but less efficient without memoization.
- Bottom-Up DP with Separate Table
const dp = Array.from({ length: m }, () => Array(n).fill(0));
Useful if input grid must remain unchanged.
Largest Square
Given a 2D binary matrix filled with ‘0’s and ‘1’s, find the area of the largest square containing only ‘1’s and return its area.
/**
* Finds the area of the largest square containing only 1's in a 2D binary matrix.
* @param {character[][]} matrix - 2D binary matrix of '0' and '1' strings.
* @returns {number} - Area of the largest square of 1's.
*/
function maximalSquare(matrix) {
// TODO: Implement the dynamic programming logic to find the largest square
return 0;
}
🪜 Stepper Hints
🪂 Hint 1:
Try visualizing the matrix and drawing some squares made entirely of 1s. What happens when you expand a square by one more row and column?
🧭 Hint 2:
How can you know if a square of size 2x2 or 3x3 exists at a particular cell? What does it depend on?
🔎 Hint 3:
Try breaking the problem into subproblems:
Can you figure out the largest square ending at a particular cell (i, j)?
🧠 Hint 4:
For cell (i, j), if it’s a ‘1’, the size of the largest square ending at that cell is:
1 + min(top, left, top-left)
Those are:
* (i-1, j)
* (i, j-1)
* (i-1, j-1)
⚙️ Final Hint:
Use a DP table (or modify the matrix in place if allowed). Keep track of the maximum square size found while building the DP table.
// --- Test Cases ---
function testMaximalSquare() {
const testCases = [
{
matrix: [],
expected: 0
},
{
matrix: [['0']],
expected: 0
},
{
matrix: [['1']],
expected: 1
},
{
matrix: [
['1', '0'],
['0', '1']
],
expected: 1
},
{
matrix: [
['1', '1', '1'],
['1', '1', '1'],
['1', '1', '1']
],
expected: 9
},
{
matrix: [
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
],
expected: 4 // 2x2 square
},
{
matrix: [
['0', '1'],
['1', '0']
],
expected: 1
}
];
testCases.forEach(({ matrix, expected }, index) => {
const result = maximalSquare(matrix);
const passed = result === expected;
console.log(`Test Case ${index + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Input matrix: ${JSON.stringify(matrix)}`);
console.log(` Expected: ${expected}`);
console.log(` Got: ${result}`);
}
});
}
// Run tests
testMaximalSquare();
📚 Related LeetCode Problems
https://leetcode.com/problems/maximal-square/
https://leetcode.com/problems/maximal-rectangle/
https://leetcode.com/problems/count-square-submatrices-with-all-ones/
✅ JavaScript Solution (DP with extra space)
/**
* Returns the area of the largest square of '1's in a binary matrix.
* @param {character[][]} matrix
* @return {number}
*/
function maximalSquare(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const dp = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
let maxSide = 0;
for (let i = 1; i <= rows; i++) {
for (let j = 1; j <= cols; j++) {
if (matrix[i - 1][j - 1] === '1') {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // top
dp[i][j - 1], // left
dp[i - 1][j - 1] // top-left
);
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
🧪 Example Usage
const matrix = [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ]; console.log(maximalSquare(matrix)); // Output: 4 (2x2 square)
⏱ Time and Space Complexity
Time Complexity: O(m * n) — visiting each cell once
Space Complexity: O(m * n) — extra dp table (or O(n) if optimized to 1D)
🔄 Alternate Approaches
1. In-Place DP
Modify the original matrix to save space.
Be careful to convert ‘1’ and ‘0’ to numbers.
- 1D DP Optimization
Use just one row (or two), reusing space — reduces space complexity to O(n)
🚀 Why Optimize Space?
In the original 2D dp[i][j], to compute dp[i][j], we only need:
- dp[i-1][j-1] → top-left
- dp[i-1][j] → top
- dp[i][j-1] → left
So at any time, we only need the previous row and the current row. Hence, we can reduce space from a full 2D array to a 1D array with one extra variable for top-left.
✅ JavaScript Solution (Space-Optimized)
/**
* Returns the area of the largest square of '1's using O(n) space.
* @param {character[][]} matrix
* @return {number}
*/
function maximalSquare(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const dp = Array(cols + 1).fill(0); // 1D DP array for the current row
let maxSide = 0;
let prev = 0; // Stores dp[j-1] from previous row (top-left)
for (let i = 1; i <= rows; i++) {
prev = 0; // Reset for each row
for (let j = 1; j <= cols; j++) {
const temp = dp[j]; // Store current cell before updating
if (matrix[i - 1][j - 1] === '1') {
dp[j] = 1 + Math.min(dp[j], dp[j - 1], prev);
maxSide = Math.max(maxSide, dp[j]);
} else {
dp[j] = 0; // Reset when encountering '0'
}
prev = temp; // Move top-left reference
}
}
return maxSide * maxSide;
}
⏱ Time and Space Complexity
Time Complexity: O(m * n) — same as before, iterate through each cell once
Space Complexity: O(n) — only one row of the matrix is stored in memory
Boggle With Paper Dictionary
Given a 2D board of characters and a list of valid words (a dictionary), find all words on the board that appear in the dictionary.
Rules:
* You can form words by sequentially adjacent letters on the board.
* Adjacent letters can be horizontally or vertically neighboring (no diagonal moves).
* You cannot use the same cell more than once in a single word.
* Return all valid words found on the board that exist in the dictionary, sorted in lexicographical order.
/**
* Finds all valid words on the board from the given dictionary.
* @param {character[][]} board - 2D board of letters.
* @param {string[]} words - List of valid words (dictionary).
* @returns {string[]} - List of found words, sorted lexicographically.
*/
function findWords(board, words) {
// TODO: Implement word search logic using Trie and DFS
return [];
}
🪜 Stepper Hints
🪂 Hint 1:
Try starting from each cell. Can you “walk” through the board and form valid words?
🧭 Hint 2:
Brute-force search for each word in the dictionary could be very slow. How can you avoid unnecessary searches?
🔎 Hint 3:
Can you group words by common prefixes? That way, if a prefix doesn’t match, you don’t need to explore further.
🧠 Hint 4:
Build a Trie (prefix tree) from the dictionary. While traversing the board, only continue exploring if the current path exists in the trie.
⚙️ Final Hint:
Use DFS with backtracking:
* Mark a cell as visited
* Recurse on neighbors
* Unmark it after recursion
Use a Trie to quickly check for prefix matches during DFS.
// --- Test Cases ---
function testFindWords() {
const testCases = [
{
board: [
['o', 'a', 'a', 'n'],
['e', 't', 'a', 'e'],
['i', 'h', 'k', 'r'],
['i', 'f', 'l', 'v']
],
words: ['oath', 'pea', 'eat', 'rain'],
expected: ['eat', 'oath']
},
{
board: [
['a', 'b'],
['c', 'd']
],
words: ['ab', 'cb', 'ad', 'bd', 'ac', 'ca', 'da', 'bc', 'db', 'adcb'],
expected: ['ab', 'bd']
},
{
board: [
['a']
],
words: ['a'],
expected: ['a']
},
{
board: [],
words: ['any'],
expected: []
},
{
board: [
['a', 'b'],
['c', 'd']
],
words: [],
expected: []
},
{
board: [
['x', 'y', 'z'],
['a', 'b', 'c'],
['d', 'e', 'f']
],
words: ['xyz', 'xya', 'xyc', 'bcf', 'def'],
expected: ['bcf', 'def', 'xyz']
}
];
testCases.forEach(({ board, words, expected }, index) => {
const result = findWords(board, words).sort();
const passed = JSON.stringify(result) === JSON.stringify(expected.sort());
console.log(`Test Case ${index + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Board: ${JSON.stringify(board)}`);
console.log(` Words: ${JSON.stringify(words)}`);
console.log(` Expected: ${JSON.stringify(expected)}`);
console.log(` Got: ${JSON.stringify(result)}`);
}
});
}
// Run tests
testFindWords();
📚 Related LeetCode Problems
https://leetcode.com/problems/word-search-ii/
https://leetcode.com/problems/word-search/
https://leetcode.com/problems/word-squares/
https://leetcode.com/problems/design-add-and-search-words-data-structure/
✅ JavaScript Solution (Trie + DFS Backtracking)
class TrieNode {
constructor() {
this.children = {};
this.word = null; // Store full word at the end node
}
}
function buildTrie(words) {
const root = new TrieNode();
for (let word of words) {
let node = root;
for (let char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.word = word;
}
return root;
}
/**
* Finds all valid words from a dictionary in a 2D board.
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
function findWords(board, words) {
const root = buildTrie(words);
const result = new Set();
const rows = board.length;
const cols = board[0].length;
function dfs(r, c, node) {
const char = board[r][c];
if (!node.children[char]) return;
node = node.children[char];
if (node.word !== null) {
result.add(node.word); // avoid duplicates
node.word = null; // de-duplicate by pruning
}
board[r][c] = '#'; // mark visited
const directions = [
[0, 1], [1, 0], [-1, 0], [0, -1]
];
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
dfs(nr, nc, node);
}
}
board[r][c] = char; // backtrack
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
dfs(i, j, root);
}
}
return Array.from(result).sort();
}
🧪 Example
const board = [ ["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"] ]; const words = ["oath", "pea", "eat", "rain"]; console.log(findWords(board, words)); // Output: ["eat", "oath"]
⏱ Time and Space Complexity
Time Complexity:
Worst case: O(M * 4^L) where:
* M = total cells on board
* L = maximum length of a word
Using a Trie cuts off search branches early, reducing redundant paths.
Space Complexity:
O(N) for Trie, where N = total characters in all words
O(L) for recursion stack depth during DFS
Graph Depth First Search
Implement a method that supports finding a node in a graph using Depth First Search.
🪜 Stepper Hints
🪂 Hint 1:
Imagine walking through a maze. You pick a path and keep going until you hit a wall. Then you backtrack and try a new path.
🧭 Hint 2:
Can you think of a way to explore each node and mark it so you don’t visit it again?
🔍 Hint 3:
This strategy can be implemented recursively or with an explicit stack. Which way do you prefer to start?
🧠 Hint 4:
When you visit a node:
* Mark it as visited.
* Check if it’s the one you’re looking for.
* Otherwise, recursively search its neighbors.
⚙️ Final Hint:
Use a Set to track visited nodes. This will prevent infinite loops in cyclic graphs.
/**
* Performs Depth First Search to find a target node in a graph.
* @param {Object} graph - Adjacency list representing the graph, e.g. { A: ['B', 'C'], B: ['D'], C: [] }
* @param {string} startNode - The node to start searching from.
* @param {string} targetNode - The node to find.
* @returns {boolean} - True if targetNode is found, false otherwise.
*/
function dfsFindNode(graph, startNode, targetNode) {
// TODO: Implement DFS to find the targetNode starting from startNode
return false;
}
// --- Test Cases ---
function testDfsFindNode() {
const testCases = [
{
graph: {
A: ['B', 'C'],
B: ['D'],
C: [],
D: []
},
startNode: 'A',
targetNode: 'D',
expected: true
},
{
graph: {
A: ['B', 'C'],
B: ['D'],
C: [],
D: []
},
startNode: 'A',
targetNode: 'E',
expected: false
},
{
graph: {
A: ['B'],
B: ['C'],
C: ['A'] // cycle
},
startNode: 'A',
targetNode: 'C',
expected: true
},
{
graph: {
A: ['B'],
B: ['C'],
C: ['A'] // cycle
},
startNode: 'B',
targetNode: 'D',
expected: false
},
{
graph: {
X: ['Y'],
Y: [],
Z: ['X']
},
startNode: 'Z',
targetNode: 'Y',
expected: true
},
{
graph: {
X: ['Y'],
Y: [],
Z: ['X']
},
startNode: 'X',
targetNode: 'Z',
expected: false
}
];
testCases.forEach(({ graph, startNode, targetNode, expected }, index) => {
const result = dfsFindNode(graph, startNode, targetNode);
const passed = result === expected;
console.log(`Test Case ${index + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Graph: ${JSON.stringify(graph)}`);
console.log(` Start: ${startNode}, Target: ${targetNode}`);
console.log(` Expected: ${expected}, Got: ${result}`);
}
});
}
// Run tests
testDfsFindNode();
📚 Related LeetCode Problems
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/clone-graph/
https://leetcode.com/problems/pacific-atlantic-water-flow/
✅ JavaScript DFS Implementation (Recursive)
We’ll assume the graph is represented using an adjacency list:
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addNode(node) {
if (!this.adjacencyList.has(node)) {
this.adjacencyList.set(node, []);
}
}
addEdge(src, dest) {
if (!this.adjacencyList.has(src)) this.addNode(src);
if (!this.adjacencyList.has(dest)) this.addNode(dest);
this.adjacencyList.get(src).push(dest);
}
getNodes() {
return [...this.adjacencyList.keys()];
}
getNeighbors(node) {
return this.adjacencyList.get(node) || [];
}
getAdjacencyList() {
return this.adjacencyList;
}
}
/**
* Performs DFS to find targetNode starting from startNode in a Graph instance.
* @param {Graph} graph - Instance of the Graph class.
* @param {*} startNode - Node to start DFS from.
* @param {*} targetNode - Node to search for.
* @returns {boolean} - True if targetNode is found, else false.
*/
function dfsFindNode(graph, startNode, targetNode) {
const visited = new Set();
function dfs(node) {
if (node === targetNode) return true;
visited.add(node);
const neighbors = graph.adjacencyList.get(node) || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
if (dfs(neighbor)) return true;
}
}
return false;
}
if (!graph.adjacencyList.has(startNode)) {
// startNode doesn't exist in graph
return false;
}
return dfs(startNode);
}
🧪 Example Usage
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('E', 'F');
console.log(dfsFindNode(graph, 'A', 'F')); // true
console.log(dfsFindNode(graph, 'A', 'Z')); // false
⏱ Time and Space Complexity
Time Complexity: O(V + E)
V = vertices, E = edges (visit each node and edge once)
Space Complexity: O(V)
For the recursion stack and visited set
🔄 Alternate Approaches
🔁 Iterative DFS (using a stack)
Useful when you want to avoid recursion (e.g., due to call stack limits):
/**
* Iterative DFS to find targetNode starting from startNode in a Graph instance.
* @param {Graph} graph - Instance of the Graph class.
* @param {*} startNode - Node to start DFS from.
* @param {*} targetNode - Node to search for.
* @returns {boolean} - True if targetNode is found, else false.
*/
function dfsIterative(graph, startNode, targetNode) {
if (!graph.adjacencyList.has(startNode)) {
return false; // startNode doesn't exist in graph
}
const visited = new Set();
const stack = [startNode];
while (stack.length > 0) {
const node = stack.pop();
if (node === targetNode) return true;
if (!visited.has(node)) {
visited.add(node);
const neighbors = graph.adjacencyList.get(node) || [];
// Add neighbors to stack
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
return false;
}
Djikstra Shortest Path Algorithm in a Graph
Given a weighted graph represented as adjacency lists or edge lists, implement Dijkstra’s algorithm to find the shortest path from a source vertex to a target vertex.
/**
* Implements Dijkstra's algorithm to find shortest path distance from start to end.
* @param {Map} graph - Adjacency list represented as Map(node -> Array of [neighbor, weight])
* @param {*} start - Starting node
* @param {*} end - Target node
* @returns {number} - Shortest distance or -1 if no path exists
*/
function dijkstra(graph, start, end) {
// TODO: Implement the Dijkstra's algorithm here using MinHeap
// You can base your implementation on the provided code snippet above.
return -1;
}
🪜 Stepper Hints
🪂 Hint 1:
What’s a good way to explore the graph while always picking the shortest route discovered so far?
🧭 Hint 2:
You might need a way to track the minimum distance to each node from the start. Maybe use a map or array?
🔍 Hint 3:
Can you think of a structure that efficiently gives you the node with the smallest known distance?
🧠 Hint 4:
Try using a min-heap (priority queue) to always process the closest unvisited node.
🛠️ Final Hint:
Update the shortest distance to each neighbor if a better path is found through the current node. Continue this until the destination is reached or all nodes are processed.
// --- Test Cases ---
function testDijkstra() {
const testCases = [
{
graph: new Map([
['A', [['B', 1], ['C', 4]]],
['B', [['C', 2], ['D', 5]]],
['C', [['D', 1]]],
['D', []],
]),
start: 'A',
end: 'D',
expected: 4 // A->B->C->D: 1+2+1=4
},
{
graph: new Map([
['A', [['B', 1]]],
['B', [['A', 1]]],
]),
start: 'A',
end: 'C',
expected: -1 // No path to C
},
{
graph: new Map([
['X', [['Y', 7]]],
['Y', [['Z', 3]]],
['Z', [['X', 2]]],
]),
start: 'X',
end: 'Z',
expected: 10 // X->Y->Z: 7 + 3 = 10
},
{
graph: new Map([
['1', [['2', 2], ['3', 4]]],
['2', [['3', 1], ['4', 7]]],
['3', [['5', 3]]],
['4', [['6', 1]]],
['5', [['4', 2], ['6', 5]]],
['6', []],
]),
start: '1',
end: '6',
expected: 8 // 1->2->3->5->4->6 shortest path 2+1+3+2+1=9 (actually 8 by 1->3->5->4->6)
}
];
testCases.forEach(({ graph, start, end, expected }, i) => {
const result = dijkstra(graph, start, end);
const passed = result === expected;
console.log(`Test case ${i + 1}: ${passed ? 'PASSED' : 'FAILED'}`);
if (!passed) {
console.log(` Graph: ${JSON.stringify([...graph])}`);
console.log(` Start: ${start}, End: ${end}`);
console.log(` Expected: ${expected}, Got: ${result}`);
}
});
}
// Run the tests
testDijkstra();
📚 Related LeetCode Problems
https://leetcode.com/problems/network-delay-time/
https://leetcode.com/problems/path-with-minimum-effort/
https://leetcode.com/problems/cheapest-flights-within-k-stops/
https://leetcode.com/problems/path-with-maximum-probability/
✅ JavaScript Solution Using Priority Queue
We’ll build a simple MinHeap to support efficient extraction of the shortest path.
🧱 Priority Queue (MinHeap)
class Graph {
constructor() {
// Map node -> Array of [neighbor, weight]
this.adjacencyList = new Map();
}
addNode(node) {
if (!this.adjacencyList.has(node)) {
this.adjacencyList.set(node, []);
}
}
addEdge(src, dest, weight = 1) {
// Add nodes if they don't exist
if (!this.adjacencyList.has(src)) this.addNode(src);
if (!this.adjacencyList.has(dest)) this.addNode(dest);
// Add edge from src to dest with given weight
this.adjacencyList.get(src).push([dest, weight]);
}
getNodes() {
return [...this.adjacencyList.keys()];
}
getNeighbors(node) {
return this.adjacencyList.get(node) || [];
}
// Optional: to get the whole adjacency list for your dijkstra function
getAdjacencyList() {
return this.adjacencyList;
}
}
class MinHeap {
constructor() {
this.heap = [];
}
insert([node, dist]) {
this.heap.push([node, dist]);
this._bubbleUp(this.heap.length - 1);
}
extractMin() {
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this._sinkDown(0);
}
return min;
}
isEmpty() {
return this.heap.length === 0;
}
_bubbleUp(idx) {
const element = this.heap[idx];
while (idx > 0) {
const parentIdx = Math.floor((idx - 1) / 2);
const parent = this.heap[parentIdx];
if (element[1] >= parent[1]) break;
this.heap[parentIdx] = element;
this.heap[idx] = parent;
idx = parentIdx;
}
}
_sinkDown(idx) {
const length = this.heap.length;
const element = this.heap[idx];
while (true) {
let leftIdx = 2 * idx + 1;
let rightIdx = 2 * idx + 2;
let swap = null;
if (leftIdx < length) {
if (this.heap[leftIdx][1] < element[1]) swap = leftIdx;
}
if (rightIdx < length) {
if (
(swap === null && this.heap[rightIdx][1] < element[1]) ||
(swap !== null && this.heap[rightIdx][1] < this.heap[leftIdx][1])
) {
swap = rightIdx;
}
}
if (swap === null) break;
this.heap[idx] = this.heap[swap];
this.heap[swap] = element;
idx = swap;
}
}
}
🧭 Dijkstra’s Algorithm
function dijkstra(graph, start, end) {
const distances = new Map();
const visited = new Set();
const pq = new MinHeap();
for (let node of graph.keys()) {
distances.set(node, Infinity);
}
distances.set(start, 0);
pq.insert([start, 0]);
while (!pq.isEmpty()) {
const [currentNode, currentDist] = pq.extractMin();
if (visited.has(currentNode)) continue;
visited.add(currentNode);
if (currentNode === end) return currentDist;
for (const [neighbor, weight] of graph.get(currentNode) || []) {
if (!visited.has(neighbor)) {
const newDist = currentDist + weight;
if (newDist < distances.get(neighbor)) {
distances.set(neighbor, newDist);
pq.insert([neighbor, newDist]);
}
}
}
}
return distances.get(end) === Infinity ? -1 : distances.get(end);
}
🧪 Example Usage
const graph = new Graph();
graph.addEdge('A', 'B', 1);
graph.addEdge('A', 'C', 4);
graph.addEdge('B', 'C', 2);
graph.addEdge('B', 'D', 5);
graph.addEdge('C', 'D', 1);
graph.addNode('D');
console.log(dijkstra(graph, 'A', 'D')); // Output: 4 (A -> B -> C -> D)
⏱ Time and Space Complexity
Time Complexity:
Using MinHeap: O((V + E) log V)
Naive version (w/o heap): O(V^2)
Space Complexity: O(V) for distances, visited, and heap storage
🔁 Alternate Approaches
1. Bellman-Ford:
Works with negative weights.
Slower: O(V * E)
Use when graph has negative edge weights but no negative cycles.
- A* (A-star Search):
Uses a heuristic to optimize search (e.g., Euclidean distance in a grid).
More efficient than Dijkstra for pathfinding in physical maps.
Maximum Contiguous Subsequence
Given an integer array, find the contiguous subsequence (subarray) which has the largest sum. Return the maximum sum along with the start and end indices of that subsequence.
/**
* Finds the contiguous subarray with the largest sum.
* @param {number[]} nums - Input array of integers.
* @returns {{ maxSum: number, start: number, end: number }}
*/
function maxSubarrayWithIndices(nums) {
// TODO: Implement your logic here
return { maxSum: 0, start: -1, end: -1 };
}
🪜 Stepper Hints
🪂 Hint 1:
Think of walking through the array, keeping track of how much “gain” or “loss” you’ve had so far. When would you decide to restart?
🧭 Hint 2:
You can calculate the maximum sum that ends at each position — and keep track of the overall best you’ve seen so far.
🔍 Hint 3:
If the sum becomes negative at some point, what’s the impact on future subarrays that include this part?
📌 Hint 4:
Try keeping:
* currentSum: the best subarray ending at this index
* maxSum: the best sum you’ve ever seen
* Also store indices when currentSum starts and when a new maxSum is found.
// --- Test Cases ---
function testMaxSubarrayWithIndices() {
const testCases = [
{
input: [1, -2, 3, 4, -1, 2, 1, -5, 4],
expected: { maxSum: 9, start: 2, end: 6 }
},
{
input: [-3, -1, -2],
expected: { maxSum: -1, start: 1, end: 1 }
},
{
input: [5, 4, -1, 7, 8],
expected: { maxSum: 23, start: 0, end: 4 }
},
{
input: [1],
expected: { maxSum: 1, start: 0, end: 0 }
},
{
input: [],
expected: { maxSum: 0, start: -1, end: -1 }
},
{
input: [0, 0, 0, 0],
expected: { maxSum: 0, start: 0, end: 0 }
},
{
input: [-2, 1],
expected: { maxSum: 1, start: 1, end: 1 }
}
];
testCases.forEach(({ input, expected }, i) => {
const result = maxSubarrayWithIndices(input);
const pass = result.maxSum === expected.maxSum
&& result.start === expected.start
&& result.end === expected.end;
console.log(`Test case #${i + 1}: ${pass ? 'PASSED' : 'FAILED'}`);
if (!pass) {
console.log(` Input: ${JSON.stringify(input)}`);
console.log(` Expected: ${JSON.stringify(expected)}`);
console.log(` Got: ${JSON.stringify(result)}`);
}
});
}
// Run tests
testMaxSubarrayWithIndices();
📚 Related LeetCode Problem
https://leetcode.com/problems/maximum-subarray/
✅ JavaScript Implementation (Kadane + Indices)
/**
* Finds the contiguous subarray with the largest sum.
* @param {number[]} nums - Input array of integers.
* @returns {{ maxSum: number, start: number, end: number }}
*/
function maxSubarrayWithIndices(nums) {
if (!nums || nums.length === 0) return { maxSum: 0, start: -1, end: -1 };
let maxSum = nums[0];
let currentSum = nums[0];
let start = 0;
let end = 0;
let tempStart = 0;
for (let i = 1; i < nums.length; i++) {
if (currentSum + nums[i] < nums[i]) {
currentSum = nums[i];
tempStart = i;
} else {
currentSum += nums[i];
}
if (currentSum > maxSum) {
maxSum = currentSum;
start = tempStart;
end = i;
}
}
return { maxSum, start, end };
}
🧪 Example Usage
const result = maxSubarrayWithIndices([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
console.log(result);
// Output: { maxSum: 6, start: 3, end: 6 }
// Explanation: Subarray is [4, -1, 2, 1]
⏱ Time and Space Complexity
Time Complexity: O(n)
Single pass through the array.
Space Complexity: O(1)
Constant space, no extra data structures.
🔄 Alternate Approaches (Worth Knowing)
1. Divide and Conquer Approach
Time: O(n log n)
Rarely used in practice due to overhead, but theoretically interesting.
- Prefix Sum with Brute Force (for learning)
Try all subarrays — O(n²)
Only useful for teaching brute force vs optimized approaches.
Breadth First Search Algorithm for a Graph
Given a graph represented using adjacency lists, implement the Breadth First Search (BFS) algorithm starting from a given source vertex. Your function should traverse the graph level by level, visiting all vertices reachable from the source.
/**
* BFS traversal starting from the source node.
* @param {Map<any, any[]>} graph - adjacency list map of the graph
* @param {any} source - node to start BFS from
* @returns {any[]} - order of visited nodes
*/
function bfs(graph, source) {
// TODO: Implement BFS traversal here
// Hint: Use a queue and a visited set
return []; // stub
}
🪜 Stepper Hints
🪂 Hint 1:
Imagine you’re throwing a rock into a pond — how do ripples expand?
🧭 Hint 2:
Think of visiting all neighboring nodes before moving deeper. What data structure might help?
🔁 Hint 3:
Use a queue to manage the next node to explore. Each time you “dequeue,” look at its neighbors.
🚧 Hint 4:
You’ll need to mark visited nodes to prevent cycles or redundant processing.
/** ======= TEST CASES ======= */
function runTests() {
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('E', 'F');
// BFS from A should visit in level order
let result = bfs(graph.getAdjacencyList(), 'A');
console.assert(
JSON.stringify(result) === JSON.stringify(['A', 'B', 'C', 'D', 'E', 'F']),
`Test 1 Failed: got ${JSON.stringify(result)}`
);
// BFS from B should visit B, D, E, F
result = bfs(graph.getAdjacencyList(), 'B');
console.assert(
JSON.stringify(result) === JSON.stringify(['B', 'D', 'E', 'F']),
`Test 2 Failed: got ${JSON.stringify(result)}`
);
// BFS from a node not in the graph (should return just that node or empty)
result = bfs(graph.getAdjacencyList(), 'X');
console.assert(
JSON.stringify(result) === JSON.stringify(['X']),
`Test 3 Failed: got ${JSON.stringify(result)}`
);
// Empty graph test
const emptyGraph = new Graph();
result = bfs(emptyGraph.getAdjacencyList(), 'A');
console.assert(
JSON.stringify(result) === JSON.stringify(['A']),
`Test 4 Failed: got ${JSON.stringify(result)}`
);
console.log('All tests passed or assertions checked.');
}
runTests();
📚 Related LeetCode Problems
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/walls-and-gates/
https://leetcode.com/problems/rotting-oranges/
https://leetcode.com/problems/open-the-lock/
✅ JavaScript BFS Implementation
We’ll write a function that takes:
* a graph (adjacency list as a Map)
* a source node
* and returns the order of visited nodes.
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addNode(node) {
if (!this.adjacencyList.has(node)) {
this.adjacencyList.set(node, []);
}
}
addEdge(src, dest) {
if (!this.adjacencyList.has(src)) this.addNode(src);
if (!this.adjacencyList.has(dest)) this.addNode(dest);
this.adjacencyList.get(src).push(dest);
}
getNodes() {
return [...this.adjacencyList.keys()];
}
getNeighbors(node) {
return this.adjacencyList.get(node) || [];
}
getAdjacencyList() {
return this.adjacencyList;
}
}
/**
* Performs BFS traversal on a graph from the given source.
* @param {Map<any, any[]>} graph - Adjacency list representation of the graph.
* @param {any} source - Starting vertex.
* @returns {any[]} Order of nodes visited during BFS.
*/
function bfs(graph, source) {
const visited = new Set();
const queue = [];
const result = [];
queue.push(source);
visited.add(source);
while (queue.length > 0) {
const current = queue.shift();
result.push(current);
for (const neighbor of graph.get(current) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
return result;
}
🧪 Example Usage:
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('C', 'F');
graph.addEdge('E', 'F');
console.log(bfs(graph, 'A'));
// Output: ['A', 'B', 'C', 'D', 'E', 'F']
⏱ Time & Space Complexity:
Let:
V = number of vertices
E = number of edges
Time Complexity: O(V + E)
Every node and edge is visited once.
Space Complexity: O(V)
For visited, queue, and result.
🔄 Alternate Approaches:
1. DFS (Depth-First Search)
Uses a stack or recursion.
Explores deeply before backing out.
BFS is better for shortest paths in unweighted graphs.
- BFS for Shortest Path
Add a distance map to track levels from the source.
Great for finding minimum number of steps.
✅ Bonus: BFS with Distance Tracking
function bfsWithDistances(graph, source) {
const visited = new Set();
const queue = [[source, 0]];
const distances = new Map();
visited.add(source);
distances.set(source, 0);
while (queue.length > 0) {
const [current, dist] = queue.shift();
for (const neighbor of graph.get(current) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
distances.set(neighbor, dist + 1);
queue.push([neighbor, dist + 1]);
}
}
}
return distances;
}
Even Split
Given an array of integers, determine if it is possible to split the array into two parts such that the sum of all elements in each part is the same.
/**
* Given an array of integers, determine if it is possible to split
* the array into two parts such that the sum of all elements in each part is the same.
*
* @param {number[]} nums - Array of integers
* @returns {boolean} - true if such a split is possible, false otherwise
*/
function canPartition(nums) {
// TODO: Implement your logic here
return false;
}
🪜 Stepper Hints
🪂 Hint 1:
If you’re trying to divide something into two equal parts — what’s the very first thing to check?
🧭 Hint 2:
Is it even mathematically possible for the total sum to be evenly split?
🧩 Hint 3:
Think of this like a subset sum problem — can you pick a combination of elements that adds up to half the total?
🧰 Hint 4:
Try using a boolean array to represent which sums can be achieved using subsets of elements you’ve seen so far.
// --- Test Cases ---
function testCanPartition() {
const testCases = [
{ input: [1, 2, 3, 3], expected: true }, // 1+2+3 == 3
{ input: [1, 1, 1, 1, 1, 1], expected: true }, // sum=6, split into two 3 sums
{ input: [1, 2, 3, 4, 5], expected: false }, // total sum 15, no equal split
{ input: [10, 10], expected: true }, // split into [10], [10]
{ input: [5], expected: false }, // cannot split single element
{ input: [], expected: true }, // empty array split trivially
{ input: [0, 0, 0, 0], expected: true }, // all zeros can split
{ input: [-1, 1, 0], expected: true }, // -1+1=0
{ input: [100, 200, 300, 600], expected: false }, // sum=1200, no equal split
];
testCases.forEach(({ input, expected }, i) => {
const result = canPartition(input);
const pass = result === expected;
console.log(`Test case #${i + 1}: ${pass ? 'PASSED' : 'FAILED'}`);
if (!pass) {
console.log(` Input: ${JSON.stringify(input)}`);
console.log(` Expected: ${expected}, Got: ${result}`);
}
});
}
// Run tests
testCanPartition();
📚 Related LeetCode Problem
https://leetcode.com/problems/partition-equal-subset-sum/
✅ JavaScript Solution
We’ll solve this using bottom-up dynamic programming to track which sums are possible.
/**
* Determines if the array can be split into two parts with equal sum.
* @param {number[]} nums
* @return {boolean}
*/
function canPartition(nums) {
const totalSum = nums.reduce((sum, num) => sum + num, 0);
// Early exit: can't split if total sum is odd
if (totalSum % 2 !== 0) return false;
const target = totalSum / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
// Traverse backwards to avoid overwriting results
for (let i = target; i >= num; i--) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
🧪 Example Usage:
console.log(canPartition([1, 5, 11, 5])); // true console.log(canPartition([1, 2, 3, 5])); // false
⏱ Time and Space Complexity
Let:
n = nums.length
target = totalSum / 2
Time Complexity: O(n * target)
Space Complexity: O(target) (due to space optimization)
🔄 Alternate Approaches
1. Recursive + Memoization (Top-Down DP)
Good for learning, but not space-optimal and may hit recursion depth for large inputs.
- Bitset Optimization (Advanced)
For very large inputs with small values, bit manipulation can replace the boolean array for faster subset checking. - Meet-in-the-middle (For huge arrays)
Split the array in half, generate all subset sums for each half, and check if any pair sums to the target.
