Maximal Range That Each Element Is Maximum in It

Medium

Asked by:

17 views

Topics:

ArraysStacks

You are given a 0-indexed array nums of length n.

For each index i from 0 to n - 1, find the largest range [left_i, right_i] such that the following conditions hold:

nums[i] is the maximum element in the subarray nums[left_i...right_i].
left_i <= i <= right_i.

Return an array answer of length n where answer[i] = right_i - left_i + 1.

Example 1:

Input: nums = [1,3,2,1,2]
Output: [1,3,1,1,1]
Explanation:
For i = 0, the largest range that satisfies the condition is [0, 0], so answer[0] = 0 - 0 + 1 = 1.
For i = 1, the largest range that satisfies the condition is [0, 2], so answer[1] = 2 - 0 + 1 = 3.
For i = 2, the largest range that satisfies the condition is [2, 2], so answer[2] = 2 - 2 + 1 = 1.
For i = 3, the largest range that satisfies the condition is [3, 3], so answer[3] = 3 - 3 + 1 = 1.
For i = 4, the largest range that satisfies the condition is [4, 4], so answer[4] = 4 - 4 + 1 = 1.

Example 2:

Input: nums = [1,5,4,3,5]
Output: [1,4,2,1,3]
Explanation:
For i = 0, the largest range that satisfies the condition is [0, 0], so answer[0] = 0 - 0 + 1 = 1.
For i = 1, the largest range that satisfies the condition is [0, 3], so answer[1] = 3 - 0 + 1 = 4.
For i = 2, the largest range that satisfies the condition is [2, 3], so answer[2] = 3 - 2 + 1 = 2.
For i = 3, the largest range that satisfies the condition is [3, 3], so answer[3] = 3 - 3 + 1 = 1.
For i = 4, the largest range that satisfies the condition is [3, 5], so answer[4] = 5 - 3 + 1 = 3.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values (range) of the numbers in the input array? Can they be negative, zero, or floating-point numbers?
If the input array is empty or null, what should be returned? Should I throw an exception or return a specific value like null or an empty array?
If there are multiple elements with the same maximum value, how should the maximal ranges for each of them be handled? Should I return all such ranges, or just one?
What should the format of the output be? Should it be a list of tuples representing the start and end indices of each maximal range?
Are there any constraints on the input size (the length of the array)? This will help me understand the scale of the problem.

Brute Force Solution

Approach

The brute force approach for finding the maximal range where each number is the biggest involves checking all possible ranges for each number in a collection. We test every range to see if the current number is truly the largest within that specific range. We then keep track of the longest range we've found where the number is the biggest.

Here's how the algorithm would work step-by-step:

For each number in the collection, consider it as the potential maximum for some range.
Start with a very small range: just the number itself.
Expand the range to the left and to the right, one number at a time.
For each expanded range, check if the current number is actually the biggest number within that entire range.
If it is, remember the size of this range.
If at any point another number in the range is bigger than our chosen number, stop expanding that range in that direction.
After exploring all possible ranges for that number, compare the largest range size we found to the largest we've seen so far from other numbers.
Update the 'largest range' if the current number's range is bigger.
Repeat this process for every number in the collection.
The final 'largest range' we have is the answer.

Code Implementation

def find_maximal_range(collection):
    maximal_range_size = 0

    for current_index in range(len(collection)):
        # Consider each element as the maximum for a potential range
        current_range_size = 0

        left_index = current_index
        right_index = current_index

        while left_index >= 0 and right_index < len(collection):
            is_maximum = True
            for index in range(left_index, right_index + 1):
                # Verify that the current element is the maximum in the range
                if collection[index] > collection[current_index]:
                    is_maximum = False
                    break

            if is_maximum:
                current_range_size = right_index - left_index + 1
                maximal_range_size = max(maximal_range_size, current_range_size)

                # Expand range to right, then left
                right_index += 1
                if right_index >= len(collection):
                    break

                is_maximum = True
                for index in range(left_index, right_index + 1):
                    if collection[index] > collection[current_index]:
                        is_maximum = False
                        break

                if is_maximum:
                    current_range_size = right_index - left_index + 1
                    maximal_range_size = max(maximal_range_size, current_range_size)

                else:
                    break

                left_index -= 1
                if left_index < 0:
                    break

                is_maximum = True
                for index in range(left_index, right_index + 1):
                    if collection[index] > collection[current_index]:
                        is_maximum = False
                        break
                if is_maximum:
                    current_range_size = right_index - left_index + 1
                    maximal_range_size = max(maximal_range_size, current_range_size)
                else:
                    break

            else:
                break

    return maximal_range_size

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it expands a range to the left and right, potentially checking almost all other elements in the array to confirm if the current element is the maximum. In the worst-case scenario, for each of the n elements, we might expand the range to include almost all other n elements. This results in approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm iterates through the input collection and expands ranges, keeping track of the largest range found so far. It primarily uses variables to store the current range size and the largest range encountered. No auxiliary data structures like lists or hash maps are created that depend on the input size N. Therefore, the space complexity is constant and independent of the input size.

Optimal Solution

Approach

The goal is to find, for each number in a list, the largest continuous section where that number is the highest. We can solve this efficiently by scanning the list from both the left and the right to determine the boundaries of each section, avoiding redundant comparisons.

Here's how the algorithm would work step-by-step:

For each number in the list, imagine extending a range from that number to the left.
Keep extending the range to the left as long as all the numbers you encounter are smaller than the original number.
Record the starting point of this left-extended range.
Now, do a similar thing to the right: for each number, imagine extending a range to the right.
Keep extending the range to the right as long as all the numbers you encounter are smaller than the original number.
Record the ending point of this right-extended range.
Combine the left and right ranges for each number to find the maximal continuous range where that number is the maximum.
This way, you find the biggest range for each number without re-checking areas multiple times.

Code Implementation

def find_maximal_range(number_list):
    number_list_length = len(number_list)
    left_ranges = [0] * number_list_length
    right_ranges = [0] * number_list_length
    
    for index in range(number_list_length):
        left_ranges[index] = index
        # Extend left range as far as possible
        while left_ranges[index] > 0 and number_list[index] >= number_list[left_ranges[index] - 1]:
            left_ranges[index] -= 1

        right_ranges[index] = index
        # Extend right range as far as possible
        while right_ranges[index] < number_list_length - 1 and number_list[index] > number_list[right_ranges[index] + 1]:
            right_ranges[index] += 1

    result = []
    # Combine left and right ranges to form the final result.
    for index in range(number_list_length):
        result.append((left_ranges[index], right_ranges[index]))

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to determine the left boundaries and once to determine the right boundaries for each element. Both these traversals are independent and perform a constant amount of work for each element. Therefore, the overall time complexity is dominated by these two linear scans, resulting in O(n).

Space Complexity

O(N) – The algorithm, as described, calculates left and right boundaries for each number in the list. This implicitly requires storing the left and right boundaries for all N numbers in the list. Therefore, we need two auxiliary arrays (or lists) of size N to hold the left and right boundaries respectively. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list or throw an IllegalArgumentException, depending on requirements.
Array with a single element	The element's maximal range is itself, so return a list containing a single-element range [index, index].
Array with all identical elements	Each element's maximal range is the entire array, from index 0 to index n-1.
Array sorted in ascending order	Each element's maximal range extends from its index to the end of the array.
Array sorted in descending order	Each element's maximal range is only itself.
Array with negative numbers	The algorithm should handle negative numbers correctly as it compares values directly without assumptions about positivity.
Array with very large numbers (potential integer overflow)	Use long or appropriate large number data types to avoid integer overflow during comparisons.
Input array is extremely large	Ensure the solution is efficient (e.g., using a stack or optimized algorithm) to avoid exceeding time or memory limits.

Null or empty input array

How to Handle:

Return an empty list or throw an IllegalArgumentException, depending on requirements.

Array with a single element

How to Handle:

The element's maximal range is itself, so return a list containing a single-element range [index, index].

Array with all identical elements

How to Handle:

Each element's maximal range is the entire array, from index 0 to index n-1.

Array sorted in ascending order

How to Handle:

Each element's maximal range extends from its index to the end of the array.

Array sorted in descending order

How to Handle:

Each element's maximal range is only itself.

Array with negative numbers

How to Handle:

The algorithm should handle negative numbers correctly as it compares values directly without assumptions about positivity.

Array with very large numbers (potential integer overflow)

How to Handle:

Use long or appropriate large number data types to avoid integer overflow during comparisons.

Input array is extremely large

How to Handle:

Ensure the solution is efficient (e.g., using a stack or optimized algorithm) to avoid exceeding time or memory limits.