Hash Table

hon9g commented 4 years ago

Problems selected by LeetCode for the topic Hash Table 🌐

Click ✔️ to go to each solution. The Link to each problem🌐 is at the top of each solution.

🔗 Design a Hash Table

#	title	my solution
705	Design HashSet	✔️
706	Design HashMap	✔️

🔗 Practical Application - Hash Set

#	title	my solution
217	Contains Duplicate	✔️
136	Single Number	✔️
349	Intersection of Two Arrays	✔️
202	Happy Number	✔️

🔗 Practical Application - Hash Map

#	title	my solution
1	Two Sum	✔️
205	Isomorphic Strings	✔️
599	Minimum Index Sum of Two Lists	✔️
387	First Unique Character in a String	✔️
350	Intersection of Two Arrays II	✔️
219	Contains Duplicate II	✔️
359	Logger Rate Limiter	✔️

🔗 Practical Application - Design the Key

#	title	my solution
49	Group Anagrams	✔️
249	Group Shifted Strings	✔️
36	Valid Sudoku	✔️
652	Find Duplicate Subtrees	✔️

🔗 Conclusion

#	title	my solution
771	Jewels and Stones	✔️
3	Longest Substring Without Repeating Characters	✔️
170	Two Sum III - Data structure design	✔️
454	4Sum II	✔️
347	Top K Frequent Elements	✔️
288	Unique Word Abbreviation	✔️
380	Insert Delete GetRandom O(1)	✔️

hon9g commented 4 years ago

705. Design HashSet

🌐problem
N Buckets
Time complexity: O(1) for all method

Space complexity: O(N) N =the range of values, I use 1000001 size array,


/**
* Initialize your data structure here.
*/
const MyHashSet = function() {
this.hashSet = new Array(1000001).fill(0);
};

/**

@param {number} key
@return {void} */ MyHashSet.prototype.add = function(key) { this.hashSet[key] = 1; };

/**

@param {number} key
@return {void} */ MyHashSet.prototype.remove = function(key) { this.hashSet[key] = 0; };

/**

Returns true if this set contains the specified element
@param {number} key

@return {boolean} */ MyHashSet.prototype.contains = function(key) { return this.hashSet[key] === 1; };


### Array of Array as Bucket
- The common choice of hash function is `%`
- Generally advisable to use a prime number as the base of modulo operator to reduce collisions
- `N = the range of values, It is 1000001`
- `K = the number for hash function, I use 769`
- Time complexity: **O(1)** `for add` **O(N/K)** `for remove and search`
- Space complexity: **O(N)**
```JavaScript
const MyHashSet = function() {
this.hashSet = new Array(769);
};

/**

@param {number} key
@return {void} */ MyHashSet.prototype.add = function(key) { if (!this.hashSet[key%769]) { this.hashSet[key%769] = [key]; } else { this.hashSet[key%769].push(key); } };

/**

@param {number} key
@return {void} */ MyHashSet.prototype.remove = function(key) { if (!this.hashSet[key%769]) return; this.hashSet[key%769] = this.hashSet[key%769].filter(x => x !== key); };

/**

Returns true if this set contains the specified element
@param {number} key
@return {boolean} */ MyHashSet.prototype.contains = function(key) { if (!this.hashSet[key%769]) return false; return this.hashSet[key%769].includes(key); };

Binary Search Tree as a Bucket

The common choice of hash function is %
Generally advisable to use a prime number as the base of modulo operator to reduce collisions
N = the range of values, It is 1000001
K = the number for hash function, I use 769
Time complexity: O(log(N/K)) for add, remove and search

Space complexity: O(N)


/** Binary Search Tree
* @param {number} x
* @return {void}
*/
function Node(x) {
this.val = x;
this.left = null;
this.right = null;
}

/**

@param {number} x
@return {Node} */ Node.prototype.add = function(x) { if (!this) { return new Node(x); } if (x === this.val) { return this; } else if (x < this.val) { this.left = this.left ? this.left.add(x) : new Node(x); } else { this.right = this. right ? this.right.add(x) : new Node(x); } return this; }

/**

@return {number} */ Node.prototype.successor = function() { let node = this.right; while (node.left) { node = node.left; } return node.val; }

/**

@return {number} */ Node.prototype.predecessor = function() { let node = this.left; while (node.right) { node = node.right; } return node.val; }

/**

@param {number} x
@return {Node} */ Node.prototype.remove = function(x) { if (!this) return null; if (x === this.val) { if (this.right) { this.val = this.successor(); this.right = this.val ? this.right.remove(this.val) : null; } else if (this.left) { this.val = this.predecessor(); this.left = this.val ? this.left.remove(this.val) : null; } else { return null; } } else if (x > this.val) { this.right = this.right ? this.right.remove(x) : null; } else { this.left = this.left ? this.left.remove(x) : null; } return this; }

/**

@param {number} x
@return {bool} */ Node.prototype.contains = function(x) { if (!this || x === this.val) { return this !== null; } if (x < this.val) { return this.left !== null && this.left.contains(x); } return this.right !== null && this.right.contains(x); }

/**

@return {void} */ const MyHashSet = function() { this.hashSet = new Array(769).fill(null); };

/** Hash Set

@param {number} key
@return {void} */ MyHashSet.prototype.add = function(key) { if (!this.hashSet[key%769]) { this.hashSet[key%769] = new Node(key); } else { this.hashSet[key%769].add(key); }

};

/**

@param {number} key
@return {void} */ MyHashSet.prototype.remove = function(key) { if (!this.hashSet[key%769]) return; this.hashSet[key%769] = this.hashSet[key%769].remove(key); };

/**

Returns true if this set contains the specified element
@param {number} key
@return {boolean} */ MyHashSet.prototype.contains = function(key) { if (!this.hashSet[key%769]) return false; return this.hashSet[key%769].contains(key); };

hon9g commented 4 years ago

706. Design HashMap

🌐problem
N Buckets
Hash Table Length : N
Hash Function : % prime number
Bucket : integer
Time complexity: O(1) for all method

Space complexity: O(N) N = range of key


const MyHashMap = function() {
this.map = new Array(1000001).fill(-1);
};

/**

value will always be non-negative.
@param {number} key
@param {number} value
@return {void} */ MyHashMap.prototype.put = function(key, value) { this.map[key] = value; };

/**

Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
@param {number} key
@return {number} */ MyHashMap.prototype.get = function(key) { return this.map[key]; };

/**

Removes the mapping of the specified value key if this map contains a mapping for the key
@param {number} key
@return {void} */ MyHashMap.prototype.remove = function(key) { this.map[key] = -1; };

BST as Buckets

Hash Table Length : constant prime number
Hash Function : % prime number
Bucket : Binary Search Tree
Time complexity: O(log (N/K)) for each method

Space complexity: O(N)


/**
* Node for Binary Search Tree
* @return {void}
*/
const Node = function(key, val) {
this.key = key;
this.val = val;
this.left = null;
this.right = null;
}

/**

Add Node via key
@param {number} key
@param {number} val
@return {void} */ Node.prototype.add = function(key, val) { if (!this) return new Node(key, val); if (this.key === key) { this.val = val; } else if (this.key > key) { this.left = this.left ? this.left.add(key, val) : new Node(key, val); } else { this.right = this.right ? this.right.add(key, val) : new Node(key, val); } return this; }

/**

Search value via key
@param {number} key
@return {number} */ Node.prototype.search = function(key) { if (!this) return -1; if (this.key === key) return this.val; if (this.key < key && this.right) return this.right.search(key); if (this.key > key && this.left) return this.left.search(key); return -1; }

/**

Return predecessor Node
@param {number} key
@return {void} */ Node.prototype.predecessor = function() { let node = this.left; while (node.right) { node = node.right; } return [node.key, node.val]; }

/**

Return successor Node
@param {number} key
@return {void} */ Node.prototype.successor = function() { let node = this.right; while (node.left) { node = node.left; } return [node.key, node.val]; }

/**

Remove Node via key
@param {number} key
@return {void} */ Node.prototype.remove = function(x) { if (!this) return null; if (this.key === x) { if (this.left) { [this.key, this.val] = this.predecessor(); this.left = this.key ? this.left.remove(this.key) : null; } else if (this.right) { [this.key, this.val] = this.successor(); this.right = this.key ? this.right.remove(this.key) : null; } else { return null; } } else if (this.key > x) { this.left = this.left ? this.left.remove(x) : null; } else { this.right = this.right ? this.right.remove(x) : null; } return this; }

/**

Hash Map
@return {void} */ const MyHashMap = function(size = 769) { this.n = size; this.map = new Array(size); };

/**

value will always be non-negative.
@param {number} key
@param {number} value
@return {void} */ MyHashMap.prototype.put = function(key, value) { if (!this.map[key%this.n]) { this.map[key%this.n] = new Node(key, value); } else { this.map[key%this.n].add(key, value); } };

/**

Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
@param {number} key
@return {number} */ MyHashMap.prototype.get = function(key) { return this.map[key%this.n] ? this.map[key%this.n].search(key) : -1; };

/**

Removes the mapping of the specified value key if this map contains a mapping for the key
@param {number} key
@return {void} */ MyHashMap.prototype.remove = function(key) { if (this.map[key%this.n]) { this.map[key%this.n] = this.map[key%this.n].remove(key); } };

Built-in object Map

Time complexity: O(1) for all method

Space complexity: O(N) N = range of key


/**
* Hash Map
* @return {void}
*/
var MyHashMap = function() {
this.map = new Map();
};

/**

value will always be non-negative.
@param {number} key
@param {number} value
@return {void} */ MyHashMap.prototype.put = function(key, value) { this.map.set(key, value); };

/**

Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
@param {number} key
@return {number} */ MyHashMap.prototype.get = function(key) { return this.map.has(key) ? this.map.get(key) : -1; };

/**

Removes the mapping of the specified value key if this map contains a mapping for the key
@param {number} key
@return {void} */ MyHashMap.prototype.remove = function(key) { this.map.delete(key); };

hon9g commented 4 years ago

217. Contains Duplicate

🌐problem
Hash Set
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {number[]} nums
* @return {boolean}
*/
const containsDuplicate = nums => {
const hashSet = new Set();
for(let i = 0; i < nums.length; i++) {
    if (hashSet.has(nums[i])) return true;
    hashSet.add(nums[i])
}
return false;
};

class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
    hashSet = set()
    for i in range(len(nums)):
        if nums[i] in hashSet:
            return True
        hashSet.add(nums[i])
    return False

hon9g commented 4 years ago

136. Single Number

🌐problem
Hash Set
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber = nums => {
const hashSet = new Set();
nums.forEach(x => {
    if (hashSet.has(x)) {
        hashSet.delete(x);
    } else {
        hashSet.add(x);
    }
})
return [...hashSet][0];
};

class Solution:
def singleNumber(self, nums: List[int]) -> int:
    hashSet = set()
    for i in range(len(nums)):
        if nums[i] in hashSet:
            hashSet.remove(nums[i])
        else:
            hashSet.add(nums[i])
    return hashSet.pop()

Sorting

Time complexity: O(N log N)

Space complexity: O(1)

/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber = nums => {
nums.sort()
for (let i = 0; i + 1 < nums.length; i += 2) {
    if (nums[i] !== nums[i+1]) {
        return nums[i-1] === nums[i] ? nums[i+1] : nums[i];
    }
}
return nums[nums.length - 1];
};

class Solution:
def singleNumber(self, nums: List[int]) -> int:
    nums.sort()
    for i in range(1, len(nums), 2):
        if nums[i-1] != nums[i]:
            return nums[i-1] if nums[i] == nums[i+1] else nums[i]
    return nums[-1]

Math

2(a + b) - ( a + a + b ) = b
Time complexity: O(N)

Space complexity: O(N)


/**
* @param {number} a
* @param {number} b
* @return {number}
*/
const sum = (a, b) => a + b;

/**

@param {number[]} nums

@return {number} / const singleNumber = nums => [...new Set(nums)].reduce(sum) 2 - nums.reduce(sum);

```Python
class Solution:
def singleNumber(self, nums: List[int]) -> int:
    return sum(set(nums)) * 2 - sum(nums)

Bit Manipulation

Time complexity: O(N)

Space complexity: O(1)

/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber = nums => nums.reduce((acc, curr) => acc^curr);

class Solution:
def singleNumber(self, nums: List[int]) -> int:
    res = 0
    for n in nums:
        res ^= n
    return res

hon9g commented 4 years ago

349. Intersection of Two Arrays

🌐problem
Intersection of 2 Sets
Time complexity: O(N+M)

Space complexity: O(N+M)

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
const [a, b] = [new Set(nums1), new Set(nums2)];
return [...a].filter(x => b.has(x));
};

class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
    return set(nums1) & set(nums2)

hon9g commented 4 years ago

202. Happy Number

🌐problem
Detect Cycles with a HashSet
Time complexity: O(243⋅3 + log N) = O(log N)

Space complexity: O(243⋅3) = O(1)

/**
* @param {number} n
* @return {boolean}
*/
const isHappy = n => {
const seen = new Set();
let m;
while (n !== 1) {
    if (seen.has(n)) return false;
    seen.add(n);
    [m, n] = [n, 0];
    while (m > 0) {
        n += (m % 10) ** 2;
        m = (m - m % 10) / 10;
    }
}
return true;
}


/**
* @param {string} s
* @return {number}
*/
const toInt = s => parseInt(s);

/**

@param {number} a
@param {number} b
@return {number} */ const powerSum = (a, b) => a + b ** 2;

/**

@param {number} n
@return {boolean} */ const isHappy = n => { const seen = new Set(); while (n !== 1) { if (seen.has(n)) return false; seen.add(n); n = n.toString(10).split('').map(toInt).reduce(powerSum,0); } return true; };
```
```Python
class Solution:
def isHappy(self, n: int) -> bool:
    seen = set()
    while n != 1:
        if n in seen:
            return False
        seen.add(n)
        n = sum([int(s) ** 2 for s in str(n)])
    return True
```
Floyd's Cycle-Finding Algorithm
- Time complexity: O(log N)
- Space complexity: O(1)
```
/**
```
@param {number} m
@return {number} */ const nextN = m => { let n = 0; while (m > 0) { [n, m] = [n + (m % 10) **2, (m - m % 10) / 10]; } return n; }

/**

@param {number} n
@return {boolean} */ const isHappy = n => { let [turtle, hare] = [n, nextN(n)]; while (turtle !== 1) { if (turtle === hare) return false; turtle = nextN(turtle); hare = nextN(nextN(hare)); } return true; }

hon9g commented 4 years ago

1. Two Sum

🌐problem
1 pass Hash Table
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = (nums, target) => {
const memo = new Map();
for (let i = 0; i < nums.length; i++) {
    if (memo.has(target - nums[i])) {
        return [memo.get(target - nums[i]), i];
    }
    memo.set(nums[i], i);
}
};

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = (nums, target) => {
const memo = {};
for (let i = 0; i < nums.length; i++) {
    if (memo[target - nums[i]] !== undefined) {
        return [memo[target - nums[i]], i];
    }
    memo[nums[i]] = i;
}
};

hon9g commented 4 years ago

205. Isomorphic Strings

🌐problem
Hash Map and Hash Set
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
const isIsomorphic = (s, t) => {
const [memo, seen] = [new Map(), new Set()];
for (let i = 0; i < s.length; i++) {
    if (!memo.get(s[i]) && !seen.has(t[i])) {
        memo.set(s[i], t[i]);
        seen.add(t[i]);
    }
    if (memo.get(s[i]) !== t[i]) return false;
}
return true;
};

hon9g commented 4 years ago

599. Minimum Index Sum of Two Lists

🌐problem
Linear complexity with Hash Map
Time complexity: O(L1 + L2)

Space complexity: O(L1 + 2001) = O(L1)

/**
* @param {string[]} list1
* @param {string[]} list2
* @return {string[]}
*/
const findRestaurant = (list1, list2) => {
const seen = {};
for (let i = 0; i < list1.length; i++) {
    seen[list1[i]] = i;
}
const commons = new Array(2001);
let minVal = Infinity;
for (let i = 0; i < list2.length; i++) {
    if (seen[list2[i]] !== undefined) {
        const idx = seen[list2[i]] + i;
        if (commons[idx] === undefined) {
            commons[idx] = [];
        }
        commons[idx].push(list2[i]);
        if (idx < minVal) minVal = idx;
    }
}
return commons[minVal];
};

Time complexity: O(L1 + L2)

Space complexity: O(L1)

/**
* @param {string[]} list1
* @param {string[]} list2
* @return {string[]}
*/
const findRestaurant = (list1, list2) => {
let [seen, commons, minVal] = [{}, [], Infinity];
for (let i = 0; i < list1.length; i++) seen[list1[i]] = i;
for (let i = 0; i < list2.length; i++) {
    if (seen[list2[i]] !== undefined) {
        const idx = seen[list2[i]] + i;
        if (idx < minVal) minVal = idx, commons = [];
        if (idx === minVal) commons.push(list2[i]);
    }
}
return commons;
};

class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
    seen, minVal, common = {}, float("inf"), []
    for idx, name in enumerate(list1):
        seen[name] = idx
    for idx, name in enumerate(list2):
        if name in seen:
            seen[name] = seen[name] + idx
            if minVal > seen[name]:
                minVal = seen[name]
                common = []
            if seen[name] == minVal:
                common.append(name)
    return common

hon9g commented 4 years ago

387. First Unique Character in a String

🌐problem
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {string} s
* @return {number}
*/
const firstUniqChar = s => {
const counter = {};
for (const c of s) {
    counter[c] ? counter[c]++ : counter[c] = 1;
}
for (let i = 0; i < s.length; i++) {
    if (counter[s[i]] === 1) return i;
}
return -1
};

Time complexity: O(N)

Space complexity: O(N)

class Solution:
def firstUniqChar(self, s: str) -> int:
    counter = {}
    for c in s:
        if c in counter:
            counter[c] += 1
        else:
            counter[c] = 1
    for i in range(len(s)):
        if counter[s[i]] == 1:
            return i
    return -1

hon9g commented 4 years ago

350. Intersection of Two Arrays II

🌐problem
Hash Map
Time complexity: O(N+M)

Space complexity: O(N+M)

/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
const intersect = (nums1, nums2) => {
const seen = {};
for (n of nums1) seen[n] ? seen[n]++ : seen[n] = 1;
return nums2.filter(e => seen[e] ? seen[e]-- : false)
};

hon9g commented 4 years ago

219. Contains Duplicate II

🌐problem
K sized Hash Set
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
const containsNearbyDuplicate = (nums, k) => {
for (let i = 0, seen = new Set(); i < nums.length; i++) {
    if (seen.has(nums[i])) return true;
    seen.add(nums[i]);
    if (k < seen.size) seen.delete(nums[i-k]);
}
return false;
};

hon9g commented 4 years ago

359. Logger Rate Limiter

🌐problem
Hash Table
Time complexity: O(1)

Space complexity: O(N)


var Logger = function() {
this.seen = new Map();
};

/**

Returns true if the message should be printed in the given timestamp, otherwise returns false. If this method returns false, the message will not be printed. The timestamp is in seconds granularity.
@param {number} timestamp
@param {string} message
@return {boolean} */ Logger.prototype.shouldPrintMessage = function(timestamp, message) { if (this.seen.has(message) && timestamp - this.seen.get(message) < 10) return false; this.seen.set(message, timestamp); return true; };

hon9g commented 4 years ago

49. Group Anagrams

🌐problem
Categorize by Sorted String
Time complexity: O(NK log K)

Space complexity: O(NK)

/**
* @param {string[]} strs
* @return {string[][]}
*/
const groupAnagrams = strs => {
const map = {};
strs.forEach(s => {
    const key = s.split('').sort();
    map[key] ? map[key].push(s) : map[key] = [s];
})
return Object.values(map);
};

Categorize by Count

Time complexity: O(NK)

Space complexity: O(NK)

/**
* @param {string[]} strs
* @return {string[][]}
*/
const groupAnagrams = strs => {
const map = {};
strs.forEach(s => {
    const key = new Array(26).fill(0);
    for (c of s) key[c.charCodeAt(0) - 97]++;
    map[key] ? map[key].push(s) : map[key] = [s];
})
return Object.values(map);
};

hon9g commented 4 years ago

249. Group Shifted Strings

🌐problem
Distance Between Previous char and Current char
Time complexity: O(NK)

Space complexity: O(NK)

/**
* @param {string[]} strs
* @return {string[][]}
*/
const groupStrings = strs => {
const res = {};
strs.forEach(s => {
    const key = new Array(s.length).fill(0);
    for (let i = 1; i < s.length; i++) {
        key[i] = s.charCodeAt(i-1) - (s.charCodeAt(i) + 26);
        if (key[i] > 25 || key[i] < -25) key[i] %= 26;
    }
    res[key] ? res[key].push(s) : res[key] = [s];
})
return Object.values(res);
};

Determine key by the distance between chars. Assume a = 1, b = 2, ..., y = 25, z = 26,

// if s === "azb"
const key = new Array(s.length).fill(0); // [0, 0, 0]
for (let i = 1; i < s.length; i++) {
key[i] = s.charCodeAt(i-1) - (s.charCodeAt(i) + 26); //  [0, -51, -2]
if (key[i] > 25 || key[i] < -25) key[i] %= 26; //  [0, -25, -2]
}

// if s === "bac"
const key = new Array(s.length).fill(0); // [0, 0, 0]
for (let i = 1; i < s.length; i++) {
key[i] = s.charCodeAt(i-1) - (s.charCodeAt(i) + 26); // [0, -25, -28]
if (key[i] > 25 || key[i] < -25) key[i] %= 26; // [0, -25, -2]
}

hon9g commented 4 years ago

36. Valid Sudoku

🌐problem
Hash Table
Time complexity: O(81) = O(1)

Space complexity: *O(81 3) = O(1)**

/**
* @param {character[][]} board
* @return {boolean}
*/
const isValidSudoku = board => {
let rows = [], cols = [], boxes = [];
for (let i = 0; i < 9; i++) {
    rows.push({}), cols.push({}), boxes.push({});
}
for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
        if (board[i][j] === '.') continue;
        const n = parseInt(board[i][j]);
        const boxIdx = parseInt(i/3) * 3 + parseInt(j/3);
        rows[i][n] = rows[i][n] ? rows[i][n] + 1 : 1;
        cols[j][n] = cols[j][n] ? cols[j][n] + 1 : 1;
        boxes[boxIdx][n] = boxes[boxIdx][n] ? boxes[boxIdx][n]  + 1 : 1;
        if (rows[i][n] > 1 || cols[j][n] > 1 || boxes[boxIdx][n] > 1) {
            return false
        }
    }
}
return true;
};

hon9g commented 4 years ago

652. Find Duplicate Subtrees

🌐problem
DFS with Hash Map
Time complexity: O(N^2)

Space complexity: O(N^2)

/**
* @param {TreeNode} root
* @return {TreeNode[]}
*/
const findDuplicateSubtrees = root => {
const dfs = node => {
    if (!node) return '#';
    const key = node.val + dfs(node.left) + dfs(node.right);
    seen[key] ? seen[key]++ : seen[key] = 1;
    if (seen[key] === 2) result.push(node);
    return key;
}
const result = [], seen = {};
dfs(root);
return result;
};

hon9g commented 4 years ago

771. Jewels and Stones

🌐problem
Brute Force
Time complexity: O(JS)

Space complexity: O(1)

/**
* @param {string} J
* @param {string} S
* @return {number}
*/
const numJewelsInStones = (J, S) => {
return S.split('').reduce((a, c) => J.includes(c) ? a + 1 : a, 0);
};

Hash Set

Time complexity: O(J+S)

Space complexity: O(J+S)

/**
* @param {string} J
* @param {string} S
* @return {number}
*/
const numJewelsInStones = (J, S) => {
const box = new Set(J.split(''));
return S.split('').reduce((a, c) => box.has(c) ? a + 1 : a, 0);
};

hon9g commented 4 years ago

3. Longest Substring Without Repeating Characters

🌐problem
Slicing Window
Time complexity: O(N^2)

Space complexity: O(N)

/**
* @param {string} s
* @return {number}
*/
const lengthOfLongestSubstring = s => {
let seen = new Set(), temp = '', n = 0;
for (let c of s) {
    if (seen.has(c)) {
        for (let e of temp.slice(0, temp.indexOf(c))) {
            seen.delete(e);
        }
        temp = temp.slice(temp.indexOf(c) + 1) + c;
    } else {
        temp += c, seen.add(c);
        if (n < temp.length) {
            n = temp.length;
        }
    }
}
return n;
};

Sliding Window

Time complexity: O(2N) = O(N)

Space complexity: O(N)

/**
* @param {string} s
* @return {number}
*/
const lengthOfLongestSubstring = s => {
let seen = new Set(), i = 0 , j = 0, n = 0;
while (i < s.length && j < s.length) {
    if (!seen.has(s[j])) {
        seen.add(s[j++]);
        if (n < j - i) n = j - i;
    } else {
        seen.delete(s[i++]);
    }
}
return n;
};

hon9g commented 4 years ago

170. Two Sum III - Data structure design

🌐problem
Time complexity: O()

Space complexity: O()


var TwoSum = function() {
this.nums = {};
};

/**

Add the number to an internal data structure..
@param {number} number
@return {void} */ TwoSum.prototype.add = function(n) { this.nums[n] ? this.nums[n]++ : this.nums[n] = 1; };

/**

Find if there exists any pair of numbers which sum is equal to the value.
@param {number} value
@return {boolean} */ TwoSum.prototype.find = function(val) { for (let n of Object.keys(this.nums)) { n = parseInt(n); if (this.nums[val - n]) { if (val - n !== n || 1 < this.nums[val - n]) { return true; } } } return false; };

hon9g commented 4 years ago

454. 4Sum II

🌐problem
Two Hash Sets
Time complexity: O(N^2)

Space complexity: O(N^2)


/**
* @param {number[]} A
* @param {number[]} B
* @return {number{}}
*/
const buildMap = (A, B) => {
const cnt = {};
for (a of A) {
    for (b of B) {
        cnt[a+b] ? cnt[a+b]++ : cnt[a+b] = 1;
    }
}
return cnt;
}

/**

@param {number[]} A
@param {number[]} B
@param {number[]} C
@param {number[]} D
@return {number} / const fourSumCount = (A, B, C, D) => { let n = 0; const map1 = buildMap(A,B), map2 = buildMap(C,D); for (x of Object.keys(map1)) { if (map2[x-1]) n += map1[x] map2[x-1]; } return n; };
```
### One Hash Set (TLE)
- Time complexity: **O(N^3)**
- Space complexity: **O(N)**
```JavaScript
/**
```
@param {number[]} A
@param {number[]} B
@param {number[]} C
@param {number[]} D
@return {number} / const fourSumCount = (A, B, C, D) => { let n = 0; const d = {}; for (x of D) d[x] ? d[x]++ : d[x] = 1; for (a of A) { for (b of B) { for (c of C) { if (d[-1(a+b+c)]) n += d[-1*(a+b+c)]; } } } return n; };

hon9g commented 4 years ago

347. Top K Frequent Elements

🌐problem
Time complexity: O()

Space complexity: O()

/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = (nums, k) => {
const cnt = {}, res = [];
for (n of nums) cnt[n] ? cnt[n]++ : cnt[n] = 1;
while (k--) {
    let e = 0, freq = 0;
    for (key of Object.keys(cnt)) {
        if (freq < cnt[key]) e = key, freq = cnt[key];
    }
    res.push(e);
    delete cnt[e];
}
return res;
};

hon9g commented 4 years ago

288. Unique Word Abbreviation

🌐problem
Time complexity: O()

Space complexity: O()


/** 
* @param {string} w
* @return {string}
*/
const abbr = w => w.length < 3 ? w : [w[0], w.length - 2, w[w.length - 1]].join('');

/**

@param {string[]} words */ const ValidWordAbbr = function(words) { this.dict = new Map(); for (w of words) { const key = abbr(w); this.dict.has(key) ? this.dict.get(key).add(w) : this.dict.set(key, new Set([w])); } };

/**

@param {string} word
@return {boolean} */ ValidWordAbbr.prototype.isUnique = function(word) { const key = abbr(word); if (!this.dict.has(key)) return true; return this.dict.get(key).size === 1 && this.dict.get(key).has(word); };

hon9g commented 4 years ago

380. Insert Delete GetRandom O(1)

🌐problem
Time complexity: O()

Space complexity: O()


/**
* Initialize your data structure here.
*/
var RandomizedSet = function() {
this.dict = new Map(), this.arr = [];
};

/**

Inserts a value to the set. Returns true if the set did not already contain the specified element.
@param {number} val
@return {boolean} */ RandomizedSet.prototype.insert = function(val) { if (this.dict.has(val)) return false; this.dict.set(val, this.arr.length); this.arr.push(val); return true; };

/**

Removes a value from the set. Returns true if the set contained the specified element.
@param {number} val
@return {boolean} */ RandomizedSet.prototype.remove = function(val) { if (this.dict.has(val)) { this.arr[this.dict.get(val)] = this.arr[this.arr.length - 1]; this.arr.pop(); this.dict.set(this.arr[this.dict.get(val)], this.dict.get(val)) this.dict.delete(val); return true; } return false; };

/**

Get a random element from the set.
@return {number} / RandomizedSet.prototype.getRandom = function() { return this.arr[Math.floor(Math.random() this.arr.length)];

};

hon9g / algorithms

Hash Table #26

🔗 Design a Hash Table

🔗 Practical Application - Hash Set

🔗 Practical Application - Hash Map

🔗 Practical Application - Design the Key

🔗 Conclusion

705. Design HashSet

N Buckets

Binary Search Tree as a Bucket

706. Design HashMap

N Buckets

BST as Buckets

Built-in object Map

217. Contains Duplicate

Hash Set

136. Single Number

Hash Set

Sorting

Math

Bit Manipulation

349. Intersection of Two Arrays

Intersection of 2 Sets

202. Happy Number

Detect Cycles with a HashSet

Floyd's Cycle-Finding Algorithm

1. Two Sum

1 pass Hash Table

205. Isomorphic Strings

Hash Map and Hash Set

599. Minimum Index Sum of Two Lists

Linear complexity with Hash Map

387. First Unique Character in a String

350. Intersection of Two Arrays II

Hash Map

219. Contains Duplicate II

K sized Hash Set

359. Logger Rate Limiter

49. Group Anagrams

Categorize by Sorted String

Categorize by Count

249. Group Shifted Strings

Distance Between Previous char and Current char

36. Valid Sudoku

Hash Table

652. Find Duplicate Subtrees

DFS with Hash Map

771. Jewels and Stones

Brute Force

Hash Set

3. Longest Substring Without Repeating Characters

Slicing Window

Sliding Window

170. Two Sum III - Data structure design

454. 4Sum II

Two Hash Sets

347. Top K Frequent Elements

288. Unique Word Abbreviation

380. Insert Delete GetRandom O(1)