# Adjacent Increasing Subarrays Detection II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/adjacent-increasing-subarrays-detection-ii)
Canonical: https://scaleengineer.com/dsa/problems/adjacent-increasing-subarrays-detection-ii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## 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.

**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 * 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force Iteration
This approach involves checking every possible length `k` and every possible starting position `a`. For each combination, it verifies if the two adjacent subarrays of length `k` are strictly increasing.
**Time:** O(n^3). The outer loop for `k` runs up to `n/2` times. The middle loop for `a` runs up to `n` times. The check for each pair of subarrays takes `O(k)` time. In the worst case, this is `O(n * n * n)`. · **Space:** O(1) extra space, as we are not using any auxiliary data structures that scale with the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
The most straightforward method is to test every possibility. We can iterate through all potential lengths `k`, starting from the largest possible (`n/2`) down to 1. For each `k`, we check every possible starting position `a`. At each position, we form two adjacent subarrays of length `k` and check if both are strictly increasing. The first value of `k` for which we find such a pair of subarrays is the maximum possible `k`.

```java
class Solution {
    private boolean isIncreasing(int[] nums, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] <= nums[i - 1]) {
                return false;
            }
        }
        return true;
    }

    public int findMaximumK(int[] nums) {
        int n = nums.length;
        for (int k = n / 2; k >= 1; k--) {
            for (int a = 0; a <= n - 2 * k; a++) {
                // Check first subarray: nums[a...a+k-1]
                boolean firstOk = isIncreasing(nums, a, a + k - 1);
                // Check second subarray: nums[a+k...a+2k-1]
                boolean secondOk = isIncreasing(nums, a + k, a + 2 * k - 1);

                if (firstOk && secondOk) {
                    return k; // Found the largest k, return immediately
                }
            }
        }
        return 0;
    }
}
```
### Algorithm
1. Iterate through all possible lengths `k` from `n/2` down to 1. The first `k` that satisfies the condition will be the maximum, so we can return it immediately.
2. For each `k`, iterate through all possible starting indices `a` for the first subarray, from `0` to `n - 2k`.
3. For each pair `(k, a)`, define two subarrays: `sub1 = nums[a...a+k-1]` and `sub2 = nums[a+k...a+2k-1]`.
4. Use a helper function `isIncreasing(subarray)` that checks if a given subarray is strictly increasing. This function iterates through the subarray and checks if `sub[i] > sub[i-1]` for all `i`.
5. If both `sub1` and `sub2` are strictly increasing, we have found our maximum `k` and can return it.
6. If the loops complete without finding a valid `k`, it means no such pair of subarrays exists, so we return 0.

## Brute Force with Precomputation
This approach improves upon the pure brute-force method by pre-calculating the lengths of all strictly increasing subarrays. This allows for an `O(1)` check for whether a subarray is increasing, reducing the overall complexity.
**Time:** O(n^2). Precomputation takes `O(n)`. The nested loops for `k` and `a` run in `O(n^2)`, and the check inside is `O(1)`. · **Space:** O(n) for the auxiliary `inc` array.
**Pros:** Faster than the pure brute-force approach.; The concept of precomputation is a useful optimization technique.
**Cons:** Still too slow for the given constraints, likely to time out.
### Explanation
To optimize the brute-force approach, we can avoid re-calculating whether a subarray is increasing repeatedly. We can pre-process the input array to store, for each index `i`, the length of the strictly increasing subarray ending at `i`. Let's call this array `inc`. This pre-computation takes linear time. After this, we can proceed with the same nested loops as the brute-force approach, but the check for an increasing subarray of length `k` ending at index `j` becomes a simple `O(1)` lookup: `inc[j] >= k`.

```java
class Solution {
    public int findMaximumK(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }

        int[] inc = new int[n];
        inc[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                inc[i] = inc[i - 1] + 1;
            } else {
                inc[i] = 1;
            }
        }

        for (int k = n / 2; k >= 1; k--) {
            for (int a = 0; a <= n - 2 * k; a++) {
                boolean firstOk = (inc[a + k - 1] >= k);
                boolean secondOk = (inc[a + 2 * k - 1] >= k);
                if (firstOk && secondOk) {
                    return k;
                }
            }
        }

        return 0;
    }
}
```
### Algorithm
1. Create an auxiliary array, `inc`, of size `n`. `inc[i]` will store the length of the strictly increasing subarray ending at index `i`.
2. Compute the `inc` array in a single `O(n)` pass: `inc[0] = 1`. For `i > 0`, if `nums[i] > nums[i-1]`, then `inc[i] = inc[i-1] + 1`, else `inc[i] = 1`.
3. Iterate through all possible lengths `k` from `n/2` down to 1.
4. For each `k`, iterate through all starting positions `a` from `0` to `n-2k`.
5. Check if a subarray is increasing in `O(1)` time. A subarray `nums[x...y]` is strictly increasing if its length (`y-x+1`) is less than or equal to `inc[y]`.
6. For a given `(k, a)`, check if `inc[a+k-1] >= k` and `inc[a+2k-1] >= k`.
7. If both conditions are true, we've found the maximum `k` and can return it.

## Binary Search on the Answer
This approach leverages the monotonic nature of the problem. If two adjacent increasing subarrays of length `k` exist, then they also exist for any length `k' < k`. This allows us to binary search for the maximum possible value of `k`.
**Time:** O(n log n). The precomputation takes `O(n)`. The binary search performs `O(log n)` iterations, and each `check(k)` call takes `O(n)`. The total time is `O(n + n log n) = O(n log n)`. · **Space:** O(n) for the precomputed `inc` array.
**Pros:** Significantly more efficient than `O(n^2)` approaches.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** More complex to conceptualize and implement than brute-force methods.
### Explanation
A more efficient way to find the maximum `k` is to use binary search on the value of `k` itself. The range of possible `k` values is from 0 to `n/2`. For a given `k`, we can check if it's possible to find two adjacent, strictly increasing subarrays of that length. Let's call this check `can_form(k)`. If `can_form(k)` is true, it implies that `can_form(k-1)` is also true. This monotonicity allows us to apply binary search.

The `can_form(k)` function can be implemented in `O(n)` time by first pre-calculating the lengths of increasing subarrays ending at each index, just like in the previous approach. Then, we iterate through the possible start positions `a` and perform an `O(1)` check.

```java
class Solution {
    public int findMaximumK(int[] nums) {
        int n = nums.length;
        int[] inc = new int[n];
        inc[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                inc[i] = inc[i - 1] + 1;
            } else {
                inc[i] = 1;
            }
        }

        int low = 0, high = n / 2, ans = 0;
        while (low <= high) {
            int k = low + (high - low) / 2;
            if (k == 0) {
                low = k + 1;
                continue;
            }
            if (check(k, n, inc)) {
                ans = k;
                low = k + 1;
            } else {
                high = k - 1;
            }
        }
        return ans;
    }

    private boolean check(int k, int n, int[] inc) {
        for (int a = 0; a <= n - 2 * k; a++) {
            boolean firstOk = (inc[a + k - 1] >= k);
            boolean secondOk = (inc[a + 2 * k - 1] >= k);
            if (firstOk && secondOk) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
1. Recognize the monotonic property: if a solution exists for length `k`, it also exists for any length `k' < k`.
2. This allows us to binary search for the answer `k` in the range `[0, n/2]`.
3. Create a helper function `check(k)` that returns `true` if two adjacent increasing subarrays of length `k` exist.
4. Implement `check(k)` efficiently using precomputation. First, compute an `inc` array where `inc[i]` is the length of the increasing subarray ending at `i`.
5. Inside `check(k)`, iterate from `a = 0` to `n - 2k`. For each `a`, check if `inc[a+k-1] >= k` and `inc[a+2k-1] >= k`. If found, return `true`.
6. In the main function, perform binary search. If `check(mid)` is true, a solution of length `mid` is possible, so we store it and try for a larger `k` (`low = mid + 1`). Otherwise, `mid` is too large, so we search in the lower half (`high = mid - 1`).
7. The precomputation of the `inc` array is done once before the binary search.

## Linear Time Solution with Two-Pass DP
The most efficient approach solves the problem in linear time using dynamic programming. It involves two passes over the array to precompute lengths of increasing subarrays from both left-to-right and right-to-left.
**Time:** O(n). We make three separate passes through the array: one to compute `left`, one to compute `right`, and one to find the maximum `k`. Each pass takes `O(n)` time, leading to a total of `O(n) + O(n) + O(n) = O(n)`. · **Space:** O(n). We use two auxiliary arrays, `left` and `right`, each of size `n`.
**Pros:** Optimal time complexity.; Conceptually clean, breaking the problem down by split points.
**Cons:** Requires extra space for two auxiliary arrays.
### Explanation
This optimal solution finds the answer in a single conceptual pass after some precomputation. The key insight is to consider every possible split point between two adjacent subarrays. A split point can be between index `i` and `i+1`.

For a given split point `i`, we need to find the longest increasing subarray ending at `i` and the longest increasing subarray starting at `i+1`. Let the lengths be `len1` and `len2` respectively. The largest `k` for which we can have two adjacent increasing subarrays of length `k` at this split point is `min(len1, len2)`. By checking this for all possible split points, we can find the global maximum `k`.

We can precompute these lengths using two DP arrays:
- `left[i]`: Stores the length of the strictly increasing subarray ending at `i`. This is computed in a forward pass.
- `right[i]`: Stores the length of the strictly increasing subarray starting at `i`. This is computed in a backward pass.

After populating both arrays, a final pass calculates `max(min(left[i], right[i+1]))` for all `i` from `0` to `n-2`.

```java
class Solution {
    public int findMaximumK(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return 0;
        }

        // left[i]: length of increasing subarray ending at i
        int[] left = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }

        // right[i]: length of increasing subarray starting at i
        int[] right = new int[n];
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                right[i] = right[i + 1] + 1;
            } else {
                right[i] = 1;
            }
        }

        int maxK = 0;
        // Check every split point between i and i+1
        for (int i = 0; i < n - 1; i++) {
            int k = Math.min(left[i], right[i + 1]);
            if (k > maxK) {
                maxK = k;
            }
        }

        return maxK;
    }
}
```
### Algorithm
1. The core idea is to find, for each possible split point `i` (between index `i` and `i+1`), the maximum length `k` that can be formed.
2. We need two pieces of information: the length of the longest strictly increasing subarray ending at `i`, and the length of the longest strictly increasing subarray starting at `i+1`.
3. Create a DP array `left[i]` to store the length of the strictly increasing subarray ending at `i`. Compute this with a left-to-right pass: `left[i] = (nums[i] > nums[i-1]) ? left[i-1] + 1 : 1`.
4. Create a second DP array `right[i]` to store the length of the strictly increasing subarray starting at `i`. Compute this with a right-to-left pass: `right[i] = (nums[i] < nums[i+1]) ? right[i+1] + 1 : 1`.
5. After computing both arrays, iterate through all possible split points `i` from `0` to `n-2`.
6. For each `i`, the maximum possible length `k` for this split is `min(left[i], right[i+1])`.
7. The final answer is the maximum `k` found across all split points.

# Solutions
### Java

```java
class Solution {
public
  int maxIncreasingSubarrays(List<Integer> nums) {
    int ans = 0, pre = 0, cur = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      ++cur;
      if (i == n - 1 || nums.get(i) >= nums.get(i + 1)) {
        ans = Math.max(ans, Math.max(cur / 2, Math.min(pre, cur)));
        pre = cur;
        cur = 0;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxIncreasingSubarrays(vector<int> &nums) {
    int ans = 0, pre = 0, cur = 0;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      ++cur;
      if (i == n - 1 || nums[i] >= nums[i + 1]) {
        ans = max({ans, cur / 2, min(pre, cur)});
        pre = cur;
        cur = 0;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int: ans = pre = cur = 0 for i, x in enumerate(nums): cur += 1 if i == len(nums) - 1 or x >= nums[i + 1]: ans = max(ans, cur // 2, min(pre, cur)) pre, cur = cur, 0 return ans

```