Adjacent increasing subarrays detection ii

Array Binary Search

58.9% acceptance

Feb 24, 2026

488

Given an array nums of n integers, your task is to find the maximum value of k for which there exist two adjacent subarrays of length k each, such that both subarrays are strictly increasing. Specifically, check if there are two subarrays of length k starting at indices a and b (a < b), where: Both subarrays nums[a..a + k - 1] and nums[b..b + k - 1] are strictly increasing. The subarrays must be adjacent, meaning b = a + k. Return the maximum possible value of k.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_increasing_subarrays(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // inc[i] = length of strictly increasing run ending at index i
    let mut inc = vec![1usize; n];
    for i in 1..n {
      if nums[i] > nums[i-1] { inc[i] = inc[i-1] + 1; }
    }
    // For each split point i (end of first subarray = i, start of second = i+1):
    // max k = min(inc[i], inc[end of second subarray])
    // We want to find all pairs of adjacent subarrays of length k
    // For split at position m (first subarray ends at m-1, second at m..m+k-1):
    // we need inc[m-1] >= k and inc[m+k-1] >= k
    // Equivalently: for each center point m (first array ends at m-1, second starts at m):
    // max k = min(inc[m-1], min over second array of inc)
    // Since inc is non-decreasing within each run, min of second run of length k ending at m+k-1
    // is inc[m] if inc[m] <= k, but we can take k = min(inc[m-1], inc[m+k-1])... 
    // Actually: inc[i] gives run length ending at i, so second subarray [m..m+k-1] is increasing
    // iff inc[m+k-1] >= k. And inc is monotone within increasing segment.
    // Best approach: for each m, k_max = min(inc[m-1], inc[m]) but capped at length of the run through m.
    // Actually it's: for center at m, max k such that [m-k..m-1] and [m..m+k-1] both increasing
    // = min(inc[m-1], inc[m+k-1]) >= k
    // The key insight: for fixed m, max k = min(inc[m-1], run_length_starting_at_m)
    // But run can extend beyond k positions. Let's use:
    // For each m, contribution = min(inc[m-1], inc[m]) ... wait inc[m] is run ending at m
    // If second array is [m..m+k-1], it's strictly increasing iff nums[m]>nums[m-1] is NOT required,
    // just nums[m]<nums[m+1]<...<nums[m+k-1] -> inc[m+k-1] >= k
    // For k = inc[m-1], check if inc[m + inc[m-1] - 1] >= inc[m-1]. 
    // Instead: for each m, answer contribution = min(inc[m-1], inc[m+k-1]) for some best k
    // Simpler O(n): best = max over all m of min(inc[m-1], inc[m]) ... NO
    // inc[m] = run ending AT m, not starting at m.
    // Let fwd[i] = run starting at i: fwd[i] = inc[i + fwd[i] - 1] by definition.
    // Compute fwd separately:
    let mut fwd = vec![1usize; n];
    for i in (0..n-1).rev() {
      if nums[i] < nums[i+1] { fwd[i] = fwd[i+1] + 1; }
    }
    // For center m: max k = min(inc[m-1], fwd[m])
    let mut best = 0usize;
    for m in 1..n {
      best = best.max(inc[m-1].min(fwd[m]));
    }
    best as i32
  }
}