Category: Algorithms

[LeetCode] 773. Sliding Puzzle

Solution Bidirectional BFS Set two queues, src queue and dest queue. Init src queue with input board, and dest queue with final state [[1,2,3],[4,5,0]]. When…

Full Post

[LeetCode] 327. Count of Range Sum

Solution A similar question is Leetcode 493, counting reverse pairs. A data structure “Binary Indexed Tree”, BIT, would help. Steps: Calculate prefix sum. -> sum[]…

Full Post

[LeetCode] 215. Kth Largest Element in an Array

Solution Official solutions have several approaches including sorting, heap, and quick selecting. They are all great. I’d like to put forward another solution: Binary Search….

Full Post

[LeetCode]307. Range Sum Query – Mutable

Solution Use “Binary Indexed Tree (BIT)” (Fenwick Tree) data structure which supports querying prefix sum and adding a value to a single point. Binary Indexed…

Full Post

[LeetCode] 239. Sliding Window Maximum

Solution There are several approaches to solve this problem, like sliding window or DP. A more general description of this problem is how to quickly…

Full Post

[LeetCode] 968. Binary Tree Cameras

Solution This problem can be reduced to Minimum Dominating Set problem in Trees. Find minimum set of vertices such that every vertex is in or…

Full Post

[LeetCode] 644. Maximum Average Subarray II

Solution Since the average must be> = the smallest element in the array, and <= the largest element in the array, we can perform binary…

Full Post

[LeetCode] 1273. Delete Tree Nodes

Solution Do dfs on tree and check on backtracking if sum from children to current node equals to 0, if yes, trim it and its…

Full Post

Comparisons among distributed election algorithms(Bully, Raft and ZAB)

Introduction We often hear concepts such as database clusters , and also know that database clusters provide read and write functions. So how to make…

Full Post

Kth shortest path problem

Kth shortest path problem Description Given a directed graph of N nodes (1, 2 … N) and M edges, find the the Kth shortest path…

Full Post