Implement longest increasing subarray with one deletion

Q: Implement longest increasing subarray with one deletion

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.

Q: 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.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Netflix.

Q: What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Netflix during technical interviews.

Question

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).

PracHub · Accepted Answer

def solution(nums):
    n = len(nums)
    best_len = 1
    best_l = 0
    best_r = 0

def update(cand_len, l, r):
        nonlocal best_len, best_l, best_r
        if cand_len > best_len or (cand_len == best_len and (l < best_l or (l == best_l and r < best_r))):
            best_len = cand_len
            best_l = l
            best_r = r

# The array can be viewed as maximal strictly increasing runs.
    # Any optimal answer is either:
    # 1) one entire run (no deletion), or
    # 2) two adjacent runs merged by deleting the last element of the left run
    #    or the first element of the right run.
    prev_s = None
    prev_e = None

i = 0
    while i < n:
        s = i
        while i + 1 < n and nums[i] < nums[i + 1]:
            i += 1
        e = i

# No deletion: use the whole current run.
        update(e - s + 1, s, e)

# Try to merge the previous run and the current run with one deletion.
        if prev_s is not None:
            can_merge = False

# Delete the last element of the previous run.
            # Then the bridge is nums[prev_e - 1] < nums[s], unless the previous run has length 1.
            if prev_s == prev_e or nums[prev_e - 1] < nums[s]:
                can_merge = True

# Delete the first element of the current run.
            # Then the bridge is nums[prev_e] < nums[s + 1], unless the current run has length 1.
            if s == e or nums[prev_e] < nums[s + 1]:
                can_merge = True

if can_merge:
                merged_len = (prev_e - prev_s + 1) + (e - s + 1) - 1
                update(merged_len, prev_s, e)

prev_s, prev_e = s, e
        i += 1

return [best_len, [best_l, best_r]]

Quick Overview

Solution

Hints