LeetCode 907 - Sum of Subarray Minimums


https://leetcode.com/problems/sum-of-subarray-minimums/
Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.
Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:
Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.
https://zxi.mytechroad.com/blog/stack/leetcode-907-sum-of-subarray-minimums/
  1. order matters, unlike 花花酱 LeetCode 898. Bitwise ORs of Subarrays we can not sort the numbers in this problem.
    1. e.g. sumSubarrayMins([3, 1, 2, 4]) !=sumSubarrayMins([1, 2, 3, 4]) since the first one will not have a subarray of [3,4].
  2. For A[i], assuming there are L numbers that are greater than A[i] in range A[0] ~ A[i – 1], and there are R numbers that are greater or equal than A[i] in the range of A[i+1] ~ A[n – 1]. Thus A[i] will be the min of (L + 1) * (R + 1) subsequences.
    1. e.g. A = [3,1,2,4], A[1] = 1, L = 1, R = 2, there are (1 + 1) * (2 + 1) = 6 subsequences are 1 is the min number. [3,1], [3,1,2], [3,1,2,4], [1], [1,2], [1,2,4]
Solution2 : Monotonic Stack
Time complexity: O(n)
Space complexity: O(n)
We can use a monotonic stack to compute left[i] and right[i] similar to 花花酱 LeetCode 901. Online Stock Span
  public int sumSubarrayMins(int[] A) {
    final int kMod = 1000000007;
    final int n = A.length;
    Stack<Integer> nums = new Stack<>();
    Stack<Integer> lens = new Stack<>();
    int[] left = new int[n];
    int[] right = new int[n];
    int ans = 0;
    
    for (int i = 0; i < n; ++i) {
      int len = 1;
      while (!nums.empty() && nums.peek() > A[i]) {
        len += lens.pop(); nums.pop();
      }
      nums.push(A[i]);
      lens.push(len);
      left[i] = len;
    }
    nums.clear();
    lens.clear();
    for (int i = n - 1; i >= 0; --i) {
      int len = 1;
      while (!nums.empty() && nums.peek() >= A[i]) {
        len += lens.pop(); nums.pop();
      }
      nums.push(A[i]);
      lens.push(len);
      right[i] = len;
    }
    
    for (int i = 0; i < n; ++i)
      ans = (int)(ans + (long)A[i] * left[i] * right[i]) % kMod;
    
    return ans;
  }
实际上是要求
res = sum(A[i] * f(i))，其中f(i)是子数组的数量，A[i]是最小值。
为了得到f(i)，我们要得到
  • left[i]，能在A[i]左侧取得的最长宽度，使得在这个范围内A[i]是最小值,且都大于A[i]
  • right[i], 能在A[i]右侧取得的最长宽度，使得在这个范围内A[i]是最小值，且都大于等于A[i]
然后，
  • A[i]左侧有left[i] + 1种连续子数组的取法
  • A[i]右侧有right[i] + 1种连续子数组的取法
最后根据f(i) = (left[i] + 1) * (right[i] + 1)即可求得f(i)
所以这个问题在于求left[i]和right[i]
举例，对于[3,1,2,4]：
left + 1 = [1,2,1,1]
right + 1 = [1,3,2,1]
f = [1,6,2,1]
res = 3 * 1 + 1 * 6 + 2 * 2 + 4 * 1 = 17
那么，解释一下为什么left[i]要取大于A[i]，而right[i]只需要取大于等于A[i]：
他是为了解决数组中有相等的数的情况。
假设有数组...a1...a2...a3... ...an...其中，a1=a2=a3=...=an，那么这个连续数组的各种组合中，起点可以起自...a1, ...a2, ...a3，直到...an，而终点则可以尽可能地往右边取。
所以在i=a1处，left[i]最多取到a1，而在i=a2处，left[i]最少也取到a1+1。如此类推，起点可以从...a1...a2一直取到an，而终点可以从起点一直取到最右侧（只要大于等于起点的值），如此可以把全部的连续子数组的情况覆盖。
算法
那么怎么求得left[i]和right[i]呢？我们可以看以下两个同类型的问题的讨论:
答案主要有两种做法，一种是用栈，一种是用数组。
解决方案1：栈
[C++/Java/Python] O(1)
就是用increasing stack来解决问题。
解决方案2：数组
5ms O(n) Java solution explained (beats 96%)
本来遍历要一个一个遍历的，像这样：
for (int i = 1; i < height.length; i++) {              
    int p = i - 1;
    while (p >= 0 && height[p] >= height[i]) {
        p--;
    }
    lessFromLeft[i] = p;              
}
但我们可以改良它，在往前遍历时不一个一个地遍历，而是利用之前的计算结果，直接“跳”过多个元素:
while (p >= 0 && height[p] >= height[i]) {
      p = lessFromLeft[p];
}

Approach 2: Maintain Stack of Minimums
For a specific j, let's try to count the minimum of each subarray [i, j]. The intuition is that as we increment j++, these minimums may be related to each other. Indeed, min(A[i:j+1]) = min(A[i:j], A[j]).
Playing with some array like A = [1,7,5,2,4,3,9], with j = 6 the minimum of each subarray [i, j]is B = [1,2,2,2,3,3,9]. We can see that there are critical points i = 0, i = 3, i = 5, i = 6where a minimum is reached for the first time when walking left from j.
Algorithm
Let's try to maintain an RLE (run length encoding) of these critical points B. More specifically, for the above (A, j), we will maintain stack = [(val=1, count=1), (val=2, count=3), (val=3, count=2), (val=9, count=1)], that represents a run length encoding of the subarray minimums B = [1,2,2,2,3,3,9]. For each j, we want sum(B).
As we increment j, we will have to update this stack to include the newest element (val=x, count=1). We need to pop off all values >= x before, as the minimum of the associated subarray [i, j] will now be A[j] instead of what it was before.
At the end, the answer is the dot product of this stack: \sum\limits_{e\text{ } \in \text{ stack}} e\text{.val} * e\text{.count}, which we also maintain on the side as the variable dot.
    public int sumSubarrayMins(int[] A) {
        int MOD = 1_000_000_007;

        Stack<RepInteger> stack = new Stack();
        int ans = 0, dot = 0;
        for (int j = 0; j < A.length; ++j) {
            // Add all answers for subarrays [i, j], i <= j
            int count = 1;
            while (!stack.isEmpty() && stack.peek().val >= A[j]) {
                RepInteger node = stack.pop();
                count += node.count;
                dot -= node.val * node.count;
            }
            stack.push(new RepInteger(A[j], count));
            dot += A[j] * count;
            ans += dot;
            ans %= MOD;
        }

        return ans;
    }
}

class RepInteger {
    int val, count;
    RepInteger(int v, int c) {
        val = v;
        count = c;
    }
}

I guess this is a general intuition for most solution.
res = sum(A[i] * f(i))
where f(i) is the number of subarrays,
in which A[i] is the minimum.
To get f(i), we need to find out:
left[i], the length of strict bigger numbers on the left of A[i],
right[i], the length of bigger numbers on the right of A[i].
Then,
left[i] + 1 equals to
the number of subarray ending with A[i],
and A[i] is single minimum.
right[i] + 1 equals to
the number of subarray starting with A[i],
and A[i] is the first minimum.
Finally f(i) = (left[i] + 1) * (right[i] + 1)
For [3,1,2,4] as example:
left + 1 = [1,2,1,1]
right + 1 = [1,3,2,1]
f = [1,6,2,1]
res = 3 * 1 + 1 * 6 + 2 * 2 + 4 * 1 = 17

Explanation:

To calculate left[i] and right[i],
we use two increasing stacks.
It will be easy if you can refer to this problem and my post:
901. Online Stock Span
I copy some of my codes from this solution.

More:

For some more similar problem, I suggest
828. Unique Letter String
891. Sum of Subsequence Widths

Complexity:

All elements will be pushed twice and popped at most twice
O(N) time, O(N) space
    public int sumSubarrayMins(int[] A) {
        int res = 0, n = A.length, mod = (int)1e9 + 7;
        int[] left = new int[n], right = new int[n];
        Stack<int[]> s1 = new Stack<>(), s2 = new Stack<>();
        for (int i = 0; i < n; ++i) {
            int count = 1;
            while (!s1.isEmpty() && s1.peek()[0] > A[i])
                count += s1.pop()[1];
            s1.push(new int[] {A[i], count});
            left[i] = count;
        }
        for (int i = n - 1; i >= 0; --i) {
            int count = 1;
            while (!s2.isEmpty() && s2.peek()[0] >= A[i])
                count += s2.pop()[1];
            s2.push(new int[] {A[i], count});
            right[i] = count;
        }
        for (int i = 0; i < n; ++i)
            res = (res + A[i] * left[i] * right[i]) % mod;
        return res;
    }

    int sumSubarrayMins(vector<int>& A) {
        stack<pair<int, int>> leftStack, rightStack;
        int n = A.size();
        int left[n], right[n];

        leftStack.emplace(-1, -1);  // val, idx
        for (int i = 0; i < n; i++) {
            while (!leftStack.empty() && leftStack.top().first >= A[i])
                leftStack.pop();
            if (leftStack.top().second == -1)
                left[i] = i;
            else
                left[i] = i - leftStack.top().second - 1;

            leftStack.emplace(A[i], i);
        }

        rightStack.emplace(-1, -1);
        for (int i = n - 1; i >= 0; i--) {
            // 对于leftStack，此处写的是>=
            // 这意味着对于同一子序列中有多个最小元素的情况，
            // 我们选择把这种情况的值最右侧的最小元素中计算。
            // （防止重复计算）
            while (!rightStack.empty() && rightStack.top().first > A[i])
                rightStack.pop();
            if (rightStack.top().second == -1)
                right[i] = n - i - 1;
            else
                right[i] = rightStack.top().second - i - 1;

            rightStack.emplace(A[i], i);
        }

        long long int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (left[i] + 1) * (right[i] + 1) * (long long int) A[i] % 1000000007;
            sum %= 1000000007;
        }
        return sum;
    }
显然一种较好的思路是，对于A中的每一个值A[i]，寻找以它为最小值的子序列的数量。也就是说，我们需要寻找A[i]左侧第一个比它大的值的位置，以及右侧第一个比它大的值的位置。然后就可以计算对应的子序列的数量了。

这个过程可以简化为使用一个栈。对于被某个数从栈中弹出的数而言，它右侧第一个比它小的数就是这个数。所以我们可以对所有被弹出的数得到左侧的区间范围和右侧的区间范围。我觉得这是一种非常聪明的做法

1.Here I record (A[i], count) in the stack.
We can also only record index.
2. For left part and right part, the logic is same.
So for each, I used one stack and one pass.
This process can be optimized to one pass using one stack in total.


    public int sumSubarrayMins(int[] A) {
        Stack<Integer> s = new Stack<>();
        int n = A.length, res = 0, mod = (int)1e9 + 7, j,k;
        for (int i = 0; i <= n; i++) {
            while (!s.isEmpty() && A[stack.peek()] > (i == n ? 0 : A[i])) {
                j = stack.pop();
                k = stack.isEmpty() ? -1 : stack.peek();
                res = (res + A[j] * (i - j) * (j - k)) % mod;
            }
            stack.push(i);
        }
        return res;
    }

Let's try to count the number of subarrays #(j) for which A[j] is the right-most minimum. Then, the answer will be sum #(j) * A[j]. (We must say right-most so that we form disjoint sets of subarrays and do not double count any, as the minimum of an array may not be unique.)
This in turn brings us the question of knowing the smallest index i <= j for which A[i], A[i+1], ..., A[j] are all <= A[j]; and the largest index k >= j for which A[j+1], A[j+2], ..., A[k] are all < A[j].
Algorithm
For example, if A = [10, 3, 4, 5, _3_, 2, 3, 10] and we would like to know #(j = 4) [the count of the second 3, which is marked], we would find i = 1 and k = 5.
From there, the actual count is #(j) = (j - i + 1) * (k - j + 1), as there are j - i + 1 choices i, i+1, ..., j for the left index of the subarray, and k - j + 1 choices j, j+1, ..., k for the right index of the subarray.
Answering these queries (ie. determining (i, k) given j) is a classic problem that can be answered with a stack. We'll focus on the problem of finding i: the problem of finding k is similar.
Making a Prev Array
The idea is to maintain stack, a monotone decreasing subsequence of A (actually, indices of A in implementation). These represent candidate boundaries i* - 1 for the next query, stored in increasing order of A[i*].
Now considering j in increasing order, we can remove candidates for which A[i*] <= A[j] in decreasing order of i*.
For example, if A = [10, 5, 3, 7, 0, 4, 5, 2, 1, _8_], then when considering j = 9 (A[j] = 8), we have a stack of boundaries like [-1, 0, 3, 6] (representing A[i*] = -inf, 10, 7, 5). We pop 6 and 3 from the stack, as 5 <= 8 and 7 <= 8, and we get the answer boundary i* - 1 = 0.
Note that this process is linear, since we do a linear amount of pushes and pops of the stack in total.
This is quite difficult to figure out, but this type of technique occurs often in many other problems, so it is worth learning in detail.
    public int sumSubarrayMins(int[] A) {
        int MOD = 1_000_000_007;
        int N = A.length;

        // prev has i* - 1 in increasing order of A[i* - 1]
        // where i* is the answer to query j
        Stack<Integer> stack = new Stack();
        int[] prev = new int[N];
        for (int i = 0; i < N; ++i) {
            while (!stack.isEmpty() && A[i] <= A[stack.peek()])
                stack.pop();
            prev[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        // next has k* + 1 in increasing order of A[k* + 1]
        // where k* is the answer to query j
        stack = new Stack();
        int[] next = new int[N];
        for (int k = N-1; k >= 0; --k) {
            while (!stack.isEmpty() && A[k] < A[stack.peek()])
                stack.pop();
            next[k] = stack.isEmpty() ? N : stack.peek();
            stack.push(k);
        }

        // Use prev/next array to count answer
        long ans = 0;
        for (int i = 0; i < N; ++i) {
            ans += (i - prev[i]) * (next[i] - i) % MOD * A[i] % MOD;
            ans %= MOD;
        }
        return (int) ans;

    }

What is monotonous increase stack?

Roughly speaking, the elements in the an monotonous increase stack keeps an increasing order.

The typical paradigm for monotonous increase stack:

for(int i = 0; i < A.size(); i++){
  while(!in_stk.empty() && in_stk.top() > A[i]){
    in_stk.pop();
  }
  in_stk.push(A[i]);
}

What can monotonous increase stack do?

(1) find the previous less element of each element in a vector with O(n) time:
  • What is the previous less element of an element?
    For example:
    [3, 7, 8, 4]
    The previous less element of 7 is 3.
    The previous less element of 8 is 7.
    The previous less element of 4 is 3.
    There is no previous less element for 3.
For simplicity of notation, we use abbreviation PLE to denote Previous Less Element.
  • C++ code (by slitghly modifying the paradigm):
    Instead of directly pushing the element itself, here for simplicity, we push the index.
    We do some record when the index is pushed into the stack.
// previous_less[i] = j means A[j] is the previous less element of A[i].
// previous_less[i] = -1 means there is no previous less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
  while(!in_stk.empty() && A[in_stk.top()] > A[i]){
    in_stk.pop();
  }
  previous_less[i] = in_stk.empty()? -1: in_stk.top();
  in_stk.push(i);
}
(2) find the next less element of each element in a vector with O(n) time:
  • What is the next less element of an element?
    For example:
    [3, 7, 8, 4]
    The next less element of 8 is 4.
    The next less element of 7 is 4.
    There is no next less element for 3 and 4.
For simplicity of notation, we use abbreviation NLE to denote Next Less Element.
  • C++ code (by slighly modifying the paradigm):
    We do some record when the index is poped out from the stack.
// next_less[i] = j means A[j] is the next less element of A[i].
// next_less[i] = -1 means there is no next less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
  while(!in_stk.empty() && A[in_stk.top()] > A[i]){
    auto x = in_stk.top(); in_stk.pop();
    next_less[x] = i;
  }
  in_stk.push(i);
}

How can the monotonous increase stack be applied to this problem?



For example:
Consider the element 3 in the following vector:

                            [2, 9, 7, 8, 3, 4, 6, 1]
        |                    |
              the previous less       the next less 
                 element of 3          element of 3
After finding both NLE and PLE of 3, we can determine the
distance between 3 and 2(previous less) , and the distance between 3 and 1(next less).
In this example, the distance is 4 and 3 respectively.
How much the element 3 contributes to the final answer?
It is 3*(4*3).
What is the final answer?
Denote by left[i] the distance between element A[i] and its PLE.
Denote by right[i] the distance between element A[i] and its NLE.
The final answer is,
sum(A[i]*left[i]*right[i] )

The last thing that needs to be mentioned for handling duplicate elements:

Method: Set strict less and non-strict less(less than or equal to) for finding NLE and PLE respectively. The order doesn't matter.
For example, the above code for finding NLE is strict less, while PLE is actually non-strict less.
Remark: Although in both loop conditions the signs are set as >, for NLE, we make records inside the loop, while for PLE, records are done outside the loop.

The solution (One pass)


  int sumSubarrayMins(vector<int>& A) {
    stack<pair<int, int>> in_stk_p, in_stk_n;
    // left is for the distance to previous less element
    // right is for the distance to next less element
    vector<int> left(A.size()), right(A.size());
  
    //initialize
    for(int i = 0; i < A.size(); i++) left[i] =  i + 1;
    for(int i = 0; i < A.size(); i++) right[i] = A.size() - i;
  
    for(int i = 0; i < A.size(); i++){
      // for previous less
      while(!in_stk_p.empty() && in_stk_p.top().first > A[i]) in_stk_p.pop();
      left[i] = in_stk_p.empty()? i + 1: i - in_stk_p.top().second;
      in_stk_p.push({A[i],i});
   
      // for next less
      while(!in_stk_n.empty() && in_stk_n.top().first > A[i]){
        auto x = in_stk_n.top();in_stk_n.pop();
        right[x.second] = i - x.second;
      }
      in_stk_n.push({A[i], i});
    }

    int ans = 0, mod = 1e9 +7;
    for(int i = 0; i < A.size(); i++){
      ans = (ans + A[i]*left[i]*right[i])%mod;
    }
    return ans;
  }
X. Monotone stack
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170776/Python-Simple-Stack-O(n)-Solution-10-lines

I use a monotonous non-decreasing stack to store the left boundary and right boundary where a number is the minimal number in the sub-array
e.g. given [3,1,2,4],
For 3, the boudary is: | 3 | ...
For 1, the boudray is: | 3 1 2 4 |
For 2, the boudray is: ... | 2 4 |
For 4, the boudary is: ... | 4 |
The times a number n occurs in the minimums is |left_bounday-indexof(n)| * |right_bounday-indexof(n)|
The total sum is sum([n * |left_bounday - indexof(n)| * |right_bounday - indexof(n)| for n in array])
After a number n pops out from an increasing stack, the current stack top is n's left_boundary, the number forcing n to pop is n's right_boundary.
A tricky here is to add MIN_VALUE at the head and end.
    def sumSubarrayMins(self, A):
        res = 0
        stack = []  #  non-decreasing 
        A = [float('-inf')] + A + [float('-inf')]
        for i, n in enumerate(A):
            while stack and A[stack[-1]] > n:
                cur = stack.pop()
                res += A[cur] * (i - cur) * (cur - stack[-1]) 
            stack.append(i)
        return res % (10**9 + 7)

https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170857/One-stack-solution

   Stack<Integer> stack = new Stack<>();
    int len = A.length, buff = 0, res = 0;
    for(int i = 0;i <= len;i++){
        if(i == len) buff = 0;
        else buff = A[i];
     
        if(stack.isEmpty() || buff >= A[stack.peek()]){
            stack.push(i);
        }
        else{
            while(!stack.isEmpty() && buff < A[stack.peek()]){
                int idx = stack.pop();
                int left = idx - (stack.isEmpty()?-1:stack.peek());
                int right = i - idx;
                res = (res + A[idx] * left * right) % 1000000007;
            }
            stack.push(i);
        }
    }
    return res;
}

X. Monotone stack + DP
https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170769/Java-O(n)-monotone-stack-with-DP

stack: Increasing stack, store the index
dp[i + 1]: Sum of minimum of subarrays which end with A[i]
dp[i + 1] = dp[prev + 1] + (i - prev) * A[i], where prev is the last number which is less than A[i], since we maintain a monotonous increasing stack, prev = stack.peek()

eg. [3, 1, 2, 4, 3], when i = 4, all subarrays end with A[4]:
[3]
[4, 3]
[2, 4, 3]
[1, 2, 4, 3]
[3, 1, 2, 4, 3]
In this case, stack.peek() = 2, A[2] = 2.
For the first 2 subarrays [3] and [4, 3], sum of minimum = (i - stack.peek()) * A[i] = 6.
For the last 3 subarrays [2, 4, 3], [1, 2, 4, 3] and [3, 1, 2, 4, 3], since they all contain a 2 which is less than 3, sum of minimum = dp[stack.peek() + 1] = 4.
Then, dp[i + 1] = 4 + 6 = 10

class Solution {
    public int sumSubarrayMins(int[] A) {
        Stack<Integer> stack = new Stack<>();
        int[] dp = new int[A.length + 1];
        stack.push(-1);
        int result = 0, M = (int)1e9 + 7;
        for (int i = 0; i < A.length; i++) {
            while (stack.peek() != -1 && A[i] <= A[stack.peek()]) {
                stack.pop();
            }
            dp[i + 1] = (dp[stack.peek() + 1] + (i - stack.peek()) * A[i]) % M;
            stack.push(i);
            result += dp[i + 1];
            result %= M;
        }
        return result;
    }
}
X.
Solution 1: Brute Force
Time complexity: O(n^2)
  public int sumSubarrayMins(int[] A) {
    final int kMod = 1000000007;
    final int n = A.length;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int left = 0;
      for (int j = i - 1; j >= 0 && A[j] > A[i]; --j, ++left);
      int right = 0;
      for (int j = i + 1; j < n && A[j] >= A[i]; ++j, ++right);
      ans = (int)((ans + (long)A[i] * (left + 1) * (right + 1)) % kMod);
    }
    return ans;
  }


http://blog.leanote.com/post/edlinlink@qq.com/907
at
Labels: , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • Minimum area of a square enclosing given set of points
    Problem solving with programming: Minimum area of a square enclosing given set of points Given a set of coordinates in a two dimensional ...
  • HackerRank: N Puzzle
    HackerRank: N Puzzle N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to ...
  • LeetCode 394 - Decode String
    Follow up:  LeetCode 471 - Encode String with Shortest Length https://leetcode.com/problems/decode-string/ Given an encoded string, retu...
  • Hilbert Curve - Airbnb
    airbnb面试题汇总 Hilbert Curve Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步 int hilbertCurve(...
  • Find sum of sum of all subsequences
    https://www.geeksforgeeks.org/find-sum-sum-sub-sequences/ Given an array of  n  integers. The task is to find the sum of sum of each of s...