Longest Non-Decreasing Subarray After One Replacement
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `nums`, return the maximum length of a contiguous non-decreasing subarray obtainable after changing at most one array element to any integer value. You may also leave the array unchanged.
A subarray uses consecutive positions. It is non-decreasing when each element is less than or equal to the next element within that subarray.
### Input and Output
- Input: `nums`, an array of integers.
- Output: one integer, the maximum achievable length. Return the length only; no replacement value or subarray is required.
- Equal adjacent values are allowed. The one replacement, if used, may be at any array position, including an endpoint of the chosen subarray.
For this practice version, input values fit in signed 32-bit integers. An empty array has answer `0`. The source report gives no input-size bound.
### Example
```text
nums = [1, 0, 3, 4, 5, 2, 3]
answer = 5
```
Changing the second element from `0` to `1` gives a non-decreasing contiguous subarray `[1, 1, 3, 4, 5]` of length `5`.
Overview: Find the longest contiguous non-decreasing subarray after at most one element replacement, allowing equal values and an unchanged array.
Read the full Google Software Engineer interview experience this question came from
Given an integer array `nums`, return the maximum length of a contiguous non-decreasing subarray obtainable after changing at most one array element to any integer value. You may also leave the array unchanged.
A subarray uses consecutive positions. It is non-decreasing when each element is less than or equal to the next element within that subarray.
### Input and Output
- Input: `nums`, an array of integers.
- Output: one integer, the maximum achievable length. Return the length only; no replacement value or subarray is required.
- Equal adjacent values are allowed. The one replacement, if used, may be at any array position, including an endpoint of the chosen subarray.
For this practice version, input values fit in signed 32-bit integers. An empty array has answer `0`. The source report gives no input-size bound.
### Example
```text
nums = [1, 0, 3, 4, 5, 2, 3]
answer = 5
```
Changing the second element from `0` to `1` gives a non-decreasing contiguous subarray `[1, 1, 3, 4, 5]` of length `5`.
Constraints
- nums may be empty; return 0 for an empty array.
- Each input value fits in a signed 32-bit integer; no input-size bound is supplied.
- At most one value may change to any integer, including at a subarray endpoint.
- Equal adjacent values are allowed; return only the maximum contiguous length.
Examples
Input: ([1, 0, 3, 4, 5, 2, 3],)
Expected Output: 5
Explanation: Changing the second value from zero to one yields a length-five non-decreasing subarray.
Input: ([1, 5, 3, 4],)
Expected Output: 4
Explanation: Replacing the interior five by three joins both neighboring runs.
Hints
- A subarray uses consecutive positions and allows equal neighbors.
- The replacement, if used, may be at an endpoint.