monotonic-stack

You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfill the following conditions: The value at index i must be the maximum element in the contiguous subarrays, and These contiguous subarrays must either start from or end on index i. Signature int[] countSubarrays(int[] arr) Input Array arr is a non-empty list of unique integers that range between 1 to 1,000,000,000 Size N is between 1 and 1,000,000 Output An array where each index i contains an integer denoting the maximum number of contiguous subarrays of arr[i]...

255. Verify Preorder Sequence in Binary Search Tree Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree. 1 2 3 4 5 6 7 8 9 Example 1: Input: preorder = [5,2,1,3,6] Output: true Example 2: Input: preorder = [5,2,6,1,3] Output: false Constraints: 1 <= preorder.length <= 10^4 1 <= preorder[i] <= 10^4 All the elements of preorder are unique....

654. Maximum Binary Tree You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm: Create a root node whose value is the maximum value in nums. Recursively build the left subtree on the subarray prefix to the left of the maximum value. Recursively build the right subtree on the subarray suffix to the right of the maximum value....

962. Maximum Width Ramp A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i. Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0. 1 2 3 4 5 6 7 8 9 10 11 Example 1: Input: nums = [6,0,8,2,1,5] Output: 4 Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5....

581. Shortest Unsorted Continuous Subarray Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order. Return the shortest such subarray and output its length. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Example 1: Input: nums = [2,6,4,8,10,9,15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order....

907. Sum of Subarray Minimums Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7. 1 2 3 4 5 6 7 8 9 10 11 12 13 Example 1: Input: arr = [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]....

901. Online Stock Span Design an algorithm that 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 backward) for which the stock price 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]....

1762. Buildings With an Ocean View There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line. The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height....

84. Largest Rectangle in Histogram Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram. 1 2 3 4 5 6 Example 1: Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units....