Tag Archives: monotonic stack

C# || Maximal Rectangle – How To Find Largest Rectangle Area Using C#

The following is a module with functions which demonstrates how to find the largest rectangle area containing only 1’s using C#.


1. Maximal Rectangle – Problem Statement

Given a rows x cols binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example 1:

Example 1


Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:


Input: matrix = []
Output: 0

Example 3:


Input: matrix = [["0"]]
Output: 0

Example 4:


Input: matrix = [["1"]]
Output: 1

Example 5:


Input: matrix = [["0","0"]]
Output: 0


2. Maximal Rectangle – Solution

The following is a solution which demonstrates how to find the largest rectangle area containing only 1’s.

This solution uses the monotonic stack approach.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


6
0
0
1
0

C# || Online Stock Span – How To Get Daily Price Stock Quotes & Consecutive Day Span Using C#

The following is a module with functions which demonstrates how to get the daily price stock quotes & consecutive day span using C#.


1. Stock Spanner – Problem Statement

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

Implement the StockSpanner class:

  • StockSpanner() Initializes the object of the class.
  • int next(int price) Returns the span of the stock’s price given that today’s price is price.

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:
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85); // return 6


2. Stock Spanner – Solution

The following is a solution which demonstrates how to get the daily price stock quotes & consecutive day span.

This solution uses the monotonic stack approach.

The idea of this solution is to have a stack of a pair to store the current price and the maximum number of consecutive days.

For each new price, we check the top of the stack and keep a running total of each previous consecutive day span found for all stock prices that are less than or equal to today’s price.

Then, we add today’s price and the current running consecutive day total to the stack.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


[null,1,1,1,2,1,4,6]

C# || How To Find The Next Greater Element In A Circular Array Using C#

The following is a module with functions which demonstrates how to find the next greater element in a circular array using C#.


1. Circular Next Greater – Problem Statement

Given a circular integer array nums (i.e., the next element of nums[nums.length – 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Example 1:


Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number.
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:


Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]


2. Circular Next Greater – Solution

The following is a solution which demonstrates how to find the next greater element in a circular array.

This solution uses the monotonic stack approach. This solution finds the next greater element for each array value, in the first pass, and then uses a second pass to process any remaining values since the array is circular.

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


[2,-1,2]
[2,3,4,-1,4]

C# || How To Find The Next Greater Element In An Array Using C#

The following is a module with functions which demonstrates how to find the next greater element in an array using C#.


1. Next Greater – Problem Statement

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:


Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:


Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.


2. Next Greater – Solution

The following is a solution which demonstrates how to find the next greater element in an array.

This solution uses the monotonic stack approach. This solution finds the next greater element for each array value in the second array, and uses that to find the next greater element for each matching value in the first array.

To determine the next greatest element, a stack is used to keep track of the items we’ve already seen. The array index of the item is saved to the stack.

For each loop iteration, the item at the top of the stack is checked to see if it is less than the current array item being checked. If the item at the top of the stack is less than the current array item, then the current array item is saved to the result index that matches the value from the top of the stack.

Once the next greatest elements have been found from nums2, that information is used to populate the final result from the matching values found in nums1

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


[-1,3,-1]
[3,-1]