Implement longest increasing subarray with one deletion
Company: Netflix
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an array of integers nums, return the length of the longest strictly increasing contiguous subarray you can obtain by deleting at most one element from that subarray (you may also choose to delete none). Strictly increasing means nums[i] < nums[i+1]. Constraints: 1 <= len(nums) <= 2e5; values may be negative and may have duplicates. Time O(n), extra space O(1). Also return one pair of 0-based indices [l, r] of such a maximum subarray in the original array (if multiple, pick the lexicographically smallest [l, r]). Examples: (a) nums = [1, 3, 5, 4, 7] -> length 4, one valid answer is [0, 3] by deleting 4 to make [1,3,5,7]; (b) nums = [2, 2, 2] -> length 1, e.g., [0,0]; (c) nums = [1, 2, 10, 3, 4, 5] -> length 5, e.g., [1,5] by deleting 10. Describe your algorithm, prove correctness, and provide tests for edge cases (length 1, strictly increasing already, all equal, decrease at boundaries).
Quick Answer: This question evaluates proficiency in array algorithms and algorithmic optimization, focusing on handling boundary cases, reconstructing index ranges, and meeting strict O(n) time and O(1) extra-space constraints.
Given an integer array nums, choose a contiguous subarray nums[l:r+1]. You may delete at most one element from this chosen subarray, and the remaining elements must stay in their original order. After the optional deletion, the remaining sequence must be strictly increasing, meaning every adjacent pair satisfies a[i] < a[i+1]. Return [best_length, [l, r]], where best_length is the maximum possible number of remaining elements after deleting at most one element. If multiple pairs [l, r] achieve the same best_length, return the lexicographically smallest pair (smaller l first, and if tied, smaller r). For example, for nums = [1, 3, 5, 4, 7], choosing [0, 4] and deleting 4 leaves [1, 3, 5, 7], so the achievable length is 4. Your algorithm should run in O(n) time and use O(1) extra space.
Constraints
- 1 <= len(nums) <= 2 * 10^5
- nums[i] is an integer; values may be negative and duplicates are allowed
- If multiple optimal answers exist, return the lexicographically smallest [l, r]
- Target complexity: O(n) time and O(1) extra space
Examples
Input: ([1, 3, 5, 4, 7],)
Expected Output: [4, [0, 4]]
Explanation: Choose the whole array and delete 4 (or 5). The remaining sequence has length 4.
Input: ([2, 2, 2],)
Expected Output: [1, [0, 0]]
Explanation: No strictly increasing sequence longer than 1 is possible. The lexicographically smallest optimal pair is [0, 0].
Hints
- Break the array into maximal strictly increasing runs. Any answer without deletion is just one such run.
- If an optimal span uses one deletion and crosses a run boundary, the deleted element must be either the last element of the left run or the first element of the right run.