Maximal Range That Each Element Is Maximum in It

Maximal Range That Each Element Is Maximum in It - Problem

You are given a 0-indexed array nums of distinct integers. Let us define a 0-indexed array ans of the same length as nums in the following way:

ans[i] is the maximum length of a subarray nums[l..r], such that the maximum element in that subarray is equal to nums[i].

Return the array ans.

Note that a subarray is a contiguous part of the array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,7,3,6,5]

› Output: [1,5,1,2,1]

💡 Note: For nums[0]=1: maximum subarray is [1] with length 1. For nums[1]=7: maximum subarray is [1,7,3,6,5] with length 5. For nums[2]=3: maximum subarray is [3] with length 1. For nums[3]=6: maximum subarray is [3,6,5] with length 2. For nums[4]=5: maximum subarray is [5] with length 1.

Example 2 — Increasing Array

$ Input: nums = [1,2,3,4,5]

› Output: [1,2,3,4,5]

💡 Note: In an increasing array, each element can be maximum for all subarrays starting from index 0 up to its position. So nums[i] has maximum range of i+1.

Example 3 — Single Element

$ Input: nums = [10]

› Output: [1]

💡 Note: With only one element, it can be maximum only in the subarray containing itself, which has length 1.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
All elements in nums are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of distinct integers nums = [1,7,3,6,5]

Find Boundaries

For each element, find where larger elements block its range

Calculate Ranges

Maximum range = right_bound - left_bound - 1

Key Takeaway

🎯 Key Insight: Each element's maximum range is bounded by the nearest larger elements on both sides

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is that each element can be maximum in a subarray only until we encounter a larger element on either side. The optimal approach uses monotonic stacks to find nearest larger elements efficiently. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Monotonic Stack - Optimal Solution	O(n)	O(n)	Use monotonic stack to find nearest larger elements on both sides efficiently
Brute Force - Check All Subarrays	O(n³)	O(1)	For each element, check all possible subarrays to find the maximum range where it's the maximum

Monotonic Stack - Optimal Solution — Algorithm Steps

Find nearest larger element to the left for each element using monotonic stack
Find nearest larger element to the right for each element using monotonic stack
For each element, calculate the maximum range as right_bound - left_bound - 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Left Boundaries

Use stack to find nearest larger element on left

Right Boundaries

Use stack to find nearest larger element on right

Calculate Range

Range = right_bound - left_bound - 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int* nums, int n, int* ans) {
    // Find nearest larger element to the left
    int* leftBound = (int*)malloc(n * sizeof(int));
    int* stack = (int*)malloc(n * sizeof(int));
    int top = -1;
    
    for (int i = 0; i < n; i++) {
        leftBound[i] = -1;
    }
    
    for (int i = 0; i < n; i++) {
        while (top >= 0 && nums[stack[top]] < nums[i]) {
            top--;
        }
        if (top >= 0) {
            leftBound[i] = stack[top];
        }
        stack[++top] = i;
    }
    
    // Find nearest larger element to the right
    int* rightBound = (int*)malloc(n * sizeof(int));
    top = -1;
    
    for (int i = 0; i < n; i++) {
        rightBound[i] = n;
    }
    
    for (int i = n - 1; i >= 0; i--) {
        while (top >= 0 && nums[stack[top]] < nums[i]) {
            top--;
        }
        if (top >= 0) {
            rightBound[i] = stack[top];
        }
        stack[++top] = i;
    }
    
    // Calculate maximum range for each element
    for (int i = 0; i < n; i++) {
        ans[i] = rightBound[i] - leftBound[i] - 1;
    }
    
    free(leftBound);
    free(rightBound);
    free(stack);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || strcmp(token, "0") == 0) {
            nums[n++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int ans[1000];
    solution(nums, n, ans);
    
    // Print result
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", ans[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each element is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n elements in worst case

⚡ Linearithmic Space

29.1K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler