What is the best approach for Longest Non-Decreasing Subarray After Replacing at Most One Element?

The prefix and suffix decomposition approach is the most efficient. Precompute the longest non-decreasing subarray ending at each index and starting at each index, then evaluate every position as the replacement point. This allows constant-time merging checks and produces an overall O(n) time solution with O(n) space.

Is Longest Non-Decreasing Subarray After Replacing at Most One Element asked at Google/Amazon/Meta?

Problems involving longest non-decreasing segments and single modifications appear frequently in interviews at companies like Google, Amazon, and Meta. They test array traversal, boundary reasoning, and prefix/suffix preprocessing techniques commonly used in dynamic programming patterns.

What data structure is used in Longest Non-Decreasing Subarray After Replacing at Most One Element?

The solution primarily uses arrays to store prefix and suffix lengths. These auxiliary arrays allow constant-time lookup of the longest valid segment on either side of a candidate replacement index.

What is the time complexity of Longest Non-Decreasing Subarray After Replacing at Most One Element?

The optimal solution runs in O(n) time because the array is scanned a constant number of times to build prefix and suffix lengths and then evaluated once more for the replacement position. Space complexity is O(n) for the auxiliary arrays that store segment lengths.

Description Hints 5 Solution Video 19:09

3738. Longest Non-Decreasing Subarray After Replacing at Most One Element

Q: Is Longest Non-Decreasing Subarray After Replacing at Most One Element easy or hard?

The problem is typically rated Medium difficulty. The main challenge is recognizing that a single replacement can connect two valid segments, which leads to the prefix–suffix preprocessing technique rather than brute-force scanning.

Q: Longest Non-Decreasing Subarray After Replacing at Most One Element Python/Java solution

Implement the prefix and suffix approach by first computing two arrays storing non-decreasing segment lengths. Then iterate through each index to test the effect of replacing that element. The same logic works across Python, Java, C++, Go, and TypeScript with O(n) time complexity.

Q: How to solve Longest Non-Decreasing Subarray After Replacing at Most One Element in O(n)?

Compute two arrays: prefix[i] for the longest non-decreasing segment ending at i and suffix[i] for the segment starting at i. For each index i, treat it as the replaced element and check whether nums[i-1] can connect with nums[i+1]. If the boundary condition holds, combine prefix[i-1] and suffix[i+1] with the replaced element to form a longer segment.

Medium23.5% acceptance1 company

You are given an integer array nums.

You are allowed to replace at most one element in the array with any other integer value of your choice.

Return the length of the longest non-decreasing subarray that can be obtained after performing at most one replacement.

An array is said to be non-decreasing if each element is greater than or equal to its previous one (if it exists).

Example 1:

Input: nums = [1,2,3,1,2]

Output: 4

Explanation:

Replacing nums[3] = 1 with 3 gives the array [1, 2, 3, 3, 2].

The longest non-decreasing subarray is [1, 2, 3, 3], which has a length of 4.

Example 2:

Input: nums = [2,2,2,2,2]

Output: 5

Explanation:

All elements in nums are equal, so it is already non-decreasing and the entire nums forms a subarray of length 5.

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Asked at 1 company

Google

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Use prefix and suffix arrays

Hint 2

Create a prefix array where pref[i] denotes the maximum-length non-decreasing subarray ending at i

Hint 3

Create a suffix array where suff[i] denotes the maximum-length non-decreasing subarray starting at i

Hint 4

Let the initial maximum be max(max(pref), max(suff))

Hint 5

For each index i, try to combine the prefix ending at i - 1 and the suffix starting at i + 1 if possible; also consider the maximum without combining them

19:09

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestSubarray(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3,1,2]

Input

[2,2,2,2,2]

Your code is saved on this device.Solution