Adjacent Increasing Subarrays Detection II

Problem

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.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1:

Input: nums = [2,5,7,8,9,2,3,4,3,1]
Output: 3
Explanation:
  * The subarray starting at index 2 is `[7, 8, 9]`, which is strictly increasing.
  * The subarray starting at index 5 is `[2, 3, 4]`, which is also strictly increasing.
  * These two subarrays are adjacent, and 3 is the **maximum** possible value of `k` for which two such adjacent strictly increasing subarrays exist.

Example 2:

Input: nums = [1,2,3,4,4,4,4,5,6,7]
Output: 2
Explanation:
  * The subarray starting at index 0 is `[1, 2]`, which is strictly increasing.
  * The subarray starting at index 2 is `[3, 4]`, which is also strictly increasing.
  * These two subarrays are adjacent, and 2 is the **maximum** possible value of `k` for which two such adjacent strictly increasing subarrays exist.

Constraints:

• 2 <= nums.length <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

Solution

Method 1 – Binary Search with Sliding Window

Intuition

We want the largest k such that there exist two adjacent subarrays of length k that are both strictly increasing. Since checking for all possible k is inefficient, we can use binary search on k and efficiently check for each k using a sliding window.

Approach

1. Binary Search on k:

• Set lo = 1, hi = n // 2 (since two adjacent subarrays of length k need 2k <= n).
• For each k, check if there exist two adjacent strictly increasing subarrays of length k.

2. Check Function:

• For each possible starting index i (from 0 to n - 2*k + 1), check if both nums[i:i+k] and nums[i+k:i+2*k] are strictly increasing.
• Use a sliding window to efficiently check if a subarray is strictly increasing by precomputing an array inc where inc[i] is the length of the strictly increasing sequence starting at i.

3. Return:

• The largest k for which the check passes.

Code

C++

class Solution {
public:
  int maxIncreasingSubarrays(std::vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return 0;
    std::vector<int> inc(n, 1);
    for (int i = n - 2; i >= 0; --i) {
      inc[i] = (nums[i] < nums[i + 1]) ? inc[i + 1] + 1 : 1;
    }
    int lo = 1, hi = n / 2, ans = 0;
    while (lo <= hi) {
      int k = (lo + hi) / 2;
      bool found = false;
      for (int i = 0; i + 2 * k <= n; ++i) {
        if (inc[i] >= k && inc[i + k] >= k) { found = true; break; }
      }
      if (found) { ans = k; lo = k + 1; } else { hi = k - 1; }
    }
    return ans;
  }
};

Go

package solution

type Solution struct{}

func (s *Solution) maxIncreasingSubarrays(nums []int) int {
  n := len(nums)
  if n < 2 { return 0 }
  inc := make([]int, n)
  for i := range inc { inc[i] = 1 }
  for i := n - 2; i >= 0; i-- {
    if nums[i] < nums[i+1] { inc[i] = inc[i+1] + 1 } else { inc[i] = 1 }
  }
  lo, hi, ans := 1, n/2, 0
  for lo <= hi {
    k := (lo + hi) / 2
    found := false
    for i := 0; i+2*k <= n; i++ {
      if inc[i] >= k && inc[i+k] >= k { found = true; break }
    }
    if found { ans = k; lo = k + 1 } else { hi = k - 1 }
  }
  return ans
}

Java

class Solution {
  public int maxIncreasingSubarrays(List<Integer> nums) {
    int n = nums.size();
    if (n < 2) return 0;
    int[] inc = new int[n];
    Arrays.fill(inc, 1);
    for (int i = n - 2; i >= 0; --i) {
      inc[i] = nums.get(i) < nums.get(i + 1) ? inc[i + 1] + 1 : 1;
    }
    int lo = 1, hi = n / 2, ans = 0;
    while (lo <= hi) {
      int k = (lo + hi) / 2;
      boolean found = false;
      for (int i = 0; i + 2 * k <= n; ++i) {
        if (inc[i] >= k && inc[i + k] >= k) { found = true; break; }
      }
      if (found) { ans = k; lo = k + 1; } else { hi = k - 1; }
    }
    return ans;
  }
}

Kotlin

class Solution {
  fun maxIncreasingSubarrays(nums: List<Int>): Int {
    val n = nums.size
    if (n < 2) return 0
    val inc = IntArray(n) { 1 }
    for (i in n - 2 downTo 0) {
      inc[i] = if (nums[i] < nums[i + 1]) inc[i + 1] + 1 else 1
    }
    var lo = 1
    var hi = n / 2
    var ans = 0
    while (lo <= hi) {
      val k = (lo + hi) / 2
      var found = false
      for (i in 0..(n - 2 * k)) {
        if (inc[i] >= k && inc[i + k] >= k) { found = true; break }
      }
      if (found) { ans = k; lo = k + 1 } else { hi = k - 1 }
    }
    return ans
  }
}

Python

class Solution:
  def maxIncreasingSubarrays(self, nums: list[int]) -> int:
    n = len(nums)
    if n < 2:
      return 0
    inc = [1] * n
    for i in range(n - 2, -1, -1):
      if nums[i] < nums[i + 1]:
        inc[i] = inc[i + 1] + 1
    ans = 0
    lo, hi = 1, n // 2
    while lo <= hi:
      k = (lo + hi) // 2
      found = False
      for i in range(0, n - 2 * k + 1):
        if inc[i] >= k and inc[i + k] >= k:
          found = True
          break
      if found:
        ans = k
        lo = k + 1
      else:
        hi = k - 1
    return ans

Rust

pub struct Solution;

impl Solution {
  pub fn maxIncreasingSubarrays(&self, nums: Vec<i64>) -> i32 {
    let n = nums.len();
    if n < 2 { return 0; }
    let mut inc = vec![1usize; n];
    for i in (0..n-1).rev() {
      inc[i] = if nums[i] < nums[i+1] { inc[i+1] + 1 } else { 1 };
    }
    let mut lo = 1usize;
    let mut hi = n / 2;
    let mut ans = 0i32;
    while lo <= hi {
      let k = (lo + hi) / 2;
      let mut found = false;
      for i in 0..=n - 2 * k {
        if inc[i] >= k && inc[i + k] >= k { found = true; break; }
      }
      if found { ans = k as i32; lo = k + 1; } else { if k==0 { break; } hi = k - 1; }
    }
    ans
  }
}

Typescript

class Solution {
  maxIncreasingSubarrays(nums: number[]): number {
    const n = nums.length;
    if (n < 2) return 0;
    const inc: number[] = new Array(n).fill(1);
    for (let i = n - 2; i >= 0; --i) inc[i] = nums[i] < nums[i + 1] ? inc[i + 1] + 1 : 1;
    let lo = 1, hi = Math.floor(n / 2), ans = 0;
    while (lo <= hi) {
      const k = Math.floor((lo + hi) / 2);
      let found = false;
      for (let i = 0; i + 2 * k <= n; ++i) {
        if (inc[i] >= k && inc[i + k] >= k) { found = true; break; }
      }
      if (found) { ans = k; lo = k + 1; } else { hi = k - 1; }
    }
    return ans;
  }
}

Complexity

• ⏰ Time complexity: O(N log N) (preprocessing + binary search, each check is O(N))
• 🧺 Space complexity: O(N) (for the inc array)