Problem Restatement

Given B[i] = the number of subarrays [l, r] containing index i where A[i] is the minimum, reconstruct the array A.

Key Insight

For each index i, define:

  • left[i]: the leftmost index such that A[i] is the minimum of A[left[i]..i]
  • right[i]: the rightmost index such that A[i] is the minimum of A[i..right[i]]

Then:

B[i] = (i - left[i] + 1) * (right[i] - i + 1)

This counts all subarrays [l, r] where left[i] <= l <= i <= r <= right[i].

The problem reduces to determining left[i], right[i], and A[i] for each i from 1 to N.

Algorithm: Monotone Stack with Difference Array

Process indices i = 1, 2, ..., N left to right, maintaining a stack of indices j whose values A[j] are non-decreasing (bottom to top). The stack represents the “active” previous elements whose right boundary still reaches the current position (right[j] >= i).

We maintain a difference array D to track range increment operations. When a chain of stack elements expires (right[j] < i), we pop them one by one but increment the difference array only for the last one popped — the element closest to the bottom of the chain that was blocking the current position. This represents a single “blocking effect ended” event for that expiration. For that last-popped j:

D[left[j]] += 1
D[right[j] + 1] -= 1

The final output is A[k] + prefix_sum(D, k) for each k = 1..N.

Exception: When A[i] == A[j] (equal-value case), after processing i, we immediately pop j without incrementing its range.

Maintaining the Stack Invariant

The stack contains indices j in increasing order where A[j] is non-decreasing. Additionally, any j on the stack whose right[j] < i has already been popped. Thus, the stack top j always satisfies right[j] >= i-1 (its range at least reached i-1, and possibly further).

Processing Index i

Let j be the current stack top after maintenance (step 1 below). We need to decide whether A[i] == A[j] or A[i] > A[j]. We can only have A[i] == A[j] or A[i] > A[j] because if A[i] < A[j], then j should have been popped (since right[j] < i).

Step 1: Pop expired entries, increment only the last one

While right[stack.top()] < i, pop elements from the stack. Keep track of the last element popped (the one closest to the bottom of the chain). After the loop, if a last-popped element was found, increment its range [left[last], right[last]] by 1 in the difference array:

D[left[last]] += 1
D[right[last] + 1] -= 1

The sentinel at index 0 (with right[0] = N) guarantees the stack is never empty, and the sentinel itself is never popped or incremented.

After this step, let j = stack top.

Step 2: Determine left[i] and whether A[i] == A[j] or A[i] > A[j]

Let j = stack top (never empty due to the sentinel at index 0). Two cases:

Case A[i] == A[j]:

  • We inherit: left[i] = left[j].
  • To verify this case is valid, check: 
    (i - left[j] + 1) * (right[j] - i + 1) == B[i]

    This computes what B[i] would be if A[i] == A[j] (same value, same range as j), using left[i] = left[j] and right[i] = right[j].

Case A[i] > A[j]:

  • Set left[i] = j + 1 (the range starts right after j since A[j] < A[i]).

Decision order: Check the A[i] == A[j] case first. If the equality (i - left[j] + 1) * (right[j] - i + 1) == B[i] holds, we take that case. Otherwise, A[i] > A[j].

Step 3: Compute right[i] and A[i]

Once left[i] is determined:

  • If A[i] == A[j]: Set right[i] = right[j], and A[i] = A[j] (same value).
    • Then pop j from the stack WITHOUT incrementing its range (exception to the normal pop behavior).
  • If A[i] > A[j]:
    • Set A[i] = A[j] + 1 (minimum value strictly greater than A[j]).
    • From B[i] = (i - left[i] + 1) * (right[i] - i + 1), we know i - left[i] + 1. Therefore: 
      right[i] - i + 1 = B[i] / (i - left[i] + 1)
right[i] = i - 1 + B[i] / (i - left[i] + 1)
    • The sentinel at index 0 with A[0] = 0 handles the base case: when only the sentinel remains, A[i] = 0 + 1 = 1 and left[i] = 0 + 1 = 1.

Step 4: Push i onto the stack

Push i with its computed left[i], right[i], A[i]. The stack invariant (non-decreasing A) is maintained.

Why A[i] = A[j] + 1 When A[i] > A[j]

We want the smallest valid A[i]. Since A[j] is the smallest value on the stack (well, A[j] is at the top and A is non-decreasing on stack, so A[j] is the largest), setting A[i] = A[j] + 1 ensures A[i] is the minimum in [j+1, right[i]]. Any smaller value would make A[i] <= A[j], contradicting A[i] > A[j]. Any larger value is valid but unnecessary.

Handling Equal Values on the Stack

When A[i] == A[j], we effectively “extend” j’s range to include i. Both indices share the same left and right boundaries. After processing i, j is popped from the stack without its range being incremented. This correctly handles the duplicate-minimum case: both i and j count subarrays in the same maximal range.

How right[i] Is Already Known

right[i] is fully determined the moment i is processed — no deferred computation:

  • Case A[i] == A[j]: right[i] = right[j], which was already determined when j was processed.
  • Case A[i] > A[j]: right[i] = i - 1 + B[i] / (i - left[i] + 1), computed directly from B[i] and the already-known left[i].

When a stack element j is popped at a later step i (because right[j] < i), its right boundary is simply read from the precomputed right[j] array. The stack maintenance in Step 1 uses this already-known right[j] to decide whether j is still “active” at position i. After Step 1, the remaining stack top j satisfies right[j] >= i, guaranteeing either A[i] == A[j] or A[i] > A[j].

Initial Conditions and Edge Cases

  • Sentinel as base case: The sentinel at index 0 (A[0] = 0, left[0] = 1, right[0] = N) is always on the stack. It naturally handles the first element and any case where all previous real elements expire — left[i] = 0 + 1 = 1, A[i] = 0 + 1 = 1.
  • right[i] never exceeds N: Since B[i] corresponds to a valid array A, the division B[i] / (i - left[i] + 1) always yields an integer, and the resulting right[i] will be at most N.
  • Difference array: D is initialized to zero. The final answer for position k is A[k] + prefix_sum(D, k).

Complexity

  • Time: O(N) — each index is pushed once and popped at most once. Difference array operations are O(1) per pop.
  • Space: O(N) — the stack, plus arrays for A, left, right, and D.

Implementation Note: Sentinel

Insert a sentinel element at index 0 with right[0] = N, A[0] = 0, left[0] = 1 before the loop. Since right[0] = N >= i for all i, the sentinel never gets popped — the stack is never empty, so the “stack empty” branch disappears. The equal-value check is only performed when j > 0 (j is a real element, not the sentinel). When the sentinel is the stack top, we always take A[i] > A[j], giving left[i] = 0 + 1 = 1 and A[i] = 0 + 1 = 1 as the base case.

Pseudocode

# Initialize difference array
D[1..N+1] = 0

# Sentinel
right[0] = N
A[0] = 0
left[0] = 1
stack = [0]

for i = 1 to N:
    # Step 1: pop expired, increment only the LAST one popped
    last_popped = -1
    while right[stack.top()] < i:
        last_popped = stack.pop()
    if last_popped != -1:
        D[left[last_popped]] += 1
        D[right[last_popped] + 1] -= 1

    j = stack.top()

    # Step 2: check A[i] == A[j] first
    candidate_B = (i - left[j] + 1) * (right[j] - i + 1)
    if j > 0 && candidate_B == B[i]:
        # Case: A[i] == A[j]
        left[i] = left[j]
        right[i] = right[j]
        A[i] = A[j]
        # Pop j without incrementing its range
        stack.pop()
    else:
        # Case: A[i] > A[j]
        left[i] = j + 1
        A[i] = A[j] + 1
        right[i] = i - 1 + B[i] // (i - left[i] + 1)

    stack.push(i)

# Compute final answer using prefix sum of difference array
prefix = 0
for k = 1 to N:
    prefix += D[k]
    output A[k] + prefix

Correctness Argument

  1. Stack invariant: The stack always contains indices with non-decreasing A values. When we push i, A[i] >= A[j] (top), so the invariant holds. Popping maintains the invariant since we remove from the top.

  2. B[i] decomposition: For any index i, the number of subarrays where A[i] is the minimum equals (i - left[i] + 1) * (right[i] - i + 1), where left[i] and right[i] are the maximal range where A[i] is the minimum. This is because any subarray [l, r] with left[i] <= l <= i <= r <= right[i] has minimum A[i].

  3. Disambiguation of equal vs greater: When A[i] == A[j], index i shares j’s full range: left[i] = left[j], right[i] = right[j]. When A[i] > A[j], j blocks the left extension: left[i] = j + 1. These two cases yield different left[i] values, hence different B[i] values. By checking which case produces B[i], we uniquely determine the relationship.

  4. Minimal A[i]: Setting A[i] = A[j] + 1 when A[i] > A[j] gives the smallest valid value. Larger values are also valid but produce the same left/right ranges and hence the same B — so the minimal value is a safe choice.

  5. Difference array increments: When a chain of elements expires at step i, only the last one popped (the one that was blocking the current position) gets its range incremented. This correctly models a single “blocking effect ended” event per expiration — the innermost blocker in the chain releases its range. The difference array efficiently applies O(1) per expiration event, with the final prefix sum computing the adjusted values.

  6. Equal-value pop without increment: When A[i] == A[j], j is immediately popped without incrementing because i inherits j’s full range and value — the blocking chain continues unbroken through i, so no increment is needed.