Maximal Range That Each Element Is Maximum in It

Problem Description

Welcome to the world of maximal ranges, where every element in an array is on a quest to find its rightful place as the maximum! Imagine a group of friends at a party, each trying to prove they are the tallest. The problem is simple: for each friend (or element), we want to determine how many friends they can stand next to without feeling insecure about their height.

In technical terms, given an array of integers, we need to find the length of the maximal range for each element where it is the maximum. So, if you have a friend who is 6 feet tall, they can stand next to anyone shorter than them, but if someone taller comes along, they’ll have to step aside.

In short, this problem is all about finding out how many elements can be included in the “tallest friend” club for each element in the array.

Code Solution


class Solution {
  public int[] maximumLengthOfRanges(int[] nums) {
    int[] ans = new int[nums.length];
    Deque stack = new ArrayDeque<>(); // a decreasing stack

    for (int i = 0; i <= nums.length; ++i) {
      while (!stack.isEmpty() && (i == nums.length || nums[stack.peek()] < nums[i])) {
        final int index = stack.pop();
        final int left = stack.isEmpty() ? -1 : stack.peek();
        ans[index] = i - left - 1;
      }
      stack.push(i);
    }

    return ans;
  }
}

Approach Explanation

The code uses a decreasing stack to keep track of the indices of the elements in the array. As we iterate through the array, we check if the current element is greater than the element at the index stored at the top of the stack. If it is, we pop from the stack and calculate the maximal range for the popped element. The range is determined by the difference between the current index and the index of the last element that was greater than the popped element.

This approach ensures that we efficiently find the maximal range for each element without having to check every possible combination.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n) - Each element is pushed and popped from the stack at most once.
Space Complexity	O(n) - The stack can hold up to n elements in the worst case.

Real-World Example

Imagine you are at a concert, and everyone is trying to get a better view of the stage. Each person can only see the stage if they are taller than the people in front of them. The maximal range for each person is how many people they can see in front of them before someone taller blocks their view. This is exactly what our solution calculates for each element in the array!