Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Given an integer array, one element may be replaced with any integer. The goal is to maximize the length of a contiguous subarray whose values never decrease from left to right.

The word subarray matters: useful values cannot be gathered from scattered positions. The chosen values must occupy one continuous interval. The replacement can repair one troublesome position inside that interval, but every other adjacent pair must already be in non-decreasing order.

For example, in [1, 2, 3, 1, 2], replacing the second 1 with 3 produces a non-decreasing prefix [1, 2, 3, 3] of length four. No replacement can make all five values non-decreasing because the final 2 would still come after 3.

The key observation

Suppose index i is the element being replaced. Everything kept immediately to its left must already form a non-decreasing run ending at i - 1. Likewise, everything kept immediately to its right must already form a non-decreasing run starting at i + 1.

That suggests precomputing two pieces of information:

  • ending_at[i]: the length of the non-decreasing run that ends at i.
  • starting_at[i]: the length of the non-decreasing run that starts at i.

Both arrays follow simple recurrences. A run ending at i - 1 extends through i exactly when nums[i - 1] <= nums[i]. The starting lengths use the same idea in reverse.

Once these lengths are known, replacing index i has only three meaningful outcomes. It can extend the left run by one, extend the right run by one, or join both runs through the replacement.

Joining both sides is possible exactly when nums[i - 1] <= nums[i + 1]. In that case, the replacement can be any integer between those two neighbors, inclusive. The joined length is then:

ending_at[i - 1] + 1 + starting_at[i + 1]

If the left neighbor is greater than the right neighbor, no single value can be at least the left neighbor and at most the right neighbor simultaneously. The replacement can still join one side, but not both.

The best original run is also considered because the operation is optional. Enumerating every replacement index therefore covers all possible answers.

Why the algorithm is optimal

Take any optimal result that uses a replacement at index i. After removing the replacement position from view, the part to its left is an unchanged non-decreasing run ending at i - 1, so it cannot be longer than ending_at[i - 1]. The right part is similarly bounded by starting_at[i + 1].

If both parts are present, their boundary values must satisfy nums[i - 1] <= nums[i + 1]; otherwise no replacement value can connect them. When the condition does hold, choosing a value in that closed interval constructs a valid joined run of exactly the computed length. Thus each candidate is both an upper bound and achievable, and taking the maximum over all indices is optimal.

Complexity

The two run-length passes and the candidate scan each take O(n) time. The two auxiliary arrays use O(n) space.

Python solution

from collections.abc import Sequence


class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        """Return the longest non-decreasing subarray after at most one replacement."""
        if not nums:
            # LeetCode guarantees a non-empty input, but this keeps the helper robust.
            return 0

        ending_at, starting_at = self._build_run_lengths(nums)
        best_length = max(ending_at)  # The replacement is optional.
        size = len(nums)

        for replacement_index in range(size):
            left_length = (
                ending_at[replacement_index - 1]
                if replacement_index > 0
                else 0
            )
            right_length = (
                starting_at[replacement_index + 1]
                if replacement_index + 1 < size
                else 0
            )

            # A replacement can always attach to either neighboring run alone.
            best_length = max(
                best_length,
                left_length + 1,
                1 + right_length,
            )

            # It can attach to both runs when some integer fits between the
            # unchanged boundary values.
            has_two_neighbors = 0 < replacement_index < size - 1
            if (
                has_two_neighbors
                and nums[replacement_index - 1]
                <= nums[replacement_index + 1]
            ):
                best_length = max(
                    best_length,
                    left_length + 1 + right_length,
                )

        return best_length

    @staticmethod
    def _build_run_lengths(
        nums: Sequence[int],
    ) -> tuple[list[int], list[int]]:
        """Build maximal non-decreasing run lengths in both directions."""
        size = len(nums)
        ending_at = [1] * size
        starting_at = [1] * size

        for index in range(1, size):
            if nums[index - 1] <= nums[index]:
                ending_at[index] = ending_at[index - 1] + 1

        for index in range(size - 2, -1, -1):
            if nums[index] <= nums[index + 1]:
                starting_at[index] = starting_at[index + 1] + 1

        return ending_at, starting_at

Interview follow-ups

How would you return the chosen subarray and replacement value?

Keep candidate metadata whenever best_length improves: the left boundary, right boundary, replacement index, and whether the candidate uses the left side, the right side, or both. For a joined candidate, nums[i - 1] is a valid replacement because the bridge condition guarantees it is no greater than nums[i + 1]. For a one-sided candidate, copy the adjacent boundary value. If the best answer needs no replacement, record that explicitly.

This does not change the O(n) time or O(n) space bounds. The main engineering tradeoff is deterministic tie-breaking: the interviewer may want the earliest interval, the smallest replacement value, or a preference for leaving the array unchanged.

What changes if the subarray must be strictly increasing?

Build the two run arrays with strict comparisons instead of non-strict ones. A replacement that joins both sides must be an integer strictly between the neighbors. Therefore nums[i - 1] < nums[i + 1] is not quite enough: the integer domain requires at least one whole number between them, so the safe condition is nums[i - 1] + 1 < nums[i + 1].

The scan remains O(n) time and O(n) space. In a fixed-width language, avoid overflow by comparing the gap carefully or by widening the numeric type before adding one. If replacement values were real numbers rather than integers, a simple strict inequality between the neighbors would be sufficient.

What if the replacement value must lie in a fixed range?

Suppose the allowed replacement is in [low, high]. Joining both sides is possible only when the intervals [nums[i - 1], nums[i + 1]] and [low, high] overlap. In code, that is max(low, nums[i - 1]) <= min(high, nums[i + 1]). Extending only the left or right run needs the analogous one-sided feasibility check.

The same prefix-and-suffix structure still works in O(n) time and O(n) space. The important change is that attaching to one side is no longer automatic; every candidate must prove that an allowed replacement value exists.

What if one element may be deleted instead of replaced?

The two run arrays can be reused. Deleting index i joins the left and right runs when nums[i - 1] <= nums[i + 1], but the candidate length becomes ending_at[i - 1] + starting_at[i + 1] because the deleted position contributes no element. If the boundary condition fails, the best candidate keeps only one side.

The algorithm remains linear. This variant is slightly simpler because there is no replacement value to choose, but edge indices and the no-deletion baseline still need explicit handling.

Can the auxiliary memory be reduced without obscuring the main idea?

Store only starting_at. Then scan from left to right while maintaining the length of the current non-decreasing run ending immediately before the candidate index. That running prefix length replaces the entire ending_at array, while starting_at[i + 1] still supplies the future information needed to evaluate a bridge.

This version keeps O(n) time and reduces the auxiliary storage from two length-n arrays to one. A constant-space solution can process maximal non-decreasing runs and retain only neighboring run metadata, but its boundary bookkeeping is considerably easier to get wrong. In an interview, the one-array optimization is often the better clarity-versus-memory tradeoff unless constant space is an explicit requirement.