Katkat
Back

Find longest increasing contiguous subarray

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use a sliding window or linear scan approach to identify contiguous subarrays and your capacity to optimize for a single modification to extend an existing sequence.

Problem Statement

Given an array of integers nums, find the length of the longest contiguous subarray that is strictly increasing. You are allowed to perform at most one operation: you can choose any single element in the array and change its value to any integer.

Function Signature

def longest_increasing_subarray(nums: List[int]) -> int:

Examples

Example 1: Input: nums = [1, 2, 8, 4, 5] Output: 4 Explanation: Change 8 to 3. The array becomes [1, 2, 3, 4, 5], which is strictly increasing and has length 4.

Example 2: Input: nums = [5, 4, 3, 2, 1] Output: 2 Explanation: By changing any single element, the longest strictly increasing subarray will have length 2 (e.g., change 4 to 6, resulting in [5, 6] or change 5 to 2 for [2, 3]).

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Edge Cases

  • Empty array or array of length 1: The answer is the length of the array.
  • Already strictly increasing arrays: The result is the total length.
  • Arrays where modification doesn't help extend beyond the current max sequence length.

Hints

Hint 1

Identify all maximal strictly increasing subarrays first and store their start and end indices.

Hint 2

Consider the conditions required to merge two increasing subarrays: you can bridge them if the gap between them is exactly one element, or if the end of the first subarray + 1 is less than the start of the second subarray - 1.

Hint 3

For each element, check if modifying it can bridge the gap between its preceding increasing subarray and the following one by satisfying the condition: `nums[i-1] + 1 < nums[i+1]`.

Follow-up questions

  • How would the solution change if you were allowed to delete one element instead of modifying one?
  • What is the time and space complexity of your current solution, and can you optimize it to O(n) time and O(1) space?
  • How would you handle the requirement if the array elements could be floating-point numbers?