LeetCode - Others | Fanjia Kong

Record the Others topic algorithm problems.

0046. Permutations

Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

solution:

const permute = (nums) => {
    let results = [];

    let permutations = (current, remaining) => {
        if(remaining.length <= 0) {
            results.push(current);
        } else {
            for(let i = 0; i < remaining.length; i++) {
                permutations([...current,remaining[i]], [...remaining.slice(0, i),...remaining.slice(i+1)]);
            }
        }
    };

    permutations([], nums);
    return results;
};

Runtime: 60 ms
Memory Usage: 37.2 MB

0136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4

solution 1:

const singleNumber = (nums) => {
    if(nums.length === 1) {
        return nums[0]
    }
    for(let i = 0; i < nums.length; i++) {
        if(nums.indexOf(nums[i]) === nums.lastIndexOf(nums[i])) {
            return nums[i];
        }
    }
    return null
};

Runtime: 356 ms
Memory Usage: 35.4 MB

solution 2:

const singleNumber = (nums) => {
    if(nums.length === 1) {
        return nums[0]
    }
    nums.sort();
    for (let i = 0; i < nums.length; i += 2) {
        if (nums[i] !== nums[i + 1]) {
            return nums[i];
        }
    }
};

Runtime: 84 ms
Memory Usage: 36.7 MB

solution 3:

const singleNumber = (nums) => {
    if(nums.length === 1) {
        return nums[0]
    }
    return nums.reduce((prev, curr) => prev ^ curr, 0);
};

Runtime: 48 ms
Memory Usage: 35.5 MB

0146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Example:
LRUCache cache = new LRUCache( 2 /_ capacity _/ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

solution:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.cache.has(key)) {
        return -1;
    }

    const v = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, v);
    return this.cache.get(key);
  };

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
  };
}

Runtime: 208 ms
Memory Usage: 58.5 MB

0155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> Returns -3.
minStack.pop();
minStack.top(); –> Returns 0.
minStack.getMin(); –> Returns -2.

solution:

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = [];
    this.min = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    var min = this.getMin();
    if (min !== undefined) {
        this.min.push(Math.min(x, min));
    } else {
        this.min.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.stack.pop();
    this.min.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if (this.stack.length) {
        return this.stack[this.stack.length - 1];
    }
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    if (this.min.length) {
        return this.min[this.min.length - 1];
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

Runtime: 96 ms
Memory Usage: 44.5 MB

0190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.
Example 1:
Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

solution 1:

const reverseBits = (n) => {
    let result = 0;
    let count = 32;

    while (count--) {
        result *= 2;
        result += n & 1;
        n = n >> 1;
    }
    return result;
};

Runtime: 64 ms
Memory Usage: 35.9 MB

solution 2:

const reverseBits = (n) => {
    const str = n.toString(2).padStart(32, '0');
    return parseInt(str.split('').reverse().join(''), 2)
};

Runtime: 84 ms
Memory Usage: 35.8 MB

0191. Number of 1 Bits

Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).
Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.
Example 2:
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one ‘1’ bit.
Example 3:
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one ‘1’ bits.

solution 1:

const hammingWeight = (n) => {
    let answer = 0
    while (n) {
        answer += n & 1
        n = n >>> 1
    }
    return answer
};

Runtime: 60 ms
Memory Usage: 34.8 MB

solution 2:

const hammingWeight = (n) => {
    let count = 0;
    while (n) {
      n &= (n-1) ;
      count++;
    }
    return count;
};

Runtime: 64 ms
Memory Usage: 34.3 MB

solution 3:

1
2
3

const hammingWeight = (n) => {
    return n.toString(2).split("0").join("").length;
};

Runtime: 60 ms
Memory Usage: 34.3 MB

solution 4:

1
2
3

const hammingWeight = (n) => {
    return n.toString(2).replace(/0/g, '').length;
};

Runtime: 88 ms
Memory Usage: 34.3 MB

solution 5:

1
2
3

const hammingWeight = (n) => {
    return n.toString(2).split("").filter(item => item === '1').length;
};

Runtime: 60 ms
Memory Usage: 34.7 MB

0200. Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3

solution:

const numIslands = (grid) => {
  let count = 0;
  function dfs(grid, row, col) {
    // bound check
    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length) {
        return;
    }
    const value = grid[row][col];
    if (value === '1') {
        grid[row][col] = '#';
        dfs(grid, row + 1, col);
        dfs(grid, row - 1, col);
        dfs(grid, row, col + 1);
        dfs(grid, row, col - 1);
    }
  }
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(grid, i,j);
      }
    }
  }

  return count;
};

Runtime: 72 ms
Memory Usage: 37.4 MB

0207. Course Schedule

There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

solution:

const canFinish = (numCourses, prerequisites) => {
  const seen = new Set();
  const seeing = new Set();
  const adj = [...Array(numCourses)].map(r => []);

  for (let [u, v] of prerequisites) {
    adj[v].push(u);
  }

  for (let c = 0; c < numCourses; c++) {
    if (!dfs(c)) {
      return false;
    }
  }
  return true;

  function dfs(v) {
    if (seen.has(v)) {
        return true;
    }
    if (seeing.has(v)) {
        return false;
    }

    seeing.add(v);
    for (let nv of adj[v]) {
      if (!dfs(nv)) {
        return false;
      }
    }
    seeing.delete(v);
    seen.add(v);
    return true;
  }
};

Runtime: 68 ms
Memory Usage: 38.7 MB

0208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // returns true
trie.search(“app”); // returns false
trie.startsWith(“app”); // returns true
trie.insert(“app”);
trie.search(“app”); // returns true
Note:
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

solution:

function Trie() {
    const root = {};
	return { insert, search, startsWith };

	function insert(word) {
		let curr = root;
		word.split('').forEach(ch => curr = curr[ch] = curr[ch] || {});
		curr.isWord = true;
	}

	function traverse(word) {
		let curr = root;
		for (var i = 0; i < word.length; i++) {
			if (!curr) return null;
			curr = curr[word[i]];
		}
		return curr;
	}

	function search(word) {
		let node = traverse(word);
		return !!node && !!node.isWord;
	}

	function startsWith(word) {
		return !!traverse(word);
	}
};

/**
 * Your Trie object will be instantiated and called as such:
 * var obj = new Trie()
 * obj.insert(word)
 * var param_2 = obj.search(word)
 * var param_3 = obj.startsWith(prefix)
 */

Runtime: 172 ms
Memory Usage: 53.9 MB

0212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:
Input:
board = [
[‘o’,’a’,’a’,’n’],
[‘e’,’t’,’a’,’e’],
[‘i’,’h’,’k’,’r’],
[‘i’,’f’,’l’,’v’]
]
words = [“oath”,”pea”,”eat”,”rain”]
Output: [“eat”,”oath”]

Note:
All inputs are consist of lowercase letters a-z.
The values of words are distinct.

solution1:

const findWords = (board, words) => {
  const dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  let res = [];

  const buildTrie = () => {
    const root = {};
    for (const w of words) {
      let node = root;
      for (const c of w) {
        if (node[c] == null) node[c] = {};
        node = node[c];
      }
      node.word = w;
    }
    return root;
  };

  const search = (node, x, y) => {
    if (node.word != null) {
      res.push(node.word);
      node.word = null; // make sure only print one time for each word
    }

    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
    if (node[board[x][y]] == null) return;

    const c = board[x][y];
    board[x][y] = '#'; // Mark visited
    for (const [dx, dy] of dirs) {
      const i = x + dx;
      const j = y + dy;
      search(node[c], i, j);
    }
    board[x][y] = c; // Reset
  };

  const root = buildTrie();
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      search(root, i, j);
    }
  }
  return res;
};

Runtime: 152 ms
Memory Usage: 50.5 MB

solution2:

const findWords = (board, words) => {
  let res = [];
  const root = buildTrie(words);
  for (let row = 0; row < board.length; row++) {
    for (let col = 0; col < board[0].length; col++) {
      dfs(root, row, col, board, res);
    }
  }
  return res;

};

function dfs(node, row, col, board, res) {
    if (node.end) {
      res.push(node.end);
      node.end = null;   // make sure only print one time for each word
    }

    if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) return;
    if (!node[board[row][col]]) return;

    const c = board[row][col];
    board[row][col] = '#';  // mark visited
    dfs(node[c], row + 1, col, board, res); // up
    dfs(node[c], row - 1, col, board, res); // down
    dfs(node[c], row, col + 1, board, res); // right
    dfs(node[c], row, col - 1, board, res); // left
    board[row][col] = c;  // reset - back track
}

function buildTrie(words) {
    const root = {};
    for (let w of words) {
      let pointer = root; // here 'pointer' just a reference, that we use to go down from root till last child node
                          // and when we rich last child node - this is the end of the world
                          // and instead of setting "node.end = true", we set "node.end = word"
      for (let c of w) {
        if (!pointer[c]) pointer[c] = {}; // if we already have such node, lets ignore it creating and just move the pointer
        pointer = pointer[c];
      }
      pointer.end = w; 
    }
    return root;
}

Runtime: 148 ms
Memory Usage: 50.4 MB

0215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

solution:

const findKthLargest = (nums, k) => {
    return quickSelect(nums)

    function quickSelect(nums, lo = 0, hi = nums.length - 1) {
      if (lo >= hi) {
          return nums[hi];
      }
      // We arbitrarily pick the last num
      let pivot = nums[hi]

      // i is the position that that the pivot should be in
      // j is the current num
      let i = lo,
          j = lo
      // for every num between lo and hi
      for (; j < hi; j++) {
        // if the current num is less than or equal to the pivot, swap
        if (nums[j] <= pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++
        }
      }
      [nums[i], nums[j]] = [nums[j], nums[i]]
      if (i === nums.length - k) {
        return nums[i]
      } else if (i < nums.length - k) {
        return quickSelect(nums, i + 1, hi);
      } else {
        return quickSelect(nums, lo, i - 1);
      }
    };
};

Runtime: 124 ms
Memory Usage: 37.6 MB

0239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.

Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

Example 2:
Input: nums = [1], k = 1
Output: [1]

Example 3:
Input: nums = [1,-1], k = 1
Output: [1,-1]

Example 4:
Input: nums = [9,11], k = 2
Output: [11]

Example 5:
Input: nums = [4,-2], k = 2
Output: [4]

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

solution:

const maxSlidingWindow = (nums, k) => {
    const q = [];  // stores *indices*
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        while (q && nums[q[q.length - 1]] <= nums[i]) {
            q.pop();
        }
        q.push(i);
        // remove first element if it's outside the window
        if (q[0] === i - k) {
            q.shift();
        }
        // if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
        if (i >= k - 1) {
            res.push(nums[q[0]]);
        }
    }
    return res;    
};

Runtime: 276 ms
Memory Usage: 66.3 MB

0240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
Example:
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.

solution:

const searchMatrix = (matrix, target) => {
  if (matrix.length === 0 || matrix[0].length === 0) {
      return false;
  }

  let i = 0;
  let j = matrix[0].length - 1;

  while (j >= 0 && i < matrix.length) {
    if (matrix[i][j] === target) {
        return true;
    } else if (matrix[i][j] > target) {
        j--;
    } else {
        i++;
    }
  }

  return false;
};

Runtime: 68 ms
Memory Usage: 37.2 MB

0242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false
Note:
You may assume the string contains only lowercase alphabets.

solution 1:

const isAnagram = (s, t) => {
    if (s.length !== t.length) {
        return false;
    }
    const map = {};
    for (let i = 0; i < s.length; i++) {
        map[s[i]] ? map[s[i]]++ : map[s[i]] = 1;
    }
    for (let i = 0; i < t.length; i++) {
        if (map[t[i]]) {
            map[t[i]]--;
        } else {
            return false;
        }
    }
    return true;
};

Runtime: 60 ms
Memory Usage: 36.1 MB

solution 2:

const isAnagram = (s, t) => {
    if (s.length !== t.length) {
        return false;
    }
    return s.split('').sort().toString() === t.split('').sort().toString()
};

Runtime: 112 ms
Memory Usage: 39.9 MB

0295. Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

Example:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

Follow up:
If all integer numbers from the stream are between 0 and 100, how would you optimize it?
If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

solution1:

var MedianFinder = function() {
    this.ary = [];
};

MedianFinder.prototype.addNum = function(num) {
    var low = 0 ; 
    var high = this.ary.length-1;   
    while(low <= high) {
        var mid = Math.floor((high + low)/2);            
        if(this.ary[mid]  < num) {
                low = mid+1;
            }
        else {
            high =mid-1;
        }
    }    
    // insert at  location trick for javascript array.
    this.ary.splice(low, 0, num);  
};

MedianFinder.prototype.findMedian = function() {   
    if(this.ary.length % 2 ==0) {
        var mid = this.ary.length/2;
        return (this.ary[mid] + this.ary[mid-1])/2;
    } else {
        var mid = Math.floor(this.ary.length/2);
        return (this.ary[mid]);
    }
};

Runtime: 240 ms
Memory Usage: 57.1 MB

solution2:

var MedianFinder = function() {
    this.maxHeap = new Heap(Heap.maxComparator);
    this.minHeap = new Heap(Heap.minComparator);
};

MedianFinder.prototype.addNum = function(num) {
    if(this.maxHeap.peek() === null || num < this.maxHeap.peek()) {
        this.maxHeap.add(num);
    } else {
        this.minHeap.add(num);
    }
    
    if(this.maxHeap.size - this.minHeap.size > 1) {
        this.minHeap.add(this.maxHeap.poll());
    } else if(this.minHeap.size - this.maxHeap.size > 1) {
        this.maxHeap.add(this.minHeap.poll());
    }
};

MedianFinder.prototype.findMedian = function() {
    if(this.maxHeap.size > this.minHeap.size) {
        return this.maxHeap.peek();
    } else if(this.maxHeap.size < this.minHeap.size) {
        return this.minHeap.peek();
    } else {
        return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
    }
};

class Heap {
	constructor(comparator) {
		this.size = 0;
		this.values = [];
		this.comparator = comparator || Heap.minComparator;
	}

	add(val) {
		this.values.push(val);
		this.size ++;
		this.bubbleUp();
	}

	peek() {
		return this.values[0] || null;
	}

	poll() {
		const max = this.values[0];
		const end = this.values.pop();
		this.size --;
		if (this.values.length) {
			this.values[0] = end;
			this.bubbleDown();
		}
		return max;
	}

	bubbleUp() {
		let index = this.values.length - 1;
		let parent = Math.floor((index - 1) / 2);

		while (this.comparator(this.values[index], this.values[parent]) < 0) {
			[this.values[parent], this.values[index]] = [this.values[index], this.values[parent]];
			index = parent;
			parent = Math.floor((index - 1) / 2);
		}
	}

	bubbleDown() {
		let index = 0, length = this.values.length;

		while (true) {
			let left = null,
				right = null,
				swap = null,
				leftIndex = index * 2 + 1,
				rightIndex = index * 2 + 2;

			if (leftIndex < length) {
				left = this.values[leftIndex];
				if (this.comparator(left, this.values[index]) < 0) swap = leftIndex;
			}

			if (rightIndex < length) {
				right = this.values[rightIndex];
				if ((swap !== null && this.comparator(right, left) < 0) || (swap === null && this.comparator(right, this.values[index]))) {
					swap = rightIndex;
				}
			}
			if (swap === null) break;

			[this.values[index], this.values[swap]] = [this.values[swap], this.values[index]];
			index = swap;
		}
	}
}

Heap.minComparator = (a, b) => { return a - b; }

Heap.maxComparator = (a, b) => { return b - a; }

Runtime: 248 ms
Memory Usage: 59.3 MB

0347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

solution 1:

const topKFrequent = (nums, k) => {
    const map = {};
    const result = [];
    const bucket = Array(nums.length + 1).fill().map(() => []);
    for (let num of nums) {
        map[num] = ~~map[num] + 1;
    }
    for (let num in map) {
        bucket[map[num]].push(parseInt(num));
    }
    for (let i = nums.length; i >= 0 && k > 0; k--) {
        while (bucket[i].length === 0) i--;
        result.push(bucket[i].shift());
    }
    return result;
};

Runtime: 92 ms
Memory Usage: 45.9 MB

solution 2:

const topKFrequent = (nums, k) => {
    let res = [], map = new Map();
    nums.forEach(n => map.set(n, map.get(n) + 1 || 1));
    let sortedArray = [...map.entries()].sort((a, b) => b[1] - a[1]);
    for(let i = 0; i < k; i++) {
        res.push(sortedArray[i][0]);
    }
    return res;
};

Runtime: 100 ms
Memory Usage: 37.1 MB

0350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

solution:

const intersect = (nums1, nums2) => {
    // track how often each number occurs in first list
    let store = nums1.reduce((map, n) => {
        map[n] = (map[n] + 1) || 1;
        return map;
    }, {});

    // filter out numbers from second list based on
    // how often they occurred in the first list
    return nums2.filter(n => {
        if (store[n]) {
            store[n]--;
            return true;
        } else {
            return false;
        }
    });
};

Runtime: 56 ms
Memory Usage: 34.8 MB

0371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = -2, b = 3
Output: 1

solution:

const getSum = (a, b) => {
    const sum = a ^ b; // XOR derives the sum bits, without carry
    const carry = (a & b) << 1; // AND derives the carry bits
    if (!carry) {
        return sum;
    }
    return getSum(sum, carry);
};

Runtime: 72 ms
Memory Usage: 33.9 MB

0394. Decode String

Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].
Examples:
s = “3[a]2[bc]”, return “aaabcbc”.
s = “3[a2[c]]”, return “accaccacc”.
s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

solution:

const decodeString = (s) =>{
    let multiply = [];
    let tempMult = '';
    let repeatStr = [];
    let solution = '';
    for (let char of s) {
        if(!isNaN(char)) {
            tempMult = `${tempMult}${char}`;
        } else if (char === '[') {
            multiply.push(tempMult);
            tempMult = '';
            repeatStr.push(solution);
            solution = '';
        } else if (char === ']'){
            solution = repeatStr.pop() + solution.repeat(multiply.pop())
        } else {
            solution += char;
        }
    }
    return solution;
}

Runtime: 48 ms
Memory Usage: 34 MB

0406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note:
The number of people is less than 1,100.
Example
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

solution:

const reconstructQueue = (people) => {
    people.sort((a,b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
    let res = [];
    for(let i = 0; i < people.length; i++) {
        res.splice(people[i][1], 0, people[i]);
    }
    return res;
};

Runtime: 80 ms
Memory Usage: 39.4 MB

0412. Fizz Buzz

Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

Example:
n = 15,
Return:
[
“1”,
“2”,
“Fizz”,
“4”,
“Buzz”,
“Fizz”,
“7”,
“8”,
“Fizz”,
“Buzz”,
“11”,
“Fizz”,
“13”,
“14”,
“FizzBuzz”
]

solution 1:

const fizzBuzz = (n) => {
    let results = [];
    for (let i = 1; i <= n; i++) {
        let str = '';
        if (i % 3 === 0) {
            str += 'Fizz';
        }
        if (i % 5 === 0) {
            str += 'Buzz';
        }
        if (str === '') {
            results.push("" + i);
        } else {
            results.push(str);
        }
    }
    return results;
};

Runtime: 64 ms
Memory Usage: 37.6 MB

solution 2:

1
2
3

const fizzBuzz = (n) => {
    return new Array(n).fill(0).map((a, i) => (++i % 3 ? '' : 'Fizz') + (i % 5 ? '' : 'Buzz') || '' + i);
};

Runtime: 64 ms
Memory Usage: 37.1 MB

0438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: “cbaebabacd” p: “abc”
Output:
[0, 6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:
Input:
s: “abab” p: “ab”
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

solution:

const findAnagrams = (s, p) => {
    const resultArray = [];
    const pLength = p.length;
    const sLength = s.length;

    // create two empty arrays with 0 inside
    const pWindow = new Array(26).fill(0);
    const sWindow = new Array(26).fill(0);

    //assume only a-z
    [...p].forEach(character => {
        // charCodeAt returns a--> 97, b --> 98, c--> 99, etc
        pWindow[character.charCodeAt(0) - 97]++;
    });

    [...s].forEach((character, index) => {
        //jump into next position, and minus the previous chart from window
        if (index >= pLength) {
            sWindow[s.charCodeAt(index-pLength) - 97]--;
        }
        sWindow[character.charCodeAt(0) - 97]++;
        // compare two strings
        if (pWindow.join() === sWindow.join()) {
            resultArray.push(index+1-pLength);
        }
    });

    return resultArray
};

Runtime: 252 ms
Memory Usage: 43.8 MB

0739. Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

solution:

const dailyTemperatures = (T) => {
    let res = Array.from({length:T.length},x=>0);
    let stack = [];
    for(let i = 0; i < T.length; i++){
    	while(stack.length > 0 && T[stack[stack.length - 1]] < T[i]){
    		let j = stack.pop();
    		res[j] = i - j;
    	}
    	stack.push(i);
    }
    return res;
};

Runtime: 168 ms
Memory Usage: 42.4 MB

0763. Partition Labels

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:
Input: S = “ababcbacadefegdehijhklij”
Output: [9,7,8]
Explanation:
The partition is “ababcbaca”, “defegde”, “hijhklij”.
This is a partition so that each letter appears in at most one part.
A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.

Note:
S will have length in range [1, 500].
S will consist of lowercase English letters (‘a’ to ‘z’) only.

solution1:

const partitionLabels = (S) => {
    const last = new Array(26).fill(-1);
    const partitions = [];
    let anchor = 0;
    let end = 0;
    
    for (let i = 0; i < S.length; i++) {
        last[S.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
    }
    
    /*
    example
    a b c c a d d b e f f e
    
          a b c d e  f  
    last=[4,7,3,6,11,10]   
    i=0  -> end=max(0,4)=4     anchor=0
    i=1  -> end=max(4,7)=7     anchor=0
    i=2  -> end=max(7,3)=7     anchor=0
    i=3  -> end=max(7,3)=7     anchor=0
    i=4  -> end=max(7,3)=7     anchor=0
    i=5  -> end=max(7,6)=7     anchor=0
    i=6  -> end=max(7,6)=7     anchor=0
    i=7  -> end=max(7,7)=7     anchor=8   partitions.push(7 - 0 + 1)
    i=8  -> end=max(7,11)=11   anchor=8
    i=9  -> end=max(11,10)=11  anchor=8
    i=10 -> end=max(11,10)=11  anchor=8
    i=11 -> end=max(11,11)=11  anchor=12  partitions.push(11 - 8 + 1)  
    partitions = [8, 4]
    */

    for (let i = 0; i < S.length; i++) {
        end = Math.max(end, last[S.charCodeAt(i) - 'a'.charCodeAt(0)]);
        if (i === end) {
            partitions.push(i - anchor + 1);
            anchor = i + 1;
        }
    }
    return partitions;
};

Runtime: 92 ms
Memory Usage: 39.2 MB

solution2:

const partitionLabels = (S) => {
    const ht = {};
	let results = [];

    for(let i = 0; i < S.length; i++) {
    	if(!ht.hasOwnProperty(S.charAt(i))) {
    		ht[S.charAt(i)] = {min: i, max: i};
    	} else {
    		ht[S.charAt(i)].max = i;
    	}
    }

	for(char in ht) {
		if(!results.length || ht[char].min > results[results.length - 1].max) {
			results.push({min: ht[char].min, max: ht[char].max});
		} else if(ht[char].min < results[results.length - 1].max && ht[char].max > results[results.length - 1].max) {
			 results[results.length - 1].max = ht[char].max
		}
	}

	return results.map(result => {
		return result.max - result.min + 1;
	});
};

Runtime: 88 ms
Memory Usage: 41.1 MB