[LeetCode] 739. Daily Temperatures

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

Use monotonic stack to keep a decreasing sequence.

class Solution {
    fun dailyTemperatures(temperatures: IntArray): IntArray {
        val stack = Stack<int>()
        val result = IntArray(temperatures.size) { 0 }
        
        for (i in 0 until temperatures.size) {
            // pop all the days which temperature is lower than current day
            while (!stack.empty() && temperatures[stack.peek()] < temperatures[i]) {
                val last = stack.pop()
                result[last] = i - last 
            }
            
            stack.push(i)
        }
        
        return result
    }
}

[LeetCode] 1762. Buildings With an Ocean View

 Problem : https://leetcode.com/problems/buildings-with-an-ocean-view/

Maintain a decreasing monotonic stack.

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        stack = []
        
        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] <= h:
                stack.pop()
            
            stack.append(i)
        
        return stack

[LeetCode] 1019. Next Greater Node in Linked List

 Problem : https://leetcode.com/problems/next-greater-node-in-linked-list/

Use postorder traversal and maintain a decreasing monotonic stack.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        
        def postorder(node):
            if node.next:
                stack = postorder(node.next)
                while stack and stack[-1] <= node.val:
                    stack.pop()
                
                result.append(stack[-1] if stack else 0)                
                stack.append(node.val)
                
                return stack
            else:
                result.append(0)
                return [node.val]
        
        postorder(head)
        return result[::-1]

Or maintain a increasing monotonic stack which also saves the position of each smaller value.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        stack = []
        
        while head:
            while stack and stack[-1][1] < head.val:
                result[stack[-1][0]] = head.val
                stack.pop()
            
            stack.append([len(result), head.val])
            result.append(0)
            
            head = head.next
        
        return result

[LeetCode] 321. Create Maximum Number

 Problem : https://leetcode.com/problems/create-maximum-number/

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        
        def monotoneDecreasingSequence(nums, size):
            if size <= 0: return []
            
            dropCount = len(nums) - size
            
            result = []
            
            for n in nums:
                while result and result[-1] < n and dropCount > 0:
                    result.pop()
                    dropCount -= 1
                    
                result.append(n)
            
            return result[:size]
    
    
        def merge(n1, n2):
            i = j = 0
            result = []
            while i < len(n1) or j < len(n2):
                if i < len(n1) and j < len(n2):
                    # important! compare the rest numbers in lexical 
                    if n1[i:] > n2[j:]:
                        result.append(n1[i])
                        i += 1
                    else:
                        result.append(n2[j])
                        j += 1
                elif i < len(n1):
                    result.append(n1[i])
                    i += 1
                else:
                    result.append(n2[j])
                    j += 1
            
            return result
        
        result = []
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) +1):
            mds1 = monotoneDecreasingSequence(nums1, i)
            mds2 = monotoneDecreasingSequence(nums2, k - i)
            merged = merge(mds1, mds2)
            
            result = max(result, merged)
        
        return result

[LeetCode] 221 Maximal Square

 Problem : https://leetcode.com/problems/maximal-square/

This problem is similar to 84. Largest Rectangle in Histogram .

Base on the same idea, we can find the largest square ends on each row.

Time complexity = O ( M * ( N + N ) ),  M = row of the matrix, N = column of the matrix.

class Solution {
    public int maximalSquare(char[][] matrix) {
        int ROW = matrix.length;
        int COLUMN = matrix[0].length;
        
        // rows[i] = the accumulated height of each column base on ith row
        int[][] rows = new int[ROW][COLUMN];
        int result = 0;
        
        for (int y = 0; y < ROW; y++) {
            for (int x = 0; x < COLUMN; x++) {
                if (matrix[y][x] == '1') {
                    rows[y][x] = 1;
                } else {
                    continue;
                }
                
                // increase the height of column x on row y
                if (y > 0 && matrix[y-1][x] == '1') {
                    rows[y][x] += rows[y-1][x];
                }
            }
            
            // find the largest square base on y row.
            result = Math.max(result, squareBaseOnRow(rows[y]));
        }
        
        return result;
    }
    
    /**
    * find the largest square which bottom line is on current row
    */
    int squareBaseOnRow(int[] row) {
        int N = row.length;
        int result = 0;
        
        Stack<Integer> stack = new Stack();
        
        for (int i = 0; i <= N; i++) {
            // add '0' height column in the end to clean the stack
            int currentHeight = i < N ? row[i] : 0;
            
            while (!stack.isEmpty() && row[stack.peek()] > currentHeight) {
                // the highest column so far
                int height = row[stack.pop()];

                // important!  
                // if stack is empty, there is no shorter column in front of it,
                // then the left boundry = 0.
                // otherwise, the left boundry = stack.peek() + 1

                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                int right = i;

                // because it needs a square ...
                int width = Math.min(height, right - left);
                result = Math.max(result, width * width);
            }
            
            stack.push(i);    
        }
        
        return result;
    }
}

Edited on 12/16/2021. Replaced with the monotonic stack based solution.

[LeetCode] 42. Trapping Rain Water

Problem : https://leetcode.com/problems/trapping-rain-water/

It is intuitive that if one position can contain water, it must be on the lower level of both left and right side.

So we may iterate from left to right to find the maximum height of each bar from left.

Then iterate from right to left to find the maximum height of each bar from right.

The volume of each bar  = Min( maximum_height_from left,  maximum_height_from_right ) - bar_height.

Time Complexity = O ( N + N + N )

class Solution:
    def trap(self, height: List[int]) -> int:
        N = len(height)
        if N < 2: return 0
        
        # left[i] = maximum height from left of position i
        left = [0] * N
        mx = 0
        for i in range(N):
            left[i] = mx
            mx = max(mx, height[i])
        
        # right[i] = maximum height from right of position i
        right = [0] * N
        mx = 0
        for i in reversed(range(N)):
            right[i] = mx
            mx = max(mx, height[i])
        
        result = 0
        for i in range(N):
            # maximum water can be contained at ith position
            result += max(0, min(left[i], right[i]) - height[i])
        
        return result

Monotonic stack based solution. Time Complexity = O ( 2 * N ), because for every position it could be visited at most 2 times. 

class Solution:
    def trap(self, height: List[int]) -> int:
        
        # maintain a monotonic decreasing stack 
        stack = []
        result = 0
        
        for right in range(len(height)):
            
            # it can form a cavity if we find a taller right bar
            while stack and height[stack[-1]] < height[right]:
                bottom = stack.pop()
                
                # break if cannot find left bar
                if not stack:
                    break
                    
                left = stack[-1]
                
                # calculate the portion of water can be contained by this position
                bound_distance = right - left - 1
                bound_height = min(height[left], height[right]) - height[bottom]
                
                result += bound_distance * bound_height
                
            stack.append(right)
         
        return result

Edited on 06/18/2021. Update a more intuitive solution.

Edited on 08/01/2021. Add the monotonic stack based solution.