花花酱 LeetCode 907. Sum of Subarray Minimums

By zxi on September 16, 2018

Problem

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.

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

Idea

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].
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]

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 1504 ms

class Solution {

public:

int sumSubarrayMins(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

int ans = 0;

for (int i = 0; i < A.size(); ++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 < A.size() && A[j] >= A[i]; ++j, ++right);

ans = (ans + static_cast<long>(A[i]) * (left + 1) * (right + 1)) % kMod;

}

return ans;

}

};

Java

// Author: Huahua, 511 ms

class Solution {

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;

}

Python3 (TLE)

# Author: Huahua, 96/100 passed

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

ans = 0

for i in range(n):

left, right = 1, 1

while i - left >= 0 and A[i - left] > A[i]:

left += 1

while i + right < n and A[i + right] >= A[i]:

right += 1

ans += A[i] * left * right

return ans % kMod

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

C++

// Author: Huahua, 60 ms

class Solution {

public:

int sumSubarrayMins(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

const int n = A.size();

vector<int> left(n);

vector<int> right(n);

stack<pair<int, int>> s;

int ans = 0;

for (int i = 0; i < n; ++i) {

int len = 1;

while (!s.empty() && s.top().first > A[i]) {

len += s.top().second; s.pop();

}

s.emplace(A[i], len);

left[i] = len;

}

while (!s.empty()) s.pop();

for (int i = n - 1; i >= 0; --i) {

int len = 1;

while (!s.empty() && s.top().first >= A[i]) {

len += s.top().second; s.pop();

}

s.emplace(A[i], len);

right[i] = len;

}

for (int i = 0; i < n; ++i)

ans = (ans + static_cast<long>(left[i]) * A[i] * right[i]) % kMod;

return ans;

}

};

Java

// Author: Huahua, 154 ms

class Solution {

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;

}

Python3

# Author: Huahua, 376 ms

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

s, left, right = [], [1] * n, [1] * n

for i in range(n):

while s and s[-1][0] > A[i]:

left[i] += s.pop()[1]

s.append((A[i], left[i]))

s = []

for i in range(n - 1, -1, -1):

while s and s[-1][0] >= A[i]:

right[i] += s.pop()[1]

s.append((A[i], right[i]))

ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod

return ans

Python3 V2

# Author: Huahua, 366 ms

class Solution:

def sumSubarrayMins(self, A):

kMod = 10 ** 9 + 7

n = len(A)

left, right = [1] * n, [1] * n

def fillLength(counts, start, end, step):

s = []

for i in range(start, end, step):

num = A[i] if step > 0 else A[i] - 1

while s and s[-1][0] > num:

counts[i] += s.pop()[1]

s.append((A[i], counts[i]))

fillLength(left, 0, n, 1)

fillLength(right, n - 1, -1, -1)

ans = sum(a * l * r for a, l, r in zip(A, left, right)) % kMod

return ans

花花酱 LeetCode 905. Sort Array By Parity

By zxi on September 15, 2018

Problem

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]

Output: [2,4,3,1]

The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

Solution 1: Split Odd/Even

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> sortArrayByParity(vector<int>& A) {

vector<int> even;

vector<int> odd;

for (int a : A) {

if (a % 2) odd.push_back(a);

else even.push_back(a);

}

even.insert(end(even), begin(odd), end(odd));

return even;

}

};

Solution 2: Stable sort by key % 2

Time complexity: O(nlogn)

Space complexity: O(1) in-place

C++

// Author: Huahua, 52 ms

class Solution {

public:

vector<int> sortArrayByParity(vector<int>& A) {

stable_sort(begin(A), end(A), [](int a, int b){

return a % 2 < b % 2;

});

return A;

}

};

花花酱 LeetCode 904. Fruit Into Baskets

By zxi on September 15, 2018

Problem

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets. If you cannot, stop.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].

Example 3:

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Example 4:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

Solution: Hashtable + Sliding window

Time complexity: O(n)

Space complexity: O(1)

Keep track of the last index of each element. If a third type of fruit comes in, the new window starts after the fruit with smaller last index. Otherwise extend the current window.

[1 3 1 3 1 1] 4 1 4 … <- org window, 3 has a smaller last index than 1.

1 3 1 3 [1 1 4] 1 4 … <- new window

C++

// Author: Huahua, 144 ms

class Solution {

public:

int totalFruit(vector<int>& tree) {

map<int, int> idx; // {fruit -> last_index}

int ans = 0;

int cur = 0;

for (int i = 0; i < tree.size(); ++i) {

int f = tree[i];

if (!idx.count(f)) {

if (idx.size() == 2) {

auto it1 = begin(idx);

auto it2 = next(it1);

if (it1->second > it2->second) swap(it1, it2);

cur = i - it1->second - 1;

idx.erase(it1);

}

idx[f] = i;

ans = max(++cur, ans);

}

return ans;

}

};

花花酱 LeetCode 901. Online Stock Span

By zxi on September 14, 2018

Problem

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Example 1:

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.

Note:

Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
There will be at most 10000 calls to StockSpanner.next per test case.
There will be at most 150000 calls to StockSpanner.next across all test cases.
The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

Solution 1: Brute Force (TLE)

Time complexity: O(n) per next call

Space complexity: O(n)

Solution 2: DP

dp[i] := span of prices[i]

j = i – 1
while j >= 0 and prices[i] >= prices[j]: j -= dp[j]
dp[i] = i – j

C++

// Author: Huahua, 144 ms

class StockSpanner {

public:

StockSpanner() {}

int next(int price) {

if (prices_.empty() || price < prices_.back()) {

dp_.push_back(1);

} else {

int j = prices_.size() - 1;

while (j >= 0 && price >= prices_[j]) {

j -= dp_[j];

}

dp_.push_back(prices_.size() - j);

}

prices_.push_back(price);

return dp_.back();

}

private:

vector<int> dp_;

vector<int> prices_;

};

Solution 3: Monotonic Stack

Maintain a monotonic stack whose element are pairs of <price, span>, sorted by price from high to low.

When a new price comes in

If it’s less than top price, add a new pair (price, 1) to the stack, return 1
If it’s greater than top element, collapse the stack and accumulate the span until the top price is higher than the new price. return the total span

e.g. prices: 10, 6, 5, 4, 3, 7

after 3, the stack looks [(10,1), (6,1), (5,1), (4,1), (3, 1)],

when 7 arrives, [(10,1), ~~(6,1), (5,1), (4,1), (3, 1),~~ (7, 4 + 1)] = [(10, 1), (7, 5)]

Time complexity: O(1) amortized, each element will be pushed on to stack once, and pop at most once.

Space complexity: O(n), in the worst case, the prices is in descending order.

C++

// Author: Huahua

class StockSpanner {

public:

StockSpanner() {}

int next(int price) {

int span = 1;

while (!s_.empty() && price >= s_.top().first) {

span += s_.top().second;

s_.pop();

}

s_.emplace(price, span);

return span;

}

private:

stack<pair<int, int>> s_; // {price, span}, ordered by price DESC.

};

Java

// Author: Huahua

class StockSpanner {

private Stack<Integer> prices;

private Stack<Integer> spans;

public StockSpanner() {

prices = new Stack<>();

spans = new Stack<>();

}

public int next(int price) {

int span = 1;

while (!prices.empty() && price >= prices.peek()) {

span += spans.pop();

prices.pop();

}

prices.push(price);

spans.push(span);

return span;

}

Python3

# Author: Huahua

class StockSpanner:

def __init__(self):

self.s = list()

def next(self, price):

span = 1

while self.s and price >= self.s[-1][0]:

span += self.s[-1][1]

self.s.pop()

self.s.append((price, span))

return span

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the binary tree.

Solution 1: Recursion

Time complexity: O(n)

Space complexity: O(h)

For a given root, recursively call LCA(root.left, p, q) and LCA(root.right, p, q)

if both returns a valid node which means p, q are in different subtrees, then root will be their LCA.

if only one valid node returns, which means p, q are in the same subtree, return that valid node as their LCA.

C++

// Author: Huahua

class Solution {

public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (!root || root == p || root == q) return root;

TreeNode* l = lowestCommonAncestor(root->left, p, q);

TreeNode* r = lowestCommonAncestor(root->right, p, q);

if (l && r) return root;

return l ? l : r;

}

};

Java

// Author: Huahua

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || root == p || root == q) return root;

TreeNode l = lowestCommonAncestor(root.left, p, q);

TreeNode r = lowestCommonAncestor(root.right, p, q);

if (l == null || r == null) return l == null ? r : l;

return root;

}

Python3

# Author: Huahua

class Solution:

def lowestCommonAncestor(self, root, p, q):

if any((not root, root == p, root == q)): return root

l = self.lowestCommonAncestor(root.left, p, q)

r = self.lowestCommonAncestor(root.right, p, q)

if not l or not r: return l if l else r

return root

花花酱 LeetCode 907. Sum of Subarray Minimums

Problem

Idea

Solution 1: Brute Force

C++

Java

Python3 (TLE)

Solution2 : Monotonic Stack

C++

Java

Python3

Python3 V2

花花酱 LeetCode 905. Sort Array By Parity

Problem

Solution 1: Split Odd/Even

C++

Solution 2: Stable sort by key % 2

C++

花花酱 LeetCode 904. Fruit Into Baskets

Problem

Solution: Hashtable + Sliding window

C++

花花酱 LeetCode 901. Online Stock Span

Problem

Solution 1: Brute Force (TLE)

Solution 2: DP

C++

Solution 3: Monotonic Stack

C++

Java

Python3

Related Problems

花花酱 LeetCode 236. Lowest Common Ancestor of a Binary Tree

Problem

Solution 1: Recursion

C++

Java

Python3

Related Problems:

Huahua's Tech Road

花花酱 LeetCode 907. Sum of Subarray Minimums

Problem

Idea

Solution 1: Brute Force

C++

Java

Python3 (TLE)

Solution2 : Monotonic Stack

C++

Java

Python3

Python3 V2

花花酱 LeetCode 905. Sort Array By Parity

Problem

Solution 1: Split Odd/Even

C++

Solution 2: Stable sort by key % 2

C++

花花酱 LeetCode 904. Fruit Into Baskets

Problem

Solution: Hashtable + Sliding window

C++

花花酱 LeetCode 901. Online Stock Span

Problem

Solution 1: Brute Force (TLE)

Solution 2: DP

C++

Solution 3: Monotonic Stack

C++

Java

Python3

Related Problems

花花酱 LeetCode 236. Lowest Common Ancestor of a Binary Tree

Problem

Solution 1: Recursion

C++

Java

Python3

Related Problems: