## 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:**

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.

```
```
1234567891011121314151617181920212223242526272829303132333435363738
// ============================================================================// Author: Kenneth Perkins// Date: Nov 30, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the largest rectangle area// ============================================================================public class Solution { public int MaximalRectangle(char[][] matrix) { if (matrix.Length == 0) { return 0; } var result = 0; var histogram = new int[matrix[0].Length + 1]; for (int row = 0; row < matrix.Length; ++row) { var stack = new Stack<int>(); for (int col = 0; col <= matrix[row].Length; ++col) { // Set value if (col < matrix[row].Length) { if (matrix[row][col] == '1') { histogram[col] += 1; } else { histogram[col] = 0; } } // Compute area while (stack.Count > 0 && histogram[stack.Peek()] >= histogram[col]) { var area = histogram[stack.Pop()] * (stack.Count == 0 ? col : (col - stack.Peek() - 1)); result = Math.Max(result, area); } stack.Push(col); } } return result; }}// http://programmingnotes.org/

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

```
```
123456789101112131415161718192021222324252627282930
// ============================================================================// Author: Kenneth Perkins// Date: Nov 12, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to get the daily price stock quotes day span// ============================================================================public class StockSpanner { // Store the current price & maximum number of consecutive days Stack<KeyValuePair<int, int>> stack; public StockSpanner() { stack = new Stack<KeyValuePair<int, int>>(); } public int Next(int price) { var consecutiveDays = 1; // Compare current price with the item on the top of the stack while (stack.Count > 0 && stack.Peek().Key <= price) { // Get the previous consecutive day span and add to the current result consecutiveDays += stack.Peek().Value; stack.Pop(); } // Add the current price and consecutive day span to the stack stack.Push(new KeyValuePair<int, int>(price, consecutiveDays)); return consecutiveDays; }}// http://programmingnotes.org/

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

```
```
12345678910111213141516171819202122232425262728293031323334353637383940414243
// ============================================================================// Author: Kenneth Perkins// Date: Oct 15, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the next greater element in a // circular array// ============================================================================public class Solution { public int[] NextGreaterElements(int[] nums) { var result = GetNextGreatest(nums); return result; } public int[] GetNextGreatest(int[] nums) { var result = new int[nums.Length]; var stack = new Stack<int>(); for (int index = 0; index < nums.Length; ++index) { // Default to -1 for this index result[index] = -1; // Fill in values that have a greater element while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) { result[stack.Peek()] = nums[index]; stack.Pop(); } // Add index to stack stack.Push(index); } // Fill in any left over values since this is circular for (int index = 0; index < nums.Length && stack.Count > 0; ++index) { while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) { result[stack.Peek()] = nums[index]; stack.Pop(); } } return result; }}// http://programmingnotes.org/

**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

```
```
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
// ============================================================================// Author: Kenneth Perkins// Date: Oct 14, 2021// Taken From: http://programmingnotes.org/// File: Solution.cs// Description: Demonstrates how to find the next greater element in an array// ============================================================================public class Solution { public int[] NextGreaterElement(int[] nums1, int[] nums2) { // For each element in nums2, get the next greatest element var nums2NextGreatest = GetNextGreatest(nums2); // Create a dictionary with the next greatest of each element from nums2 var seen = new Dictionary<int, int>(); for (int index = 0; index < nums2.Length; ++index) { seen[nums2[index]] = nums2NextGreatest[index]; } // From the items in the dictionary, populate the results var result = new int[nums1.Length]; for (int index = 0; index < nums1.Length; ++index) { result[index] = seen[nums1[index]]; } return result; } public int[] GetNextGreatest(int[] nums) { // Create a stack that keeps track of the item and its index var stack = new Stack<int>(); var result = new int[nums.Length]; // Go through array and find the next greatest value for (int index = 0; index < nums.Length; ++index) { // Default the value at index to -1 result[index] = -1; // Check to see if the item at the top of the stack is less than current item while (stack.Count > 0 && nums[stack.Peek()] < nums[index]) { // Save the current item at the result index result[stack.Peek()] = nums[index]; stack.Pop(); } // Save array index to the stack stack.Push(index); } return result; }}// http://programmingnotes.org/

**QUICK NOTES**:

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

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

[-1,3,-1]

[3,-1]