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 Onsite rounds at Netflix.

What role is this question designed for?

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

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

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

Expected Output: [5, [0, 5]]

Explanation: Deleting 10 from the whole array leaves [1, 2, 3, 4, 5], so the best length is 5.

Input: ([42],)

Expected Output: [1, [0, 0]]

Explanation: A single element is already strictly increasing.

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

Expected Output: [5, [0, 4]]

Explanation: The array is already strictly increasing, so the whole array is optimal.

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

Expected Output: [3, [0, 3]]

Explanation: Deleting 5 from the whole array leaves [1, 2, 3] of length 3, which is lexicographically smaller than [1, 3].

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

Expected Output: [3, [0, 2]]

Explanation: Deleting 0 from [0, 3] also gives length 3, but [0, 2] is lexicographically smaller than [0, 3].

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

Expected Output: [4, [0, 4]]

Explanation: Deleting either of the equal 2s from the whole array yields [1, 2, 3, 4].

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

Expected Output: [4, [0, 4]]

Explanation: Several spans achieve length 4, such as [1, 4] and [1, 5], but [0, 4] is lexicographically smallest because deleting 5 leaves [1, 2, 3, 4].

Solution

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]]

Time complexity: O(n). Space complexity: O(1).

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.

Quick Overview

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.