Compute subarray span for each element

Q: Compute subarray span for each element

This question evaluates array reasoning and competency in determining span-like influence regions under maximum-value constraints for each element, including handling circular-array extensions and scalability considerations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an integer array nums of length n.

For each index i (0 <= i < n), define ans[i] as the maximum possible length of a contiguous subarray nums[l..r] such that:

l <= i <= r (the subarray contains index i ), and
the maximum element in nums[l..r] is exactly nums[i] .

In other words, starting from position i, you can expand to the left and right as long as you do not include any element strictly greater than nums[i]. Among all such subarrays that still contain index i, ans[i] is the maximum possible length.

Return the array ans of length n.

You may assume n can be large (e.g., up to around 2 * 10^5), so you should design an efficient algorithm.

Example 1

Input:  nums = [1, 5, 4, 3, 6]
Output: ans = [1, 4, 2, 1, 5]

Explanation:
- i = 0, nums[0] = 1:
  Any subarray containing index 0 that goes past index 0 includes an element > 1, so only [1] works ⇒ ans[0] = 1.
- i = 1, nums[1] = 5:
  We can take subarray [1, 5, 4, 3]. Its max = 5 and includes index 1 ⇒ length 4.
- i = 2, nums[2] = 4:
  If we extend left to index 1, max becomes 5, which is > 4 (not allowed). Right we can go to index 3.
  So best subarray is [4, 3] ⇒ length 2.
- i = 3, nums[3] = 3:
  Any extension left/right hits a value > 3, so only [3] ⇒ length 1.
- i = 4, nums[4] = 6:
  We can take the whole array [1, 5, 4, 3, 6]; its max is 6 ⇒ length 5.

Example 2

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

Explanation:
For each i, we can expand from index 0 up to i, since the array is strictly increasing.
Thus ans[i] = i + 1.

Follow-up (circular array):

Now suppose nums is circular: index 0 comes after index n - 1. A contiguous subarray on this circle may wrap around the end of the array (e.g., [nums[3], nums[4], nums[0], nums[1]] when n = 5).

For each index i, compute the maximum possible length of a circular contiguous segment such that:

the segment contains index i , and
the maximum element on that segment is exactly nums[i] .

Return the resulting array for the circular case as well, or describe how to modify your algorithm to handle the circular version.

Compute subarray span for each element

Overview

Comments (0)