[Leetcode] Stack

Posted on | In , |

1047. Remove All Adjacent Duplicates In String

Leetcode: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

1
2
3
4
5
6
7
8
def removeDuplicates(self, S: str) -> str:
    stack = []
    for ch in S:
        if stack and ch == stack[-1]:
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

1209. Remove All Adjacent Duplicates in String II

Leetcode: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

Brute Force: Count and remove
Time Complexity: O(n)
Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def removeDuplicates(self, s: str, k: int) -> str:
    length = -1
    while length != len(s):
        length = len(s)
        cnt = 1
        i = 0
        while i < len(s):
            if i == 0 or s[i] != s[i - 1]:
                cnt = 1
            else:
                cnt += 1
                if cnt == k:
                    s = s[:i - k + 1] + s[i + 1:]
            i += 1
            if i >= len(s):
                break
    return s

Memoized brute force

  1. Use an array to store repeating times of each character
1
2
3
4
5
6
7
8
9
10
11
12
13
def removeDuplicates(self, s: str, k: int) -> str:
    counts = [1 for i in range(len(s))]
    i = 0
    while i < len(s):
        if i > 0 and s[i] == s[i - 1]:
            counts[i] = counts[i - 1] + 1
            if counts[i] == k:
                s = s[:i - k + 1] + s[i + 1:]
                i -= k
        else:
            counts[i] = 1
        i += 1
    return s

Stack solution

  1. Build a stack for counts
  2. If the current character is the same as the one before, increment the count on the top of the stack. Else, push 1 to the stack
  3. If the count on the top of the stack equals k, erase last k characters and pop from the stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        i = 0
        while i < len(s):
            if i == 0 or s[i] != s[i - 1]:
                stack.append(1)
            else:
                stack[-1] += 1
                if stack[-1] == k:
                    stack.pop()
                    s = s[:i - k + 1] + s[i + 1:]
                    i -= k
            i += 1
        return s

If we store both the count and the character in the stack, we do not have to modify the string. Instead, we can reconstruct the result from characters and counts in the stack.

Stack with Tree

654. Maximum Binary Tree

Leetcode: https://leetcode.com/problems/maximum-binary-tree/

1
2
3
4
5
6
7
8
9
10
11
12
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
    if not nums:
        return None
    stack = []
    for num in nums:
        node = TreeNode(num)
        while stack and stack[-1].val < num:
            node.left = stack.pop() # Run till stack[-1].val > num
        if stack and stack[-1].val > num:
            stack[-1].right = node
        stack.append(node)
    return stack[0]

255. Verify Preorder Sequence in Binary Search Tree

Leetcode: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

Note:

  1. In preorder traversal, we first traverse left all the way to the leaf, during this process, the value is in a descending order. If the current number is larger than the stack[-1], it means we reach to the right subtree
  2. Then we start popping elements from stack, the last popped out element is the parent of the current element
  3. The parent would always smaller than the right subtree.
1
2
3
4
5
6
7
8
9
10
def verifyPreorder(self, preorder):
    stack = []
    low = -float('inf')
    for cur in preorder:
        while stack and stack[-1] < cur:
            low = stack.pop()
        if cur < low:
            return False
        stack.append(cur)
    return True

Parenthesis problems

32. Longest Valid Parentheses

Leetcode: https://leetcode.com/problems/longest-valid-parentheses/

[Solution]

  • Scan the string from the beginning to end
  • Use a stack to save all the unmatched parentheses
  • If current character is ‘(‘, push its index to the stack. If current character is ‘)’ and the character at the index of the top of stack is ‘(‘, we just find a matching pair so pop from the stack. Otherwise, we push the index of ‘)’ to the stack.
  • After the scan is done, the stack will only contain the indices of characters which cannot be matched. Then let’s use the opposite side - substring between adjacent indices should be valid parentheses.
  • If the stack is empty, the whole input string is valid. Otherwise, we can scan the stack to get longest valid substring as described in step 3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def longestValidParentheses(self, s: 'str') -> 'int':
    if not s or len(s) == 0:
        return 0
    stack = []
    last = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            if len(stack) != 0:
                if s[stack[-1]] == '(':
                    stack.pop()
                else:
                    stack.append(i)
            else:
                stack.append(i)
                
    if len(stack) == 0:
        return len(s)
    
    res = 0
    a = len(s)
    while len(stack) != 0:
        b = stack.pop()
        res = max(a - b - 1, res)
        a = b
    res = max(res, a)
    
    return res

678. Valid Parenthesis String

301. Remove Invalid Parentheses

Largest area problem

84. Largest Rectangle in Histogram

Leetcode: https://leetcode.com/problems/largest-rectangle-in-histogram/

85. Maximal Rectangle

Leetcode: https://leetcode.com/problems/maximal-rectangle/

Stack Sort Problem

  • Ascending order stack:
    • Used when
      • Delete/skip k digits, find smallest
      • remove larger element before nums[i]
    • if cur < stack[-1]: stack.pop(), stack.append(cur)

739. Daily Temperatures

Leetcode: https://leetcode.com/problems/daily-temperatures/

Use a stack to store the index of elements. Use the stack to strictly store increasing temperatures.

1
2
3
4
5
6
7
8
9
def dailyTemperatures(self, T: List[int]) -> List[int]:
    res = [0] * len(T)
    stack = []
    for i in range(len(T)):
        while stack and T[stack[-1]] < T[i]:
            index = stack.pop()
            res[index] = i - index
        stack.append(i)
    return res

581. Shortest Unsorted Continuous Subarray

Leetcode: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

To find the left boundary, use a stack to keep track of all acsending sequence, once meet with a down slope, pop elements out untill the top of the stack is smaller than the element. Use the same way to find the right boundary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var findUnsortedSubarray = function(nums) {
    if (nums.length < 2) { return 0 }
    let stack = [0];
    let left = nums.length;
    let right = 0;
    for (let i = 1; i < nums.length; i++) {
        while (nums[i] < nums[stack[stack.length - 1]]) {
            left = Math.min(left, stack.pop());
        }
        stack.push(i);
    }
    stack = [nums.length - 1];
    for (let i = nums.length - 2; i >= 0; i--) {
        while (stack.length !== 0 && nums[i] > nums[stack[stack.length - 1]]) {
            right = Math.max(right, stack.pop());
        }
        stack.push(i);
    }
    return right - left > 0 ? right - left + 1: 0;
};

Note: Go forward to find the left boundary of unsorted elements, go backwards to find the right boundary of unsorted elements.

Time Complexity: O(N), Space: O(2N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findUnsortedSubarray(self, nums: List[int]) -> int:
    forward = []
    backward = []
    left, right = float('inf'), -1
    for i in range(len(nums)):
        j = len(nums) - i - 1
        while forward and forward[-1][1] > nums[i]:
            left = min(left, forward.pop()[0])
        forward.append([i, nums[i]])
        while backward and backward[-1][1] < nums[j]:
            right = max(right, backward.pop()[0])
        backward.append([j, nums[j]])
    # ! Remember the case when nums is already sorted
    if left == float('inf') and right == -1:
        return 0
    return right - left + 1

402. Remove K Digits

DP solution (TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def removeKdigits(self, num, k):
    if k == 0 or len(num) < k:
        return num
    if k == len(num):
        return "0"
    n = len(num) - k
    dp = [["0" for j in range(len(num))] for i in range(n + 1)]
    for i in range(n + 1):
        for j in range(len(num)):
            if i == 0:
                continue
            if i > j:
                dp[i][j] = num[:j + 1]
            else:
                if int(dp[i - 1][j - 1] + num[j]) > int(dp[i][j - 1]):
                    dp[i][j] = dp[i][j - 1]
                else:
                    dp[i][j] = dp[i - 1][j - 1] + num[j]
    # print(dp)
    return dp[-1][-1]

Note:

  1. Beware of the cases when k == len(num) and k == 0, and k > 0 after iteration
  2. Always keep stack in acsending order
  3. Keep removing the previous digits that’s larger than the current digit while k > 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def removeKdigits(self, num, k):
    if k >= len(num):
        return "0"
    if k == 0:
        return num
    stack = []
    for i in range(len(num)):
        cur = num[i]
        while stack and int(cur) < int(stack[-1]) and k > 0:
            stack.pop()
            k -= 1
        stack.append(cur)
    if not stack:
        return "0"
    if k > 0:
        return str(int("".join(stack[:-k])))
    return str(int("".join(stack)))

901. Online Stock Span

Leetcode: https://leetcode.com/problems/online-stock-span/

Weighted decreasing stack, the weight represents number of elements skipped.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class StockSpanner:
    def __init__(self):
        self.stack = []
        

    def next(self, price: int) -> int:
        if not self.stack:
            self.stack.append((price, 1))
            return 1
        w = 1
        while self.stack and self.stack[-1][0] <= price:
            _, weight = self.stack.pop()
            w += weight
        self.stack.append((price, w))
        return self.stack[-1][1]

316. Remove Duplicate Letters

Leetcode: https://leetcode.com/problems/remove-duplicate-letters/

Pretty Good Video: https://www.youtube.com/watch?v=SrlvMmfG8sA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def removeDuplicateLetters(self, s: str) -> str:
    used = [0] * 26
    count = [0] * 26
    stack = []
    for ch in s:
        index = ord(ch) - ord('a')
        count[index] += 1
    for ch in s:
        index = ord(ch) - ord('a')
        if used[index] == 1: # If ch is already used, we just ignore it
            count[index] -= 1
            continue
        while stack and ord(stack[-1]) - ord('a') > index and count[ord(stack[-1]) - ord('a')] > 0: # If the last used character X is after current ch in the alphabet, and after ch there's still exist X (count > 0), we discard X from the stack and set used to false 
            use = stack.pop()
            used[ord(use) - ord('a')] = 0
        used[index] = 1
        stack.append(ch)
        count[index] -= 1
    return "".join(stack)

636. Exclusive Time of Functions

Leetcode: https://leetcode.com/problems/exclusive-time-of-functions/

Note:

  • Use prev to remember the previous boundary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
    # 1
    # ["0:start:0","0:start:2","0:end:5","0:start:6","0:end:6","0:end:7"]
    stack = [int(logs[0].split(':')[0])] # [0, s, 0]
    res = [0] * n
    maxLog = 0
    prev = 0
    for i in range(1, len(logs)):
        s = logs[i]
        cur = s.split(':')
        log = int(cur[0])
        maxLog = max(maxLog, log)
        status = cur[1]
        time = int(cur[2])
        if status == "start":
            if stack:
                res[stack[-1]] += time - prev
            stack.append(log)
            prev = time
        else:
            res[stack[-1]] += time - prev + 1
            stack.pop()
            prev = time + 1
    return res[:maxLog + 1]

1776. Car Fleet II

Leetcode: https://leetcode.com/problems/car-fleet-ii/

Idea: Similar to Car Fleet I, iterate from the last car, if A can’t catch B before B catch C, then C would be the next car A catch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
    # brute force
    res = [-1 for _ in range(len(cars))]
    for i in reversed(range(len(cars) - 1)):
        j = i + 1
        Pi, Vi = cars[i]
        Pj, Vj = cars[j]
        
        if res[j] == -1:
            if Vi > Vj:
                res[i] = (Pj - Pi) / (Vi - Vj)
            else:
                res[i] = -1
        else:
            while j < len(cars) and (Vi <= Vj or (Pj - Pi) / (Vi - Vj) >= res[j] and res[j] > 0):
                # if cannot reach next car or by the time next car reach another car: find the next j after i so that: Vj < Vi and Tj >= Ti or Tj == -1
                j += 1
                if j < len(cars):
                    Pj, Vj = cars[j]
                else:
                    break
            if j < len(cars) and Vi > Vj:
                # found valid j
                res[i] = (Pj - Pi) / (Vi - Vj)
            else:
                res[i] = -1
    return res

Optimize with stack: a stack of car indices where the collision time is strict decreasing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:
    # brute force: 
    # If a can't catch b before b catch c, then a catch c
    # loop from the back
    res = [-1 for _ in range(len(cars))]
    stack = [len(cars) - 1]
    for i in reversed(range(len(cars) - 1)):
        j = i + 1
        Pi, Vi = cars[i]
        Pj, Vj = cars[j]
        
        if res[j] == -1:
            if Vi > Vj:
                res[i] = (Pj - Pi) / (Vi - Vj)
            else:
                res[i] = -1
        else:
            while stack:
                j = stack[-1]
                Pj, Vj = cars[j]
                if Vi <= Vj or (Pj - Pi) / (Vi - Vj) >= res[j] and res[j] > 0:
                    # if cannot reach next car or by the time next car reach another car: find the next j after i so that: Vj < Vi and Tj >= Ti or Tj == -1
                    # skip current car
                    stack.pop()
                else:
                    break
            if stack:
                j = stack[-1]
                Pj, Vj = cars[j]
                res[i] = (Pj - Pi) / (Vi - Vj)
                
        stack.append(i)
    return res