Posts tagged as “stack”

花花酱 LeetCode 962. Maximum Width Ramp

By zxi on December 25, 2018

Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j]. The width of such a ramp is j - i.

Find the maximum width of a ramp in A. If one doesn’t exist, return 0.

Example 1:

Input: [6,0,8,2,1,5] 
Output: 4 
Explanation:  The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,8,1,0,1,9,4,0,4,1] 
Output: 7 
Explanation:  The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Solution: Stack

Using a stack to store start candidates’ (decreasing order) index
Scan from right to left, compare the current number with the one on the top of the stack, pop if greater.

e.g.
A = [6,0,8,2,1,5]
stack = [0, 1] => [6, 0]
cur: A[5] = 5, stack.top = A[1] = 0, ramp = 5, stack.pop()
cur: A[4] = 1, stack.top = A[0] = 6
cur: A[3] = 2, stack.top = A[0] = 6
cur: A[2] = 8, stack.top = A[0] = 6, ramp = 2, stack.pop()
stack.isEmpty() => END

C++

// Author: Huahua, running time: 44 ms

class Solution {

public:

int maxWidthRamp(vector<int>& A) {

stack<int> s;

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

if (s.empty() || A[i] < A[s.top()])

s.push(i);

int ans = 0;

for (int i = A.size() - 1; i >= 0; --i)

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

ans = max(ans, i - s.top());

s.pop();

}

return ans;

}

};

Python3

# Author: Huahua, running time: 92 ms

class Solution:

def maxWidthRamp(self, A):

s = []

for i in range(len(A)):

if not s or A[i] < A[s[-1]]: s.append(i)

ans = 0

for i in range(len(A) - 1, -1, -1):

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

ans = max(ans, i - s.pop())

return ans

花花酱 LeetCode 946. Validate Stack Sequences

By zxi on November 29, 2018

Problem

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Note:

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed is a permutation of popped.
pushed and popped have distinct values.

Solution: Simulation

Simulate the push/pop operation.

Push element from |pushed sequence| onto stack s one by one and pop when top of the stack s is equal the current element in the |popped sequence|.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 8 ms

class Solution {

public:

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

stack<int> s;

auto it = begin(popped);

for (int e : pushed) {

s.push(e);

while (!s.empty() && s.top() == *it) {

s.pop();

++it;

}

return it == end(popped);

}

};

Python3

# Author: Huahua, Running time: 40 ms

class Solution:

def validateStackSequences(self, pushed, popped):

s = []

i = 0

for e in pushed:

s.append(e)

while s and s[-1] == popped[i]:

s.pop()

i += 1

return i == len(popped)

花花酱 LeetCode 32. Longest Valid Parentheses

By zxi on October 3, 2018

Problem

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

Solution: Stack

Use a stack to track the index of all unmatched open parentheses.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestValidParentheses(string s) {

stack<int> q;

int start = 0;

int ans = 0;

for (int i = 0;i < s.length(); i++) {

if(s[i] == '(') {

q.push(i);

} else {

if (q.empty()) {

start = i + 1;

} else {

int index = q.top(); q.pop();

ans = max(ans, q.empty() ? i - start + 1 : i - q.top());

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def longestValidParentheses(self, s):

q = []

start, ans = 0, 0

for i in range(len(s)):

if s[i] == '(':

q.append(i)

continue

if not q:

start = i + 1

else:

q.pop()

ans = max(ans, i - q[-1] if q else i - start + 1)

return ans

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution: Stack

Using a stack to track the existing open parentheses, if the current one is a close parenthesis but does not match the top of the stack, return false, otherwise pop the stack. Check whether the stack is empty in the end.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isValid(string s) {

map<char, char> p{{')', '('}, {']', '['}, {'}', '{'}};

stack<char> st;

for (char c : s) {

if (!p.count(c)) {

st.push(c);

} else {

if (st.empty() || p[c] != st.top()) return false;

st.pop();

}

return st.empty();

}

};

Python3

# Author: Huahua

class Solution:

def isValid(self, s):

p = {')' : '(', ']': '[', '}' : '{'}

stack = []

for c in s:

if c not in p:

stack.append(c)

else:

if not stack or stack[-1] != p[c]: return False

stack.pop()

return not stack

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

Posts tagged as “stack”

花花酱 LeetCode 962. Maximum Width Ramp

Solution: Stack

C++

Python3

花花酱 LeetCode 946. Validate Stack Sequences

Problem

Solution: Simulation

C++

Python3

花花酱 LeetCode 32. Longest Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems

花花酱 LeetCode 20. Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems

花花酱 LeetCode 907. Sum of Subarray Minimums

Problem

Idea

Solution 1: Brute Force

C++

Java

Python3 (TLE)

Solution2 : Monotonic Stack

C++

Java

Python3

Python3 V2