monotonic stack – My Programming Notes

Tag Archives: monotonic stack

C# || Daily Temperatures – How To Find The Number Of Days Until Warmer Temperature Using C#

March 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the number of days until warmer temperature using C#.

1. Daily Temperatures – Problem Statement

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the i^th day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Example 2:

Input: temperatures = [30,40,50,60] Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90] Output: [1,1,0]

2. Daily Temperatures – Solution

The following is a solution which demonstrates how to find the number of days until warmer temperature.

This solution uses the monotonic stack approach.





		
		
			2. Daily Temperatures - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find number of days until warmer temperature
// ============================================================================
public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        // Stack used to save the array index of each item
        var stack = new Stack<int>();
        var result = new int[temperatures.Length];

        // Go through items in the array
        for (int currentIndex = 0; currentIndex < temperatures.Length; ++currentIndex) {
            // Compare the item at the top of the stack to the current array item.
            // If the item at the top of stack is less than current array item,
            // save the distance between the array indexes in the result array.
            while (stack.Count > 0 && temperatures[stack.Peek()] < temperatures[currentIndex]) {
                // Get the distance between the two array indexes
                var previousIndex = stack.Pop();
                result[previousIndex] = currentIndex - previousIndex;
            }
            // Save the array index for this item to the stack
            stack.Push(currentIndex);
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					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
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Mar 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find number of days until warmer temperature
// ============================================================================
public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        // Stack used to save the array index of each item
        var stack = new Stack<int>();
        var result = new int[temperatures.Length];
 
        // Go through items in the array
        for (int currentIndex = 0; currentIndex < temperatures.Length; ++currentIndex) {
            // Compare the item at the top of the stack to the current array item.
            // If the item at the top of stack is less than current array item,
            // save the distance between the array indexes in the result array.
            while (stack.Count > 0 && temperatures[stack.Peek()] < temperatures[currentIndex]) {
                // Get the distance between the two array indexes
                var previousIndex = stack.Pop();
                result[previousIndex] = currentIndex - previousIndex;
            }
            // Save the array index for this item to the stack
            stack.Push(currentIndex);
        }
        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:

[1,1,4,2,1,1,0,0] [1,1,1,0] [1,1,0]

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

November 30, 2021 admin No comments

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.





		
		
			2. Maximal Rectangle - Solution
			
C#
			
			// ============================================================================
//    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/
			
				
					
				
					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
34
35
36
37
38
				
						// ============================================================================
//    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#

November 12, 2021 admin No comments

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.





		
		
			2. Stock Spanner - Solution
			
C#
			
			// ============================================================================
//    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/
			
				
					
				
					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
				
						// ============================================================================
//    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#

October 15, 2021 admin No comments

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.





		
		
			2. Circular Next Greater - Solution
			
C#
			
			// ============================================================================
//    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/
			
				
					
				
					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
34
35
36
37
38
39
40
41
42
43
				
						// ============================================================================
//    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#

October 14, 2021 admin No comments

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





		
		
			2. Next Greater - Solution
			
C#
			
			// ============================================================================
//    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/
			
				
					
				
					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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
				
						// ============================================================================
//    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.

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]

Tag Archives: monotonic stack

C# || Daily Temperatures – How To Find The Number Of Days Until Warmer Temperature Using C#

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

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

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

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

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories