Advanced Leetcode Techniques - dohdat/leetcode-practice GitHub Wiki
var findJudge = function(n, trust) {
let trustCounts = new Array(n + 1).fill(0);
for (let [a, b] of trust) {
trustCounts[a]--;
trustCounts[b]++;
}
for (let i = 1; i < trustCounts.length; i++) {
if (trustCounts[i] === n - 1) {
return i;
}
}
return -1;
};Find the shortest path from k to n
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
var networkDelayTime = function (times, n, k) {
// Our return value, how long did it take
// to reach all nodes within the network from {k}
let time_taken = 0;
// A set so we don't visit the same node twice.
const visited_set = new Set();
const min_heap = new MinPriorityQueue();
// An adjacency list, where we store
// Node -> [[Edge, Cost],[Edge, Cost]]
const node_edge_cost = new Map();
// Build the adjacency list.
for (const [node, edge, cost] of times) {
let edges = [];
if (node_edge_cost.has(node)) {
edges = node_edge_cost.get(node);
}
edges.push([edge, cost]);
node_edge_cost.set(node, edges);
}
// We have been asked to start at {k}
// So we enqueue {k} at the cost of 0, as of course
// it costs nothing as we start here.
min_heap.enqueue([k, 0], 0);
while (min_heap.size()) {
// Get the cheapest operation relative to {k}
// Node and cost
const [node, cost] = min_heap.dequeue().element;
// Have we already been here? No loops today kiddo
if (visited_set.has(node)) continue;
// Set it. We don't want to come back here.
visited_set.add(node);
// Did our distance increase?
// If so, update it. If not, keep the same
time_taken = Math.max(cost, time_taken);
// Get the edges for this node (If any)
const node_edges = node_edge_cost.get(node) || [];
for (const [edge_node, edge_cost] of node_edges) {
if (!visited_set.has(edge_node)) {
// Add it to the queue, set the priority to the cost of the edge
// So we only ever visit the cheapest edge.
min_heap.enqueue([edge_node, edge_cost + cost], edge_cost + cost);
}
}
}
// Did we visit every node?
// If not, we failed to spread the message across the network.
// If so, return the time taken.
return visited_set.size === n ? time_taken : -1;
};Time Complexity: O(E log V)
Works when there is negative weight edge. Slower than Dijkstra.
var networkDelayTime = function(times, n, k) {
let arr = new Array(n + 1).fill(Infinity);
arr[k] = 0;
for (let i = 0; i <= n; i++) {
let temp = arr.slice();
for (let [source, target, cost] of times) {
if (temp[source] === Infinity) continue;
temp[target] = Math.min(temp[target], temp[source] + cost);
}
arr = temp;
}
arr.shift();
let res = Math.max(...arr);
return res === Infinity ? -1 : res;
};Time Complexity: O ( V ⋅ E )
Find all possible paths from source to target. Return them in any order.
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
var allPathsSourceTarget = function(graph) {
let res = [];
let target = graph.length - 1;
function dfs(node, path) {
path.push(node);
if (node === target) {
res.push(path);
return;
}
let visiting = graph[node];
for(let cur of visiting) {
dfs(cur, [...path])
}
}
dfs(0, []);
return res;
};Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.
Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
**Explanation: **
We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.
var minCostConnectPoints = function(points) {
let cost = 0;
let n = points.length;
let dist = new Array(n).fill(Infinity);
dist[0] = 0;
let next = 0;
for (let i = 1; i < n; i++) {
let min = Infinity;
let point = -1;
for (let j = 1; j < n; j++) {
let [x1, y1] = points[j];
let [x2, y2] = points[next];
if (dist[j] > 0) {
dist[j] = Math.min(dist[j], Math.abs(x1 - x2) + Math.abs(y1 - y2));
if (dist[j] < min) {
min = dist[j];
point = j;
}
}
}
cost += min;
dist[point] = 0;
next = point;
}
return cost;
};Return the correct order you should take to finish all courses.
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
var findOrder = function(numCourses, prerequisites) {
let preMap = new Map();
//Create a set, not an array, so that we do not add visited nodes
let res = new Set();
let visited = new Set();
//create adjList
for (let [crs, pre] of prerequisites) {
preMap.set(crs, (preMap.get(crs) || []).concat(pre));
}
function dfs(node) {
if (visited.has(node)) return false;
visited.add(node);
let visiting = preMap.get(node);
while (visiting && visiting.length > 0) {
let c = visiting.shift();
if (!dfs(c)) return false;
}
visited.delete(node);
res.add(node);
return true;
}
for (let i = 0; i < numCourses; i++) {
if (!dfs(i)) return [];
}
return [...res];
};Time Complexity: O(V+E), where V = vertices, E = Edges.
A Union-Find data structure is to maintain a set of elements partitioned into a number of mutually disjoint (non-overlapping) subsets. So no elements belong to more than one set.
Applications:
-
connected component in Graph problem.
-
detecting cycles in graph.
-
minimum spanning tree.
Question:
Find if Path Exists in Graph
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
var validPath = function(n, edges, source, destination) {
let parent = new Array(n);
for (let i = 0; i < parent.length; i++) {
parent[i] = i;
}
function find(a) {
while (parent[a] !== a) {
parent[a] = parent[parent[a]];
a = parent[a];
}
return a;
}
function union(a, b) {
const rootA = find(a);
const rootB = find(b);
if (rootA !== rootB) {
parent[rootA] = rootB;
}
}
for (let [a, b] of edges) {
union(a, b);
}
return find(source) === find(destination);
};Time Complexity: O(log n)
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
var merge = function(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let prev = intervals[0];
let res = [prev];
for (let i = 0; i < intervals.length; i++) {
let c = intervals[i];
if (c[0] <= prev[1]) {
prev[1] = Math.max(prev[1], c[1]);
} else {
res.push(c);
prev = c;
}
}
return res;
}; Return true if there is a cycle in the linked list. Otherwise, return false.
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
var hasCycle = function(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
};Heaps are structures meant to allow quick access to the min or the max.
Can get acccess to max or min at constant time O(1)
Time complexity: O(nlogn)
MaxPriorityQueue
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
var topKFrequent = function(nums, k) {
let map = new Map();
let maxHeap = new MaxPriorityQueue(item => item.value);
// O(n) Time complexity
for (let num of nums) {
map.set(num, (map.get(num) || 0) + 1);
}
let ans = [];
// We are building a maxHeap for the D unique item
// O(D) time complexity
for (let [key, value] of map) {
maxHeap.enqueue(key, value);
}
for (let i = 0; i < k; i++) {
// We are dequeuing the k elements which can take upto O(klogD)
let _item = maxHeap.dequeue();
ans.push(_item.element);
}
return ans;
};MinPriorityQueue
Return the closest point to origin.
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
var kClosest = function(points, k) {
let q = new MinPriorityQueue({ priority: (x) => x[0] });
let res = [];
function calculateDis([a, b]) {
return a * a + b * b;
}
for (let p of points) {
q.enqueue([calculateDis(p), p]);
}
for (let i = 0; i < k; i++) {
let c = q.dequeue().element;
res.push(c[1]);
}
return res;
};Greedy is an algo approach that builds up a solution piece by piece, always choosing the next piece that offers that most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are the best fit for Greedy.
Question:
Given an integer array nums, find the subarray which has the largest sum and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
var maxSubArray = function(nums) {
let res = nums[0];
let curMax = 0;
for (let n of nums) {
if (curMax < 0) {
curMax = 0;
}
curMax += n;
res = Math.max(res, curMax);
}
return res;
};Given an integer array nums, return the length of the longest strictly increasing subsequence.
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
var lengthOfLIS = function(nums) {
const dp = new Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
};Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
var rob = function(nums) {
let n = nums.length;
if (nums === null || n === 0) {
return 0;
}
let dp = new Array(n);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
};You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
-
1 step + 1 step + 1 step
-
1 step + 2 steps
-
2 steps + 1 step
var climbStairs = function(n) {
let memo = [];
function dfs(step, end) {
if (step === end) {
return 1;
}
if (end < step) {
return 0;
}
if (memo[step]) {
return memo[step];
}
memo[step] = dfs(step + 1, end) + dfs(step + 2, end);
return memo[step];
}
return dfs(0, n);
};Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
var longestCommonSubsequence = function(text1, text2) {
const memo = new Map();
function recursion(index1, index2) {
// base cases
if (index1 < 0 || index2 < 0) return 0;
const key = index1 + "#" + index2;
if (memo.has(key)) return memo.get(key);
let result = 0;
if (text1[index1] === text2[index2]) {
result = recursion(index1 - 1, index2 - 1) + 1;
} else {
result = Math.max(
recursion(index1, index2 - 1),
recursion(index1 - 1, index2)
);
}
memo.set(key, result);
return result;
}
return recursion(text1.length - 1, text2.length - 1);
};Given an m x n board of characters and a list of strings words, return all words on the board.
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"]
var findWords = function(board, words) {
let rows = board.length;
let cols = board[0].length;
let res = new Set();
let visited = new Array(rows).fill(false).map(() => new Array(cols).fill(false));
function TrieNode() {
this.children = new Map();
this.end = false;
}
let root = new TrieNode();
function add(word) {
let cur = root;
for (let c of word) {
if (!cur.children.has(c)) {
cur.children.set(c, new TrieNode());
}
cur = cur.children.get(c);
}
cur.end = true;
}
//add all the words to Trie
for (let word of words) {
add(word);
}
function dfs(r, c, node, word) {
if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] || !node.children.get(board[r][c])) {
return;
}
visited[r][c] = true;
word += board[r][c];
node = node.children.get(board[r][c]);
if (node.end) {
res.add(word);
}
dfs(r - 1, c, node, word);
dfs(r + 1, c, node, word);
dfs(r, c - 1, node, word);
dfs(r, c + 1, node, word);
visited[r][c] = false;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
dfs(r, c, root, '');
}
}
return [...res];
};Write a function that takes an unsigned integer and returns the number of '1' bits it has.
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
var hammingWeight = function(n) {
let count = 0;
while (n !== 0) {
let bitComp = n & 1; //1 &1 will return 1, 0 &1 will return 0
if (bitComp === 1) count++;
n >>>= 1; // unsigned right shift assignment (chop off the last bit and assign it)
}
return count;
};
