Coding Problems & Solutions

Longest Common Prefix

Find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "".

Core Idea: Vertical Scan (Character by Character Comparison)

The most intuitive and efficient approach is to compare the strings character by character, from left to right. We assume the first string is our initial candidate for the common prefix, and then we verify this prefix against all other strings.

Algorithm Steps:

1. Handle Edge Cases: If the input array is empty, return `""`. If it contains only one string, return that string.
2. Iterate Vertically (Character by Character): Use the first string (`strs[0]`) as a reference. Loop `charIndex` from `0` up to `strs[0].length - 1`.
3. Compare Across All Strings (Inner Loop): For each `charIndex`, iterate `strIndex` from `1` to `strs.length - 1`.
   • Check for End of String or Mismatch: If `charIndex` is equal to `strs[strIndex].length` (current string is shorter) OR `strs[strIndex][charIndex]` is not equal to `strs[0][charIndex]` (mismatch), then the common prefix ends here. Return `strs[0].substring(0, charIndex)`.
4. All Characters Matched: If the outer loop completes, `strs[0]` itself is the longest common prefix. Return `strs[0]`.

JavaScript Code:

/**
 * @param {string[]} strs
 * @return {string}
 */
function longestCommonPrefix(strs) {
    if (strs.length === 0) {
        return "";
    }
    if (strs.length === 1) {
        return strs[0];
    }

    for (let charIndex = 0; charIndex < strs[0].length; charIndex++) {
        const currentChar = strs[0][charIndex];

        for (let strIndex = 1; strIndex < strs.length; strIndex++) {
            if (charIndex === strs[strIndex].length || strs[strIndex][charIndex] !== currentChar) {
                return strs[0].substring(0, charIndex);
            }
        }
    }
    return strs[0];
}

Back to Top

Reverse Words in a String

Given an input string `s`, reverse the order of the words. Words are separated by at least one space. Return a string of words in reverse order concatenated by a single space, with no extra spaces.

Core Idea: Split, Filter, Reverse, Join

The most straightforward way is to split the string into words, filter out empty strings, reverse the array of words, and then join them back.

Algorithm Steps:

1. Split the string into words: Use `s.split(/\s+/)` to split by one or more whitespace characters. This handles multiple spaces and trims leading/trailing spaces automatically.
2. Reverse the order of words: Use `words.reverse()`.
3. Join the words back into a single string: Use `words.join(' ')`.

JavaScript Code:

/**
 * @param {string} s
 * @return {string}
 */
function reverseWords(s) {
    const words = s.split(/\s+/);
    words.reverse();
    return words.join(' ');
}

Alternative Core Idea: Two-Pointer Approach (More "In-Place")

This method involves cleaning spaces, reversing the entire character array, then reversing each word individually.

Algorithm Steps (Two-Pointer):

1. Clean up spaces: Create a helper `cleanSpaces(s)` to return a character array with single spaces between words and no leading/trailing spaces.
2. Reverse the entire string: Use a `reverseCharRange(arr, start, end)` helper to reverse the entire `charArray`.
3. Reverse each word: Iterate through the `charArray`, identify each word (sequence of non-space characters), and use `reverseCharRange` to reverse each word in place.
4. Join and return: Convert the `charArray` back to a string.

JavaScript Code (Two-Pointer):

/**
 * Helper function to clean up spaces:
 * - Removes leading/trailing spaces.
 * - Reduces multiple spaces between words to a single space.
 * @param {string} s - The input string.
 * @returns {character[]} - A character array with cleaned spaces.
 */
function cleanSpaces(s) {
    let left = 0;
    let right = s.length - 1;

    while (left <= right && s[left] === ' ') {
        left++;
    }
    while (left <= right && s[right] === ' ') {
        right--;
    }

    const charArray = [];
    for (let i = left; i <= right; i++) {
        if (s[i] !== ' ') {
            charArray.push(s[i]);
        } else if (charArray.length > 0 && charArray[charArray.length - 1] !== ' ') {
            charArray.push(' ');
        }
    }
    return charArray;
}

/**
 * Helper function to reverse characters within a specified range in an array in-place.
 * @param {character[]} arr - The character array.
 * @param {number} start - The starting index of the range (inclusive).
 * @param {number} end - The ending index of the range (inclusive).
 */
function reverseCharRange(arr, start, end) {
    while (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]];
        start++;
        end--;
    }
}

/**
 * @param {string} s
 * @return {string}
 */
function reverseWordsTwoPointer(s) {
    const charArray = cleanSpaces(s);
    if (charArray.length === 0) {
        return "";
    }

    reverseCharRange(charArray, 0, charArray.length - 1);

    let wordStart = 0;
    while (wordStart < charArray.length) {
        let wordEnd = wordStart;
        while (wordEnd < charArray.length && charArray[wordEnd] !== ' ') {
            wordEnd++;
        }
        reverseCharRange(charArray, wordStart, wordEnd - 1);
        wordStart = wordEnd + 1;
    }
    return charArray.join('');
}

Back to Top

Find the Index of the First Occurrence in a String (`strStr`)

Given two strings `needle` and `haystack`, return the index of the first occurrence of `needle` in `haystack`, or `-1` if `needle` is not part of `haystack`.

Core Idea: Brute-Force (Window Sliding and Comparison)

Slide a window of `needle`'s length across `haystack` and compare the substring within that window to `needle`.

Algorithm Steps:

1. Handle Edge Cases: If `needle` is empty, return `0`. If `haystack` is shorter than `needle`, return `-1`.
2. Iterate Through `haystack` (Outer Loop): Use `i` for potential starting positions from `0` up to `haystack.length - needle.length`.
3. Compare Substring (Inner Loop): For each `i`, use `j` from `0` to `needle.length - 1`. Compare `haystack[i + j]` with `needle[j]`. If a mismatch, `break` inner loop.
4. Found Match: If inner loop completes, return `i`.
5. No Match: If outer loop completes, return `-1`.

JavaScript Code:

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
function strStr(haystack, needle) {
    if (needle.length === 0) {
        return 0;
    }
    if (haystack.length < needle.length) {
        return -1;
    }

    for (let i = 0; i <= haystack.length - needle.length; i++) {
        let match = true;
        for (let j = 0; j < needle.length; j++) {
            if (haystack[i + j] !== needle[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            return i;
        }
    }
    return -1;
}

Back to Top

Ransom Note

Given two strings `ransomNote` and `magazine`, return `true` if `ransomNote` can be constructed by using the letters from `magazine` and `false` otherwise. Each letter in `magazine` can only be used once in `ransomNote`.

Core Idea: Character Frequency Counting

Count character frequencies in `magazine`, then "consume" them while iterating through `ransomNote`. Order does not matter.

Algorithm Steps:

1. Initial Length Check: If `ransomNote.length > magazine.length`, return `false`.
2. Build Frequency Map for `magazine`: Store counts of each character.
3. Decrement Counts Using `ransomNote`: Iterate through `ransomNote`. For each character, decrement its count in the map. If a character is not found or its count is 0, return `false`.
4. Return `true`: If loop completes, `ransomNote` can be constructed.

JavaScript Code:

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
function canConstruct(ransomNote, magazine) {
    if (ransomNote.length > magazine.length) { // Optimization
        return false;
    }
    const magazineFreqMap = new Map();
    for (const char of magazine) {
        magazineFreqMap.set(char, (magazineFreqMap.get(char) || 0) + 1);
    }

    for (const charOfNote of ransomNote) {
        if (!magazineFreqMap.has(charOfNote) || magazineFreqMap.get(charOfNote) === 0) {
            return false;
        }
        magazineFreqMap.set(charOfNote, magazineFreqMap.get(charOfNote) - 1);
    }
    return true;
}

Back to Top

Find the Difference

Given two strings `s` and `t`. String `t` is generated by random shuffling string `s` and then add one more letter at a random position. Return the letter that was added to `t`.

Core Idea: Bitwise XOR

XORing all character codes in `s` and `t` will cancel out common characters, leaving only the added one.

Algorithm Steps (XOR):

1. Initialize `charCodeSum = 0`.
2. XOR `charCodeSum` with ASCII value of each char in `s`.
3. XOR `charCodeSum` with ASCII value of each char in `t`.
4. Convert final `charCodeSum` back to a character.

JavaScript Code (XOR):

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
function findTheDifference(s, t) {
    let charCodeSum = 0;
    for (let i = 0; i < s.length; i++) {
        charCodeSum ^= s.charCodeAt(i);
    }
    for (let i = 0; i < t.length; i++) {
        charCodeSum ^= t.charCodeAt(i);
    }
    return String.fromCharCode(charCodeSum);
}

Alternative Core Idea: Frequency Map

Count frequencies in `s`, then decrement using `t`. The character that causes a count to go to zero or negative is the added one.

JavaScript Code (Frequency Map):

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
function findTheDifferenceMap(s, t) {
    const charCounts = new Map();
    for (const char of s) {
        charCounts.set(char, (charCounts.get(char) || 0) + 1);
    }
    for (const char of t) {
        if (!charCounts.has(char) || charCounts.get(char) === 0) {
            return char;
        }
        charCounts.set(char, charCounts.get(char) - 1);
    }
    return ''; // Should not be reached
}

Back to Top

Keyboard Row

Given an array of strings `words`, return the words that can be typed using letters of the alphabet on only one row of American keyboard. Case-insensitive.

Core Idea: Pre-map Characters to Rows and Validate Each Word

Create a map from characters to their keyboard row. Then, for each word, check if all its characters belong to the same row.

Algorithm Steps:

1. Create a Character-to-Row Map: Map lowercase 'q' to 1, 'a' to 2, 'z' to 3, etc.
2. Iterate Through `words` Array: For each `word`:
   • Convert `word` to lowercase.
   • Determine `expectedRow` from its first character.
   • Validate remaining characters: If any character's row doesn't match `expectedRow`, mark word as invalid and `break`.
   • If valid, add original `word` to result.
3. Return `resultWords`.

JavaScript Code:

/**
 * @param {string[]} words
 * @return {string[]}
 */
function findWords(words) {
    const resultWords = [];
    const charToRowMap = new Map();

    "qwertyuiop".split('').forEach(char => charToRowMap.set(char, 1));
    "asdfghjkl".split('').forEach(char => charToRowMap.set(char, 2));
    "zxcvbnm".split('').forEach(char => charToRowMap.set(char, 3));

    for (const word of words) {
        if (word.length === 0) continue;

        const lowerCaseWord = word.toLowerCase();
        const expectedRow = charToRowMap.get(lowerCaseWord[0]);
        if (expectedRow === undefined) continue; // Should not happen with letter inputs

        let isValidWord = true;
        for (let i = 1; i < lowerCaseWord.length; i++) {
            const char = lowerCaseWord[i];
            const actualRow = charToRowMap.get(char);
            if (actualRow !== expectedRow) {
                isValidWord = false;
                break;
            }
        }
        if (isValidWord) {
            resultWords.push(word);
        }
    }
    return resultWords;
}

Back to Top

Isomorphic Strings

Given two strings `s` and `t`, determine if they are isomorphic. Isomorphic means characters in `s` can be replaced to get `t`, preserving order, with consistent and unique mappings.

Core Idea: Using Two Hash Maps for Bi-directional Mapping

Use two maps: `sToTMap` (s char to t char) and `tToSMap` (t char to s char) to ensure both consistency and uniqueness of mappings.

Algorithm Steps:

1. Initial Check: If `s.length !== t.length`, return `false`.
2. Initialize Maps: `sToTMap = new Map()`, `tToSMap = new Map()`.
3. Iterate and Map: Loop `i` from `0` to `s.length - 1`.
   • Get `sChar = s[i]`, `tChar = t[i]`.
   • If `sToTMap.has(sChar)`: Check `sToTMap.get(sChar) === tChar`. If not, return `false`.
   • Else (`sChar` is new): Check `tToSMap.has(tChar)`. If true, return `false` (violates unique mapping). Else, set `sToTMap.set(sChar, tChar)` and `tToSMap.set(tChar, sChar)`.
4. Return `true`: If loop completes.

JavaScript Code:

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
function isIsomorphic(s, t) {
    if (s.length !== t.length) {
        return false;
    }

    const sToTMap = new Map();
    const tToSMap = new Map();

    for (let i = 0; i < s.length; i++) {
        const sChar = s[i];
        const tChar = t[i];

        if (sToTMap.has(sChar)) {
            if (sToTMap.get(sChar) !== tChar) {
                return false;
            }
        } else {
            if (tToSMap.has(tChar)) {
                return false;
            }
            sToTMap.set(sChar, tChar);
            tToSMap.set(tChar, sChar);
        }
    }
    return true;
}

Back to Top

Word Pattern

Given a `pattern` and a string `s`, find if `s` follows the same pattern. A bijection must exist between a letter in `pattern` and a non-empty word in `s`.

Core Idea: Using Two Hash Maps for Bi-directional Mapping (Char to Word)

Similar to Isomorphic Strings, but mapping characters to words. Use `charToWord` and `wordToChar` maps.

Algorithm Steps:

1. Split `s` into words.
2. Initial Length Check: If `pattern.length !== words.length`, return `false`.
3. Initialize Maps: `charToWord = new Map()`, `wordToChar = new Map()`.
4. Iterate and Validate: Loop `i` from `0` to `pattern.length - 1`.
   • Get `pChar = pattern[i]`, `currentWord = words[i]`.
   • If `charToWord.has(pChar)`: Check `charToWord.get(pChar) === currentWord`. If not, return `false`.
   • Else (`pChar` is new): Check `wordToChar.has(currentWord)`. If true, return `false`. Else, set `charToWord.set(pChar, currentWord)` and `wordToChar.set(currentWord, pChar)`.
5. Return `true`: If loop completes.

JavaScript Code:

/**
 * @param {string} pattern
 * @param {string} s
 * @return {boolean}
 */
function wordPattern(pattern, s) {
    const words = s.split(' ');
    if (pattern.length !== words.length) {
        return false;
    }

    const charToWord = new Map();
    const wordToChar = new Map();

    for (let i = 0; i < pattern.length; i++) {
        const pChar = pattern[i];
        const currentWord = words[i];

        if (charToWord.has(pChar)) {
            if (charToWord.get(pChar) !== currentWord) {
                return false;
            }
        } else {
            if (wordToChar.has(currentWord)) {
                return false;
            }
            charToWord.set(pChar, currentWord);
            wordToChar.set(currentWord, pChar);
        }
    }
    return true;
}

Back to Top

Minimum Size Subarray Sum

Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a subarray whose sum is greater than or equal to `target`. If no such subarray, return `0`.

Core Idea: Sliding Window

Use two pointers (`left`, `right`) to define a window. Expand the window by moving `right`. When sum meets target, shrink from `left` to find minimum length, updating `minLength` along the way.

Algorithm Steps:

1. Initialize: `left = 0`, `currentSum = 0`, `minLength = Infinity`.
2. Expand Window: Loop `right` from `0` to `nums.length - 1`. Add `nums[right]` to `currentSum`.
3. Shrink Window: While `currentSum >= target`:
   • Update `minLength = min(minLength, right - left + 1)`.
   • Subtract `nums[left]` from `currentSum`.
   • Increment `left`.
4. Return: If `minLength` is `Infinity`, return `0`, else `minLength`.

JavaScript Code:

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
function minSubArrayLen(target, nums) {
    let left = 0;
    let currentSum = 0;
    let minLength = Infinity;

    for (let right = 0; right < nums.length; right++) {
        currentSum += nums[right];

        while (currentSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            currentSum -= nums[left];
            left++;
        }
    }
    return minLength === Infinity ? 0 : minLength;
}

Back to Top

Height Checker

Given `heights` (current order) and `expected` (sorted order), return the number of indices where `heights[i] != expected[i]`.

Core Idea (Optimal): Counting Sort Principles

Leverage the small, fixed range of heights (1-100) to count frequencies and implicitly reconstruct the sorted order without a full sort.

Algorithm Steps (Optimal):

1. Count Frequencies: Create `heightCounts` array (size 101) and populate it by iterating `heights`.
2. Compare and Count Mismatches:
   • Initialize `mismatches = 0`, `currentHeightsIndex = 0`.
   • Loop `expectedHeight` from `1` to `100`.
   • While `heightCounts[expectedHeight] > 0`:
     • If `heights[currentHeightsIndex] !== expectedHeight`, increment `mismatches`.
     • Decrement `heightCounts[expectedHeight]`.
     • Increment `currentHeightsIndex`.
3. Return `mismatches`.

JavaScript Code (Optimal):

/**
 * @param {number[]} heights
 * @return {number}
 */
function heightCheckerOptimal(heights) {
    let mismatches = 0;
    const heightCounts = new Array(101).fill(0);
    for (const height of heights) {
        heightCounts[height]++;
    }

    let currentHeightsIndex = 0;
    for (let expectedHeight = 1; expectedHeight <= 100; expectedHeight++) {
        while (heightCounts[expectedHeight] > 0) {
            if (heights[currentHeightsIndex] !== expectedHeight) {
                mismatches++;
            }
            heightCounts[expectedHeight]--;
            currentHeightsIndex++;
        }
    }
    return mismatches;
}

Back to Top

Intersection of Two Arrays

Given two integer arrays `nums1` and `nums2`, return an array of their intersection. Each element in the result must be unique.

Core Idea: Using a Hash Set

Convert one array into a hash set for $O(1)$ average time lookups, then iterate through the second array, adding common elements to a result set.

Algorithm Steps:

1. Create a Hash Set from `nums1`: Add all unique elements of `nums1` to `nums1Set`.
2. Find Intersections with `nums2`: Create `intersectionSet`. Iterate `nums2`. If `nums1Set.has(num)`, add `num` to `intersectionSet`.
3. Convert to Array and Return: Convert `intersectionSet` to an array.

JavaScript Code:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
function intersection(nums1, nums2) {
    const nums1Set = new Set(nums1);
    const intersectionSet = new Set();

    for (const num of nums2) {
        if (nums1Set.has(num)) {
            intersectionSet.add(num);
        }
    }
    return Array.from(intersectionSet);
}

Back to Top

Valid Parentheses

Given a string `s` containing just `'(', ')', '{', '}', '['` and `']'`, determine if the input string is valid (brackets closed by same type, in correct order, every close has open).

Core Idea: Using a Stack

A stack's LIFO property perfectly matches parenthesis matching: the most recently opened bracket must be the first one closed.

Algorithm Steps:

1. Initialize a Stack: An empty array.
2. Define Mappings: `bracketMap = {'(': ')', '{': '}', '[': ']'}`.
3. Iterate Through String: For each `char` in `s`:
   • If `char` is an opening bracket, `push` it onto the stack.
   • If `char` is a closing bracket:
     • If stack is empty, return `false`.
     • `pop` `lastOpenBracket`. If `bracketMap[lastOpenBracket] !== char`, return `false`.
4. Final Check: If stack is empty, return `true`. Else, return `false`.

JavaScript Code:

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {
    const stack = [];
    const bracketMap = {
        '(': ')',
        '{': '}',
        '[': ']'
    };

    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        if (bracketMap.hasOwnProperty(char)) {
            stack.push(char);
        } else {
            if (stack.length === 0) {
                return false;
            }
            const lastOpenBracket = stack.pop();
            if (bracketMap[lastOpenBracket] !== char) {
                return false;
            }
        }
    }
    return stack.length === 0;
}

Back to Top

Design HashMap

Implement `MyHashMap` with `put(key, value)`, `get(key)`, `remove(key)` without using built-in hash table libraries.

Core Idea: Separate Chaining with Array of Lists

Use an underlying array of "buckets". Each bucket stores a list of `[key, value]` pairs to handle collisions. A simple modulo hash function is used.

Algorithm Steps:

1. `constructor()`: Initialize `BUCKET_SIZE` (e.g., 1000) and `buckets` array, filling each with an empty array.
2. `_hash(key)`: Private helper `return key % this.BUCKET_SIZE;`.
3. `put(key, value)`:
   • Get `index = _hash(key)`.
   • Iterate `bucket[index]`. If `key` found, update `value` and return.
   • Else, `push([key, value])` to `bucket[index]`.
4. `get(key)`:
   • Get `index = _hash(key)`.
   • Iterate `bucket[index]`. If `key` found, return `value`.
   • Else, return `-1`.
5. `remove(key)`:
   • Get `index = _hash(key)`.
   • Iterate `bucket[index]`. If `key` found, `splice(i, 1)` and return.

JavaScript Code:

class MyHashMap {
    constructor() {
        this.BUCKET_SIZE = 1000;
        this.buckets = new Array(this.BUCKET_SIZE);
        for (let i = 0; i < this.BUCKET_SIZE; i++) {
            this.buckets[i] = [];
        }
    }

    _hash(key) {
        return key % this.BUCKET_SIZE;
    }

    put(key, value) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            const pair = bucket[i];
            if (pair[0] === key) {
                pair[1] = value;
                return;
            }
        }
        bucket.push([key, value]);
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            const pair = bucket[i];
            if (pair[0] === key) {
                return pair[1];
            }
        }
        return -1;
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            const pair = bucket[i];
            if (pair[0] === key) {
                bucket.splice(i, 1);
                return;
            }
        }
    }
}

Back to Top

Replace Words

Given a `dictionary` of roots and a `sentence`, replace all derivatives in the sentence with the shortest root forming it. Return the sentence after replacement.

Core Idea: Trie (Prefix Tree) for Efficient Root Lookup

A Trie allows efficient prefix matching and naturally helps find the shortest root by stopping at the first `isEndOfWord` node encountered during traversal.

Algorithm Steps:

1. Build the Trie: Insert all `rootWord`s from `dictionary` into a Trie. Mark `isEndOfWord` at the end of each root.
2. Process the Sentence: Split `sentence` into `wordsInSentence`.
3. Replace Derivatives: For each `word` in `wordsInSentence`:
   • Traverse the Trie character by character using `word`'s prefix.
   • If `currentNode.isEndOfWord` is `true`, set `foundRoot` to the current prefix and `break` (shortest root found).
   • If a character is not found in Trie, `break` (no root for this prefix).
   • Add `foundRoot` (if any) or original `word` to `resultWords`.
4. Join and Return: Join `resultWords` with spaces.

JavaScript Code:

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {string}
 */
function replaceWords(dictionary, sentence) {
    const root = new TrieNode();
    for (const rootWord of dictionary) {
        let currentNode = root;
        for (const char of rootWord) {
            if (!currentNode.children[char]) {
                currentNode.children[char] = new TrieNode();
            }
            currentNode = currentNode.children[char];
        }
        currentNode.isEndOfWord = true;
    }

    const wordsInSentence = sentence.split(' ');
    const resultWords = [];

    for (const word of wordsInSentence) {
        let currentNode = root;
        let foundRoot = null;

        for (let charIndex = 0; charIndex < word.length; charIndex++) {
            const char = word[charIndex];
            if (!currentNode.children[char]) {
                break;
            }
            currentNode = currentNode.children[char];
            if (currentNode.isEndOfWord) {
                foundRoot = word.substring(0, charIndex + 1);
                break;
            }
        }
        if (foundRoot !== null) {
            resultWords.push(foundRoot);
        } else {
            resultWords.push(word);
        }
    }
    return resultWords.join(' ');
}

Back to Top

Add Two Numbers (Linked List)

Given two non-empty linked lists representing two non-negative integers (digits in reverse order), add them and return the sum as a linked list.

Core Idea: Iterative Addition with Carry

Simulate manual addition by iterating through both lists simultaneously, adding digits and managing a carry-over.

Algorithm Steps:

1. Define `ListNode` Structure: `val`, `next`.
2. Initialize: `dummyHead = new ListNode(0)`, `current = dummyHead`, `carry = 0`.
3. Traverse and Add: Loop while `p1 || p2 || carry`.
   • Get `digit1 = p1 ? p1.val : 0`, `digit2 = p2 ? p2.val : 0`.
   • Calculate `sum = digit1 + digit2 + carry`.
   • `newDigit = sum % 10`, `carry = Math.floor(sum / 10)`.
   • `current.next = new ListNode(newDigit)`, `current = current.next`.
   • Move `p1 = p1.next`, `p2 = p2.next` (if not null).
4. Return `dummyHead.next`.

JavaScript Code:

// Definition for singly-linked list.
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function addTwoNumbers(l1, l2) {
    const dummyHead = new ListNode(0);
    let current = dummyHead;

    let p1 = l1;
    let p2 = l2;
    let carry = 0;

    while (p1 !== null || p2 !== null || carry !== 0) {
        const digit1 = p1 ? p1.val : 0;
        const digit2 = p2 ? p2.val : 0;

        const sum = digit1 + digit2 + carry;

        const newDigit = sum % 10;
        carry = Math.floor(sum / 10);

        current.next = new ListNode(newDigit);
        current = current.next;

        if (p1) {
            p1 = p1.next;
        }
        if (p2) {
            p2 = p2.next;
        }
    }
    return dummyHead.next;
}

Back to Top

Happy Number

Determine if a number `n` is happy. A happy number eventually reaches 1 when repeatedly replaced by the sum of the squares of its digits. Non-happy numbers loop endlessly in a cycle not including 1.

Core Idea: Detecting Cycles (Hash Set)

Use a hash set to keep track of numbers encountered. If a number repeats, it's in a cycle and not happy.

Algorithm Steps:

1. Helper `getNext(num)`: Returns sum of squares of digits.
2. Main `isHappy(n)`:
   • Initialize `seenNumbers = new Set()`.
   • Loop `while (n !== 1 && !seenNumbers.has(n))`:
     • `seenNumbers.add(n)`.
     • `n = getNext(n)`.
   • Return `n === 1`.

JavaScript Code:

/**
 * @param {number} n
 * @return {boolean}
 */
function isHappy(n) {
    const getNext = (num) => {
        let totalSum = 0;
        while (num > 0) {
            let digit = num % 10;
            totalSum += digit * digit;
            num = Math.floor(num / 10);
        }
        return totalSum;
    };

    const seenNumbers = new Set();
    while (n !== 1 && !seenNumbers.has(n)) {
        seenNumbers.add(n);
        n = getNext(n);
    }
    return n === 1;
}

Back to Top

Roman to Integer

Given a Roman numeral string, convert it to an integer. Handle subtractive forms (IV, IX, XL, XC, CD, CM).

Core Idea: Iterate from Left to Right, Checking for Subtractive Cases

Use a value map for symbols. Iterate, if current value is less than next value, subtract; otherwise, add.

Algorithm Steps:

1. Create a Value Map: `{'I': 1, 'V': 5, ...}`.
2. Initialize `total = 0`.
3. Iterate Through String: Loop `i` from `0` to `s.length - 1`.
   • Get `currentValue = romanValues.get(s[i])`.
   • Get `nextValue = romanValues.get(s[i+1])` (if `s[i+1]` exists).
   • If `currentValue < nextValue`, `total -= currentValue`.
   • Else, `total += currentValue`.
4. Return `total`.

JavaScript Code:

/**
 * @param {string} s
 * @return {number}
 */
function romanToInt(s) {
    const romanValues = new Map([
        ['I', 1], ['V', 5], ['X', 10], ['L', 50],
        ['C', 100], ['D', 500], ['M', 1000]
    ]);
    let total = 0;
    for (let i = 0; i < s.length; i++) {
        const currentValue = romanValues.get(s[i]);
        const nextValue = (i + 1 < s.length) ? romanValues.get(s[i + 1]) : 0;

        if (currentValue < nextValue) {
            total -= currentValue;
        } else {
            total += currentValue;
        }
    }
    return total;
}

Back to Top

Integer to Roman

Given an integer, convert it to a Roman numeral. Follow rules for additive and subtractive forms.

Core Idea: Greedy Approach with Predefined Mappings

Use an ordered list of Roman numeral values and symbols (including subtractive forms) from largest to smallest. Greedily subtract the largest possible value from the number.

Algorithm Steps:

1. Create Ordered Mappings: An array of `{value, symbol}` objects, sorted descending (e.g., `{1000, "M"}, {900, "CM"}, ... {1, "I"}`).
2. Initialize `romanNumeral = ""`.
3. Iterate and Subtract: For each `pair` in `romanMap`:
   • While `num >= pair.value`:
     • `romanNumeral += pair.symbol`.
     • `num -= pair.value`.
4. Return `romanNumeral`.

JavaScript Code:

/**
 * @param {number} num
 * @return {string}
 */
function intToRoman(num) {
    const romanMap = [
        { value: 1000, symbol: "M" }, { value: 900, symbol: "CM" },
        { value: 500, symbol: "D" }, { value: 400, symbol: "CD" },
        { value: 100, symbol: "C" }, { value: 90, symbol: "XC" },
        { value: 50, symbol: "L" }, { value: 40, symbol: "XL" },
        { value: 10, symbol: "X" }, { value: 9, symbol: "IX" },
        { value: 5, symbol: "V" }, { value: 4, symbol: "IV" },
        { value: 1, symbol: "I" }
    ];
    let romanNumeral = "";
    for (const pair of romanMap) {
        while (num >= pair.value) {
            romanNumeral += pair.symbol;
            num -= pair.value;
        }
    }
    return romanNumeral;
}

Back to Top

Spiral Matrix

Given an `m x n` matrix, return all elements of the matrix in spiral order.

Core Idea: Boundary Tracking with Four Pointers

Use `top`, `bottom`, `left`, `right` pointers to define boundaries. "Peel off" layers of the matrix (right, down, left, up) and shrink boundaries until all elements are visited.

Algorithm Steps:

1. Initialize: `result = []`, `top=0`, `bottom=m-1`, `left=0`, `right=n-1`. Handle empty matrix.
2. Main Loop: `while (top <= bottom && left <= right)`:
   • Right: `for c from left to right`, `result.push(matrix[top][c])`; `top++`.
   • Down: `for r from top to bottom`, `result.push(matrix[r][right])`; `right--`.
   • Left: `for c from right down to left`, `result.push(matrix[bottom][c])`; `bottom--`.
   • Up: `for r from bottom down to top`, `result.push(matrix[r][left])`; `left++`.
   • **Crucial:** Add `if (top > bottom) break;` or `if (left > right) break;` after each horizontal/vertical traversal to handle single-row/column cases and termination.
3. Return `result`.

JavaScript Code:

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
function spiralOrder(matrix) {
    const result = [];
    const m = matrix.length;
    if (m === 0) return result;
    const n = matrix[0].length;
    if (n === 0) return result;

    let top = 0;
    let bottom = m - 1;
    let left = 0;
    let right = n - 1;

    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) {
            result.push(matrix[top][c]);
        }
        top++;
        if (top > bottom) break;

        for (let r = top; r <= bottom; r++) {
            result.push(matrix[r][right]);
        }
        right--;
        if (left > right) break;

        for (let c = right; c >= left; c--) {
            result.push(matrix[bottom][c]);
        }
        bottom--;
        if (top > bottom) break;

        for (let r = bottom; r >= top; r--) {
            result.push(matrix[r][left]);
        }
        left++;
    }
    return result;
}

Back to Top

Word Search

Given an `m x n` grid `board` and a string `word`, return `true` if `word` exists in the grid. Word constructed from adjacent cells (horizontally/vertically). Same cell not used more than once.

Core Idea: Depth-First Search (DFS) with Backtracking

Explore all possible paths from every cell matching `word[0]`. Recursively try to match subsequent characters by moving to adjacent, unvisited cells. Mark visited, then unmark (backtrack).

Algorithm Steps:

1. Outer Loop: Iterate every cell `(r, c)` in `board`. If `board[r][c] === word[0]`, start `dfs(r, c, 0)`.
2. Recursive `dfs(row, col, wordIndex)`:
   • Base Cases:
     • If `wordIndex === word.length`, return `true` (word found).
     • If out of bounds OR `board[row][col] !== word[wordIndex]`, return `false`.
   • Mark Visited: Store `originalChar = board[row][col]`, then `board[row][col] = '#'`.
   • Explore Neighbors: For each of 4 directions `(dr, dc)`:
     • Call `dfs(row + dr, col + dc, wordIndex + 1)`. If `true`, return `true`.
   • Backtracking: Restore `board[row][col] = originalChar`. Return `false`.
3. Return `false` from Main: If no DFS finds the word.

JavaScript Code:

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
function exist(board, word) {
    const m = board.length;
    if (m === 0) return false;
    const n = board[0].length;
    if (n === 0) return false;
    if (word.length === 0) return true;

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

    const dfs = (row, col, wordIndex) => {
        if (wordIndex === word.length) {
            return true;
        }
        if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] !== word[wordIndex]) {
            return false;
        }

        const originalChar = board[row][col];
        board[row][col] = '#'; // Mark as visited

        let found = false;
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            if (dfs(newRow, newCol, wordIndex + 1)) {
                found = true;
                break;
            }
        }

        board[row][col] = originalChar; // Backtrack: restore original char
        return found;
    };

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (board[r][c] === word[0]) {
                if (dfs(r, c, 0)) {
                    return true;
                }
            }
        }
    }
    return false;
}

Back to Top

Find Duplicate File in System

Given `paths` of directory info, return all duplicate files in the file system (same content). Output is a list of groups of file paths.

Core Idea: Hash Map to Group by Content

Use a hash map where keys are file contents and values are lists of file paths. Parse each input string to extract content and path, then populate the map.

Algorithm Steps:

1. Initialize `contentMap = new Map()` (`Map`).
2. Parse Each Path String: For each `pathString` in `paths`:
   • Split by space: `directoryPath = parts[0]`, `fileInfo = parts[1...]`.
   • For each `fileInfo`:
     • Extract `fileName` and `fileContent` (using `indexOf('(')` and `substring`).
     • Construct `fullFilePath = directoryPath + '/' + fileName`.
     • If `!contentMap.has(fileContent)`, `contentMap.set(fileContent, [])`.
     • `contentMap.get(fileContent).push(fullFilePath)`.
3. Filter for Duplicates: Initialize `result = []`. Iterate `contentMap.values()`. If `filePathsArray.length > 1`, `result.push(filePathsArray)`.
4. Return `result`.

JavaScript Code:

/**
 * @param {string[]} paths
 * @return {string[][]}
 */
function findDuplicate(paths) {
    const contentMap = new Map();

    for (const pathString of paths) {
        const parts = pathString.split(' ');
        const directoryPath = parts[0];

        for (let i = 1; i < parts.length; i++) {
            const fileInfo = parts[i];
            const openParenIndex = fileInfo.indexOf('(');
            const fileName = fileInfo.substring(0, openParenIndex);
            const fileContent = fileInfo.substring(openParenIndex + 1, fileInfo.length - 1);

            const fullFilePath = `${directoryPath}/${fileName}`;

            if (!contentMap.has(fileContent)) {
                contentMap.set(fileContent, []);
            }
            contentMap.get(fileContent).push(fullFilePath);
        }
    }

    const result = [];
    for (const filePathsArray of contentMap.values()) {
        if (filePathsArray.length > 1) {
            result.push(filePathsArray);
        }
    }
    return result;
}

Back to Top