Maximal Range That Each Element Is Maximum in It

class Solution {
public:
    vector<int> findMaxRangeLengths(vector<int>& elements) {
        int length = elements.size();
        vector<int> leftBoundary(length), rightBoundary(length);
        stack<int> indexStack;

        // Determine left limit for each position
        for (int i = 0; i < length; ++i) {
            while (!indexStack.empty() && elements[indexStack.top()] < elements[i]) {
                indexStack.pop();
            }
            leftBoundary[i] = indexStack.empty() ? -1 : indexStack.top();
            indexStack.push(i);
        }

        // Clear stack to use again
        while (!indexStack.empty()) indexStack.pop();

        // Determine right limit for each position
        for (int i = length - 1; i >= 0; --i) {
            while (!indexStack.empty() && elements[indexStack.top()] < elements[i]) {
                indexStack.pop();
            }
            rightBoundary[i] = indexStack.empty() ? length : indexStack.top();
            indexStack.push(i);
        }

        // Compute maximum range length per element
        vector<int> maximumRange(length);
        for (int i = 0; i < length; ++i) {
            maximumRange[i] = rightBoundary[i] - leftBoundary[i] - 1;
        }

        return maximumRange;
    }
};

For solving the problem of finding the maximal range in which each element of an array is the maximum, the given C++ solution involves using an efficient approach with the help of stacks to determine boundary limits for each element.

• Initialization and Setup: The function starts by initializing necessary vectors for storing the left and right boundaries (leftBoundary and rightBoundary) for limits where each element can be maximum. A stack (indexStack) is used to help determine these boundaries quickly.

• Computing Left Limits:

  • Iterate through the array.
  • Utilize the stack to keep track of indices. For each element at index i, pop elements from the stack while they are less than the current element, ensuring that the stack only contains elements that might be the next greater elements for the upcoming indices.
  • Set the left boundary for each element. If the stack is empty, set to -1 (indicating no smaller elements to the left); otherwise, set it to the top of the stack.

• Reset the stack to reuse for determining the right boundaries.

• Computing Right Limits:

  • Process the elements in reverse order.
  • Similar to left limits, for each element at index i, pop elements from the stack that are smaller.
  • Assign the right boundary for each element. If the stack is empty, set it to the size of the array (indicating no smaller elements to the right); otherwise, set it to the top of the stack.

• Calculate Maximum Ranges:

  • For each element in the array, calculate the range using its right and left boundaries subtracting one (to account for zero-based indexing).

• Return Results: Finally, the function returns a vector containing the maximal range lengths where each array element is the maximum.

This solution is efficient, as it processes each element a constant number of times with the help of the stack, making it O(n) in time complexity. Such an approach is significantly faster and more scalable compared to a naive solution that would have significantly higher time complexity.

class Solution {

    public int[] findMaxRange(int[] array) {
        int length = array.length;
        int[] leftBound = new int[length];
        int[] rightBound = new int[length];
        Stack<Integer> stack = new Stack<>();

        // Determine left boundaries using stack
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && array[stack.peek()] < array[i]) {
                stack.pop();
            }
            leftBound[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        // Reset stack for the next phase
        stack.clear();

        // Determine right boundaries using stack
        for (int i = length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && array[stack.peek()] < array[i]) {
                stack.pop();
            }
            rightBound[i] = stack.isEmpty() ? length : stack.peek();
            stack.push(i);
        }

        // Compute the maximum ranges for each position
        int[] ranges = new int[length];
        for (int i = 0; i < length; i++) {
            ranges[i] = rightBound[i] - leftBound[i] - 1;
        }

        return ranges;
    }
}

This article explains a Java solution to find the maximal range in which each element of a given array is the maximum.

• Start by initializing two arrays, leftBound and rightBound, to store the left and right boundaries within which each element remains the maximum. Initialize a Stack to help in boundary determination.
• Use a for-loop to populate the leftBound array. Traverse the elements from left to right:
  1. Use the stack to maintain indices of elements. For each element, pop from the stack until you find an element greater than the current one, implying the start of a new potential max range.
  2. If the stack is empty, set the left boundary to -1 (indicating the start of the array). Otherwise, the left boundary is the index at the top of the stack.
  3. Push the current index onto the stack.
• Clear the stack to repurpose it for determining the rightBound.
• Use another for-loop to populate the rightBound array, iterating from right to left:
  1. Similar to the left boundary logic, pop from the stack until you find an element greater than the current one.
  2. If the stack is empty, set the right boundary to the array length (indicating the end of the array). Otherwise, the right boundary is the index at the top of the stack.
  3. Push the current index onto the stack.
• After determining left and right bounds for each array element, compute the maximum ranges.
  1. Use a for-loop to subtract the left boundary index from the right boundary index and subtract one to compute the range. Store this result in the ranges array.
• Return the ranges array containing the maximal ranges for each array position where the element can be the maximum.

This implementation efficiently determines the boundaries where each array element is the maximum using a stack, and it performs calculations with a time complexity influenced by the traversal and stack operations, making it suitable for large inputs.

class Solution:
    def maxSpanLength(self, elements):
        size = len(elements)
        min_left = [0] * size
        max_right = [0] * size
        temp_stack = []

        # Calculate minimum left
        for i in range(size):
            while temp_stack and elements[temp_stack[-1]] < elements[i]:
                temp_stack.pop()
            min_left[i] = -1 if not temp_stack else temp_stack[-1]
            temp_stack.append(i)

        # Reset stack for next use
        temp_stack = []

        # Calculate maximum right
        for i in range(size - 1, -1, -1):
            while temp_stack and elements[temp_stack[-1]] < elements[i]:
                temp_stack.pop()
            max_right[i] = size if not temp_stack else temp_stack[-1]
            temp_stack.append(i)

        # Calculate maximal span width for each position
        result = [0] * size
        for i in range(size):
            result[i] = max_right[i] - min_left[i] - 1

        return result

This Python code defines a method to calculate the maximal span length that each element of a given list is the maximum within that span. Implement this solution with a clear approach:

1. Initialize Arrays and Stack
   Start by defining arrays min_left and max_right to store the bounds of the spans, and a temp_stack for processing the elements.

2. Calculate Minimum Left Indexes
   Iterate through the list, and for each element, pop from the stack until the current element is larger than the element at the top of the stack. Update min_left for the current index to keep track of how far left this condition holds.

3. Reset the Stack
   Clear or reset temp_stack to reuse it for calculating the maximum right indexes.

4. Calculate Maximum Right Indexes
   Iterate through the list backwards. Similar to the previous loop, modify the stack and update max_right for each element.

5. Calculate Maximal Span Width
   Compute the range (max_right[i] - min_left[i] - 1) for each element indicating the maximum span where it is the highest.

6. Return the Result
   Finally, return the array of calculated span lengths for each element in the original list.

This structured procedure ensures efficient evaluation of the span for each element using stack operations and index manipulations.