< Back to Posts

WIP Solving NeetCode 150

https://neetcode.io/roadmaphttps://neetcode.io/roadmap

Arrays & Hashing

Contains Duplicate (easy)

https://neetcode.io/problems/duplicate-integerhttps://neetcode.io/problems/duplicate-integer

Description

Determine if there are any duplicate elements in the array nums
Return true if there are duplicate elements, otherwise return false

Solution

Solution
  1. Convert the array to a Set and compare the size of the Set with the size of the array.
    If the size of the Set is smaller than the size of the array, it indicates that there are duplicate elements.
class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    hasDuplicate(nums) {
        return new Set(nums).size < nums.length;
    }
}
  1. Sort the array and compare adjacent elements.
    If two adjacent elements are the same, it indicates that there are duplicate elements.
class Solution {
    /**
     * @param {number[]} nums
     * @return {boolean}
     */
    hasDuplicate(nums) {
        nums.sort((a, b) => a - b);
        for (let i = 1; i < nums.length; i++) {
            if (nums[i] === nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

Thought

It is possible to compare using a for loop, but it can be easily solved by using a Set to eliminate duplicates and comparing sizes.

Valid Anagram (easy)

https://neetcode.io/problems/is-anagramhttps://neetcode.io/problems/is-anagram

Description

Given two strings s and t, return true if the two strings are anagrams of each other, otherwise return false.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Solution

Solution
  1. Sort the strings and compare them.
    If the sorted strings are the same, it indicates that the strings are anagrams.
class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {boolean}
     */
    isAnagram(s, t) {
        if(s.length !== t.length) return false

        const sortedS = s.split("").sort().join()
        const sortedT = t.split("").sort().join()

        return sortedS === sortedT
    }
}
  1. Hash Table
    Count the number of occurrences of each character in the strings and compare them.
class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {boolean}
     */
    isAnagram(s, t) {
        if(s.length !== t.length) return false

        const countS = {}
        const countT = {}

        for (let i = 0; i < s.length; i++) {
            countS[s[i]] = (countS[s[i]] || 0) + 1
            countT[t[i]] = (countT[t[i]] || 0) + 1
        }

        for (const key in countS) {
            if(countS[key] !== countT[key]) return false
        }
        return true
    }
}

Thought

  • sort
  • hash table

Two Sum (easy)

https://neetcode.io/problems/two-integer-sumhttps://neetcode.io/problems/two-integer-sum

Description

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Solution

Solution

Create a list where the value is the key and the index is the value, calculate the diff, and return the index if that diff exists as a key.

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    twoSum(nums, target) {
        const prevMap = {}

        for (let i = 0; i < nums.length; i++) {
            const diff = target - nums[i];
            if(prevMap.hasOwnProperty(diff)) {
                return [prevMap[diff], i];
            }

            prevMap[nums[i]] = i
        }

        return []
    }
}

Thought

Group Anagrams (medium)

https://neetcode.io/problems/anagram-groupshttps://neetcode.io/problems/anagram-groups

Description

Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.

An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Solution

Solution

sort each string and use it as a key in a hash map.

class Solution {
    /**
     * @param {string[]} strs
     * @return {string[][]}
     */
    groupAnagrams(strs) {
        const hashMap = {}

        for(let i = 0; i < strs.length; i++) {
            const sorted = strs[i].split("").sort().join("")
            if(!hashMap[sorted]) {
                hashMap[sorted] = [];
            }   
            hashMap[sorted].push(strs[i]);
        }

        return Object.values(hashMap);
    }
}

Thought

Top K Frequent Elements (medium)

https://neetcode.io/problems/top-k-elements-in-listhttps://neetcode.io/problems/top-k-elements-in-list

Description

Given an integer array nums and an integer k, return the k most frequent elements within the array.

The test cases are generated such that the answer is always unique.

You may return the output in any order.

Solution

Solution

Thought

Encode and Decode Strings (medium)

https://neetcode.io/problems/string-encode-and-decodehttps://neetcode.io/problems/string-encode-and-decode

Description

Solution

Solution
  1. sorting
class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number[]}
     */
    topKFrequent(nums, k) {
        const hashMap = {}  // val → count

        for(let i = 0; i < nums.length; i++) {
            hashMap[nums[i]] = (hashMap[nums[i]] || 0) + 1;
        }

        const limit = Object.keys(hashMap).length <  k ? Object.keys(hashMap).length : k;
        const sorted = Object.entries(hashMap).sort(([keyA, valA], [keyB, valB]) => valB - valA);

        const res = [];
        for(let i = 0; i < limit; i++) {
            res.push(sorted[i][0]);
        }

        return res;
    }
}
  1. heap
class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number[]}
     */
    topKFrequent(nums, k) {
        const count = {};
        for (const num of nums) {
            count[num] = (count[num] || 0) + 1;
        }

        const heap = new MinPriorityQueue(x => x[1]);
        for(const [num, cnt] of Object.entries(count)){
            heap.enqueue([num, cnt]);
            if (heap.size() > k) heap.dequeue();
        }

        const res = [];
        for(let i = 0; i < k; i++) {
            const [num, cnt] = heap.dequeue();
            res.push(num)
        }
        return res; 
    }
}
  1. bucket sort
class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number[]}
     */
    topKFrequent(nums, k) {
        const count = {};
        const freq = Array.from({ length: nums.length + 1 }, () => []);

        for (const n of nums) {
            count[n] = (count[n] || 0) + 1;
        }
        for (const n in count) {
            freq[count[n]].push(parseInt(n));
        }

        const res = [];
        for (let i = freq.length - 1; i > 0; i--) {
            for (const n of freq[i]) {
                res.push(n);
                if (res.length === k) {
                    return res;
                }
            }
        }
    }
}

Thought

sortingでelementをkeyに、countをvalueにしてやった結果、entriesにして扱う必要があった。

Product of Array Except Self (medium)

https://neetcode.io/problems/products-of-array-discluding-selfhttps://neetcode.io/problems/products-of-array-discluding-self

Description

Solution

Solution

Thought

Valid Sudoku (medium)

https://neetcode.io/problems/valid-sudokuhttps://neetcode.io/problems/valid-sudoku

Description

Solution

Solution

Thought

Longest Consecutive Sequence (medium)

https://neetcode.io/problems/longest-consecutive-sequencehttps://neetcode.io/problems/longest-consecutive-sequence

Description

Solution

Solution

Thought