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:

1
2
3
4
5
6

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:

1
2
3
4
5
6

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
  • -109 <= 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.
  1. 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.
  1. Return:
  • The largest k for which the check passes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
   int maxLength(vector<int>& nums) {
      int n = nums.size(), ans = 0;
      vector<int> inc(n, 1);
      for (int i = n - 2; i >= 0; --i)
        if (nums[i] < nums[i + 1]) inc[i] = inc[i + 1] + 1;
      int lo = 1, hi = n / 2;
      while (lo <= hi) {
        int k = (lo + hi) / 2, found = 0;
        for (int i = 0; i + 2 * k <= n; ++i) {
           if (inc[i] >= k && inc[i + k] >= k) {
              found = 1; break;
           }
        }
        if (found) { ans = k; lo = k + 1; }
        else hi = k - 1;
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
   public int maxLength(int[] nums) {
      int n = nums.length, ans = 0;
      int[] inc = new int[n];
      inc[n - 1] = 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;
      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;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
   def maxLength(self, nums: list[int]) -> int:
      n: int = len(nums)
      inc: list[int] = [1] * n
      for i in range(n - 2, -1, -1):
        if nums[i] < nums[i + 1]:
           inc[i] = inc[i + 1] + 1
      ans: int = 0
      lo, hi = 1, n // 2
      while lo <= hi:
        k: int = (lo + hi) // 2
        found: bool = False
        for i in range(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

Complexity

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