How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find longest increasing contiguous subarray

Q: Find longest increasing contiguous subarray

This question evaluates proficiency in array processing and algorithmic optimization, focusing on recognition of contiguous subarray properties and handling a single-value modification to achieve strict monotonicity.

Find longest increasing contiguous subarray

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem You are given an integer array `nums` (length `n`). ### Part 1 Find the length of the **longest contiguous subarray** that is **strictly increasing** (i.e., for every adjacent pair in the subarray, `a[i] < a[i+1]`). **Input:** `nums: int[]` **Output:** `maxLen: int` **Example:** - `nums = [1, 2, 2, 3, 4]` → longest strictly increasing contiguous subarray is `[2,3,4]`, so `maxLen = 3`. ### Follow-up Now suppose you may **modify (replace) the value of at most one element** within a chosen contiguous subarray (replace it with any integer value you want) in order to make that subarray strictly increasing. Return the maximum possible length of a contiguous subarray that can be made strictly increasing with **≤ 1** replacement. **Clarification/assumption (make explicit in interview):** The replacement value is unconstrained (can be any integer), and you are asked only for the maximum achievable length. **Example idea:** - `nums = [1, 5, 3, 4]` → by replacing `5` with `2`, the whole array can become `[1,2,3,4]`, so answer is `4`. ### Constraints (reasonable interview defaults) - `1 <= n <= 2e5` - `-1e9 <= nums[i] <= 1e9` - Aim for better than `O(n^2)` in the follow-up.

Quick Answer: This question evaluates proficiency in array processing and algorithmic optimization, focusing on recognition of contiguous subarray properties and handling a single-value modification to achieve strict monotonicity.

Longest Strictly Increasing Contiguous Subarray

You are given an integer array `nums` of length `n`. Find the length of the **longest contiguous subarray** that is **strictly increasing** — that is, for every adjacent pair inside the subarray, `a[i] < a[i+1]`. Return `maxLen`, the length of that subarray. **Example:** `nums = [1, 2, 2, 3, 4]` → the longest strictly increasing contiguous subarray is `[2, 3, 4]`, so `maxLen = 3`. **Constraints:** - `0 <= n <= 2 * 10^5` - `-10^9 <= nums[i] <= 10^9` Return `0` for an empty array.

Constraints

0 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
Return 0 for an empty array
Strictly increasing means a[i] < a[i+1] (equal values break the run)

Examples

Input: ([1, 2, 2, 3, 4],)

Expected Output: 3

Explanation: The run [2, 3, 4] is the longest strictly increasing block; the first 2->2 breaks the run.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 5

Explanation: The whole array is strictly increasing.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 1

Explanation: No adjacent pair increases, so the longest run is a single element.

Input: ([7],)

Expected Output: 1

Explanation: A single element is trivially a run of length 1.

Input: ([],)

Expected Output: 0

Explanation: Empty array returns 0.

Input: ([2, 2, 2, 2],)

Expected Output: 1

Explanation: Equal values are not strictly increasing, so each run has length 1.

Input: ([1, 3, 2, 4, 6, 5, 7, 8, 9],)

Expected Output: 4

Explanation: The run [5, 7, 8, 9] at the end has length 4, longer than [2, 4, 6].

Input: ([-5, -3, -1, 0, 0, 1],)

Expected Output: 4

Explanation: The run [-5, -3, -1, 0] has length 4; the 0->0 pair stops it.

Hints

Scan left to right, keeping a running length of the current strictly increasing run.
Whenever nums[i] > nums[i-1], extend the run; otherwise reset the run length to 1.
Track the maximum run length seen. This is a single O(n) pass with O(1) extra space.

Longest Subarray Made Strictly Increasing With At Most One Replacement

You are given an integer array `nums` of length `n`. You may **replace the value of at most one element** of a chosen contiguous subarray with **any integer you want** (the replacement value is unconstrained). Using at most one such replacement, return the **maximum possible length** of a contiguous subarray that can be made **strictly increasing**. **Example:** `nums = [1, 5, 3, 4]` → replace `5` with `2` to get `[1, 2, 3, 4]`, so the answer is `4`. Note that even with a free integer choice, a replacement is not always enough: e.g. in `[1, 100, 2]` you cannot make the whole array increasing (replacing 100 would need an integer strictly between 1 and 2, which does not exist), so the best contiguous window is length 3 only via `[1, 100, v]` with v > 100... actually `[1, 100, 2]` → replace the trailing `2` with `101` giving `[1, 100, 101]`, length 3. **Constraints:** - `0 <= n <= 2 * 10^5` - `-10^9 <= nums[i] <= 10^9` - Aim for better than O(n^2). Return `0` for an empty array.

Constraints

0 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
The replacement value may be any integer (unconstrained)
At most one element of the chosen subarray may be replaced
Aim for better than O(n^2); an O(n) sliding window is expected
Return 0 for an empty array

Examples

Input: ([1, 5, 3, 4],)

Expected Output: 4

Explanation: Replace 5 with 2 to get [1, 2, 3, 4]; the whole array becomes strictly increasing, length 4.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 5

Explanation: Already strictly increasing; no replacement needed.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 2

Explanation: Every adjacent pair is decreasing, so at most a length-2 window (one pair) can be fixed with a single replacement.

Input: ([7],)

Expected Output: 1

Explanation: A single element is already a length-1 increasing window.

Input: ([],)

Expected Output: 0

Explanation: Empty array returns 0.

Input: ([3, 3, 3, 3],)

Expected Output: 2

Explanation: Any length-2 window has one bad pair (equal values) fixable by one replacement, but length 3 has two non-fixable equal pairs with no room.

Input: ([1, 100, 2],)

Expected Output: 3

Explanation: Replace the trailing 2 with 101 to get [1, 100, 101], length 3; replacing the middle 100 would need an integer strictly between 1 and 2, which is impossible, but the endpoint replacement works.

Input: ([10, 1, 2, 3],)

Expected Output: 4

Explanation: Replace the leading 10 with 0 to get [0, 1, 2, 3]; the bad pair is at the window's left endpoint so the replacement always succeeds.

Input: ([1, 2, 2, 3, 4],)

Expected Output: 4

Explanation: Window [1, 2, 2, 3]: replace the first 2 with any value below... here the achievable length is 4 (e.g. replace one element of a 4-length window so all four become strictly increasing).

Input: ([-5, -3, -1, 0, 0, 1],)

Expected Output: 5

Explanation: The single bad pair is 0 >= 0; replacing one of those zeros within a 5-length window (which has the bad pair at its boundary or with room) yields a strictly increasing length-5 window.

Hints

Call a pair (i, i+1) 'bad' if nums[i] >= nums[i+1]. A single replacement at position k only changes the pairs (k-1, k) and (k, k+1), so any fixable window must have all of its bad pairs touch one common element.
A window with 0 bad pairs is already increasing. A window with >= 3 bad pairs can never be fixed by one replacement. The interesting cases are exactly 1 or exactly 2 bad pairs.
With one bad pair you usually replace one of its two endpoints, but you must check there is room: an integer strictly between the two surrounding neighbors must exist (e.g. nums[p] < nums[p+2] - 1), unless that endpoint is at the window boundary (then it has a free side).
With two bad pairs they must be adjacent (share the middle element p+1) and you replace that middle element, which needs nums[p0] < nums[p0+2] - 1 for an integer to fit. Slide a window with a two-pointer, maintaining the bad-pair indices, shrinking from the left whenever the window becomes infeasible.

Find longest increasing contiguous subarray

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Longest Strictly Increasing Contiguous Subarray

Constraints

0 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
Return 0 for an empty array
Strictly increasing means a[i] < a[i+1] (equal values break the run)

Examples

Input: ([1, 2, 2, 3, 4],)

Expected Output: 3

Explanation: The run [2, 3, 4] is the longest strictly increasing block; the first 2->2 breaks the run.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 5

Explanation: The whole array is strictly increasing.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 1

Explanation: No adjacent pair increases, so the longest run is a single element.

Input: ([7],)

Expected Output: 1

Explanation: A single element is trivially a run of length 1.

Input: ([],)

Expected Output: 0

Explanation: Empty array returns 0.

Input: ([2, 2, 2, 2],)

Expected Output: 1

Explanation: Equal values are not strictly increasing, so each run has length 1.

Input: ([1, 3, 2, 4, 6, 5, 7, 8, 9],)

Expected Output: 4

Explanation: The run [5, 7, 8, 9] at the end has length 4, longer than [2, 4, 6].

Input: ([-5, -3, -1, 0, 0, 1],)

Expected Output: 4

Explanation: The run [-5, -3, -1, 0] has length 4; the 0->0 pair stops it.

Hints

Scan left to right, keeping a running length of the current strictly increasing run.
Whenever nums[i] > nums[i-1], extend the run; otherwise reset the run length to 1.
Track the maximum run length seen. This is a single O(n) pass with O(1) extra space.

Longest Subarray Made Strictly Increasing With At Most One Replacement

Constraints

0 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
The replacement value may be any integer (unconstrained)
At most one element of the chosen subarray may be replaced
Aim for better than O(n^2); an O(n) sliding window is expected
Return 0 for an empty array

Examples

Input: ([1, 5, 3, 4],)

Expected Output: 4

Explanation: Replace 5 with 2 to get [1, 2, 3, 4]; the whole array becomes strictly increasing, length 4.

Input: ([1, 2, 3, 4, 5],)

Expected Output: 5

Explanation: Already strictly increasing; no replacement needed.

Input: ([5, 4, 3, 2, 1],)

Expected Output: 2

Explanation: Every adjacent pair is decreasing, so at most a length-2 window (one pair) can be fixed with a single replacement.

Input: ([7],)

Expected Output: 1

Explanation: A single element is already a length-1 increasing window.

Input: ([],)

Expected Output: 0

Explanation: Empty array returns 0.

Input: ([3, 3, 3, 3],)

Expected Output: 2

Explanation: Any length-2 window has one bad pair (equal values) fixable by one replacement, but length 3 has two non-fixable equal pairs with no room.

Input: ([1, 100, 2],)

Expected Output: 3

Input: ([10, 1, 2, 3],)

Expected Output: 4

Explanation: Replace the leading 10 with 0 to get [0, 1, 2, 3]; the bad pair is at the window's left endpoint so the replacement always succeeds.

Input: ([1, 2, 2, 3, 4],)

Expected Output: 4

Explanation: Window [1, 2, 2, 3]: replace the first 2 with any value below... here the achievable length is 4 (e.g. replace one element of a 4-length window so all four become strictly increasing).

Input: ([-5, -3, -1, 0, 0, 1],)

Expected Output: 5

Explanation: The single bad pair is 0 >= 0; replacing one of those zeros within a 5-length window (which has the bad pair at its boundary or with room) yields a strictly increasing length-5 window.

Hints

Call a pair (i, i+1) 'bad' if nums[i] >= nums[i+1]. A single replacement at position k only changes the pairs (k-1, k) and (k, k+1), so any fixable window must have all of its bad pairs touch one common element.
A window with 0 bad pairs is already increasing. A window with >= 3 bad pairs can never be fixed by one replacement. The interesting cases are exactly 1 or exactly 2 bad pairs.
With one bad pair you usually replace one of its two endpoints, but you must check there is room: an integer strictly between the two surrounding neighbors must exist (e.g. nums[p] < nums[p+2] - 1), unless that endpoint is at the window boundary (then it has a free side).
With two bad pairs they must be adjacent (share the middle element p+1) and you replace that middle element, which needs nums[p0] < nums[p0+2] - 1 for an integer to fit. Slide a window with a two-pointer, maintaining the bad-pair indices, shrinking from the left whenever the window becomes infeasible.

Quick Overview

Quick Overview