Skip to content

Longest Sequence After Substitution

Level: L3-L4 Topics: Arrays, Sliding Window, Greedy

Problem Statement

Given an array of integers, find the length of the longest contiguous non-decreasing subarray.

Then solve increasingly challenging variants that allow modifying the array.

Background & Constraints

  • The array can contain up to 10^5 or 10^6 elements.
  • Elements can be any integers (positive, negative, or zero).
  • A non-decreasing subarray is one where a[i] <= a[i+1] for all consecutive pairs.
  • The basic version requires no modifications to the array.

Examples

Basic problem:

Array: [1, 3, 5, 2, 4, 6, 8, 1, 2]
Non-decreasing subarrays: [1,3,5], [2,4,6,8], [1,2]
Longest: [2, 4, 6, 8] with length 4
Answer: 4

Example with all equal:

Array: [5, 5, 5, 5]
Answer: 4 (the entire array is non-decreasing)

Example with strictly decreasing:

Array: [5, 4, 3, 2, 1]
Answer: 1 (each element alone)

Hints & Common Pitfalls

Basic Version

  • Simple linear scan: walk through the array, maintaining the current run length. When a[i] < a[i-1], reset the counter. Track the maximum.
  • Time: O(N), Space: O(1).

Variant 1: Substitute One Element

Problem: You may change one element to any integer value. Find the maximum length of a non-decreasing contiguous subarray after this one substitution.

  • Key insight: Changing one element can bridge two adjacent non-decreasing runs. Consider each position as a potential substitution point and check if the runs on either side can be merged.

  • Approach: Precompute the length of the non-decreasing run ending at each index (left[i]) and starting at each index (right[i]). For each index i, check if substituting a[i] can merge the run ending at i-1 with the run starting at i+1. The merge is valid if a[i-1] <= a[i+1] (so a value between them exists) or if the gap is small enough.

  • Edge case: Substituting the first or last element simply extends one run by 1.

Variant 2: Substitute All of One Value

Problem: Pick one value v present in the array and change all occurrences of v to any other value w that already exists in the array. Maximize the longest non-decreasing contiguous subarray.

  • Key insight: This is harder because the substitution affects multiple positions simultaneously. You need to consider which value to replace and what to replace it with.

  • Approach: For each pair (v, w) where v and w are distinct values in the array, simulate replacing all v with w and compute the longest non-decreasing subarray. Optimizing this brute force is the challenge.

  • Optimization: The number of distinct values may be much smaller than N. Focus on values that appear at "break points" (positions where the non-decreasing property is violated).

Follow-Up Questions

  1. Substitute up to K elements: Generalize variant 1 to allow substituting up to K elements. Can you solve this with a sliding window approach? What is the time complexity?

  2. Strictly increasing: How do the solutions change if you need strictly increasing instead of non-decreasing?

  3. Circular array: What if the array is circular (the last element is followed by the first)? How does this affect each variant?