Maximum Width Ramp

class Solution {
public:
    int calculateMaxWidthRamp(vector<int>& arr) {
        int length = arr.size();
        stack<int> stackIndices;

        for (int i = 0; i < length; i++) {
            if (stackIndices.empty() || arr[stackIndices.top()] > arr[i]) {
                stackIndices.push(i);
            }
        }

        int maxRampWidth = 0;

        for (int j = length - 1; j >= 0; j--) {
            while (!stackIndices.empty() &&
                   arr[stackIndices.top()] <= arr[j]) {
                maxRampWidth = max(maxRampWidth, j - stackIndices.top());
                stackIndices.pop();
            }
        }

        return maxRampWidth;
    }
};

The solution provides a method to calculate the maximum width ramp in an array using C++. The maximum width ramp is defined as the maximum distance between two indices i and j, such that i<j and arr[i] <= arr[j]. The approach utilizes a stack to efficiently track potential start points for ramps and then calculates the maximum width by comparing these start points with every other element in a reverse traversal of the array.

Here's a breakdown of how the solution works:

• Initialize a stack to store indices. These indices are potential minimum points for the ramp.
• Iterate over the array. For each element, if the stack is empty or if the element at the current index is smaller than the element at the index stored at the top of the stack, push the current index onto the stack. This way, only indices that represent a new potential minimum are stored.
• Initialize a variable to keep track of the maximum ramp width found.
• Iterate over the array again from the end to the beginning:
  • For each element, while the stack is not empty and the element at the top index of the stack is less than or equal to the current element, update the maximum ramp width if the current distance (difference between the current index and the top index of the stack) is greater than the previous maximum. Then, pop the top index from the stack.
• Return the maximum ramp width found.

This method efficiently determines the maximum width ramp in O(n) time complexity, where n is the length of the array, by leveraging the properties of the stack to keep track of the minimum elements and calculating the possible ramp widths in a single backward pass through the array.

class Solution {
    public int maximumWidthRamp(int[] array) {
        int len = array.length;
        Stack<Integer> indexStack = new Stack<>();

        // Push indices where elements are in non-decreasing order
        for (int i = 0; i < len; i++) {
            if (indexStack.isEmpty() || array[indexStack.peek()] > array[i]) {
                indexStack.push(i);
            }
        }

        int maxRampWidth = 0;

        // Evaluate from end to start for maximum width ramp
        for (int j = len - 1; j >= 0; j--) {
            while (!indexStack.isEmpty() && array[indexStack.peek()] <= array[j]) {
                maxRampWidth = Math.max(maxRampWidth, j - indexStack.peek());
                indexStack.pop();
            }
        }

        return maxRampWidth;
    }
}

In the given Java solution for the problem titled "Maximum Width Ramp," the code aims to compute the maximum width of a ramp in an integer array. Here, a ramp is defined as indices (i) and (j) where (i < j) and (array[i] \leq array[j]), and the goal is to find the maximum difference between (j) and (i) under these conditions.

• The program starts by defining a method maximumWidthRamp with an integer array parameter.
• A Stack<Integer> (indexStack) is used to keep track of indices where array elements are in non-decreasing order from the start of the array.
• Inside a loop, indices are pushed onto the stack if the stack is empty or if the current array element is smaller than the element at the index on the top of the stack.
• Another variable, maxRampWidth, is initialized to zero to store the maximum ramp width found during the algorithm's execution.
• To find the maximum ramp width, the code processes elements from the end of the array towards the start. For each element, it checks if the array element is greater than or equal to the element at the index present at the top of the stack.
• If this condition is satisfied, it calculates the potential width (the difference between the current index j and the top of indexStack), updates the maxRampWidth if this width is larger than the current maximum, and then removes the top index from the stack. This ensures that the maximum possible ramp width for every valid i index is considered.
• Finally, after examining all elements, the method returns maxRampWidth representing the largest found width of a ramp where the start and end values meet the criteria.

This algorithm effectively combines iteration with stack operations to efficiently determine the maximum width ramp in a single pass from both ends of the array, ensuring optimal performance.

class Solution:
    def maximumWidthRamp(self, array):
        array_len = len(array)
        increasing_indices = []

        for idx in range(array_len):
            if not increasing_indices or array[increasing_indices[-1]] > array[idx]:
                increasing_indices.append(idx)
        
        largest_width = 0

        for reverse_idx in range(array_len - 1, -1, -1):
            while increasing_indices and array[increasing_indices[-1]] <= array[reverse_idx]:
                largest_width = max(largest_width, reverse_idx - increasing_indices.pop())

        return largest_width

The given Python code defines a solution to find the maximum width ramp in a given array. The maximum width ramp is defined as the maximum difference between indices i and j, where i < j and array[i] <= array[j]. Here's a breakdown of the code:

1. Initialize array_len to store the length of the input array.
2. Create an empty list increasing_indices to maintain indices of the elements where each element is greater than the last recorded element in this list.
3. Loop through each index of the array:
   • If increasing_indices is empty or the last recorded value in array indexed by increasing_indices is greater than the present value at idx, append idx to increasing_indices.
4. Initialize largest_width to zero to keep track of the maximum width found.
5. Loop through the array in reverse:
   • While increasing_indices is not empty and the value at the current index from increasing_indices is less than or equal to the current array value, calculate the potential width and update largest_width if this width is larger.
6. Return largest_width as the maximum width of the ramp found.

The approach uses two main loops:

• The first loop builds a list of potential starting points for ramps by capturing increasing order indices.
• The second loop, running backward through the array, allows checking for the maximum j-i difference where the conditions are met, utilizing the increasing indices for efficient comparison.

This implementation is efficient, making use of list operations and ensuring that each index element is processed in an optimal manner to find the maximum width ramp.