# Adjacent Increasing Subarrays Detection I
**Difficulty:** EASY
[External](https://leetcode.com/problems/adjacent-increasing-subarrays-detection-i)
Canonical: https://scaleengineer.com/dsa/problems/adjacent-increasing-subarrays-detection-i
**Data structures:** Array
---
## Problem
Given an array `nums` of `n` integers and an integer `k`, determine whether there exist **two** **adjacent** subarrays of length `k` such that both subarrays are **strictly** **increasing**. Specifically, check if there are **two** subarrays 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 `true` if it is _possible_ to find **two** such subarrays, and `false` otherwise.

**Example 1:**

**Input:** nums = \[2,5,7,8,9,2,3,4,3,1\], k = 3

**Output:** true

**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, so the result is `true`.

**Example 2:**

**Input:** nums = \[1,2,3,4,4,4,4,5,6,7\], k = 5

**Output:** false

**Constraints:**

* `2 <= nums.length <= 100`
* `1 < 2 * k <= nums.length`
* `-1000 <= nums[i] <= 1000`

# Approaches
## Brute Force with Helper Function
This approach directly translates the problem statement into code. We iterate through all possible starting positions for the first of the two adjacent subarrays. For each position, we check if the two corresponding subarrays of length `k` are strictly increasing.
**Time:** O(n * k). The outer loop runs `n - 2k + 1` times, which is `O(n)`. Inside the loop, we call `isIncreasing` twice. Each call takes `O(k)` time. Thus, the total time complexity is `O(n * k)`. · **Space:** O(1). We only use a few variables for loops and indices, which does not depend on the input size.
**Pros:** Simple to understand and implement.; Low memory usage.
**Cons:** Can be inefficient for large `n` and `k`, as it performs redundant comparisons for overlapping parts of subarrays in consecutive iterations.
### Explanation
We can write a helper function, `isIncreasing(nums, start, k)`, that checks if the subarray of length `k` starting at `start` is strictly increasing. This function iterates from `start` to `start + k - 2`, comparing `nums[i]` with `nums[i+1]`. If it finds any pair where `nums[i] >= nums[i+1]`, it returns `false`. If the loop completes, it returns `true`.

The main function will loop through all possible starting indices `a` for the first subarray. The loop for `a` will run from `0` to `n - 2k`, where `n` is the length of `nums`. This range ensures that two full subarrays of length `k` fit within the array bounds.

Inside the loop, for each `a`, we call `isIncreasing(nums, a, k)` to check the first subarray and `isIncreasing(nums, a + k, k)` to check the second, adjacent subarray.

If both calls return `true`, we have found our pair, and we can immediately return `true`.

If the loop finishes without finding such a pair, it means none exist, so we return `false`.

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

    public boolean solve(int[] nums, int k) {
        int n = nums.length;
        if (2 * k > n) {
            return false;
        }
        for (int a = 0; a <= n - 2 * k; a++) {
            boolean firstSubarrayIsIncreasing = isIncreasing(nums, a, k);
            boolean secondSubarrayIsIncreasing = isIncreasing(nums, a + k, k);
            if (firstSubarrayIsIncreasing && secondSubarrayIsIncreasing) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Define a helper function `isIncreasing(nums, start, k)`:
  - Loop `i` from `start` to `start + k - 2`.
  - If `nums[i] >= nums[i+1]`, return `false`.
  - After the loop, return `true`.
- In the main function, get the length of the array, `n`.
- Loop `a` from `0` to `n - 2*k`.
- Check if `isIncreasing(nums, a, k)` is true.
- Check if `isIncreasing(nums, a + k, k)` is true.
- If both are true, return `true`.
- If the loop completes, return `false`.

## Linear Time Solution using Pre-computation
This approach improves upon the brute-force method by avoiding redundant computations. We first pre-compute information about all increasing subarrays in a single pass. Then, we use this pre-computed data to check the condition in constant time for each possible starting position.
**Time:** O(n). The first loop to populate the `dp` array takes `O(n)`. The second loop to check for the condition also takes `O(n)`. The total time complexity is `O(n) + O(n) = O(n)`. · **Space:** O(n). We use an additional array `dp` of size `n` to store the lengths of increasing subarrays.
**Pros:** Optimal time complexity, making it very efficient for all valid inputs.; The pre-computation logic is reusable for other problems involving properties of contiguous subarrays.
**Cons:** Uses extra space proportional to the input size, which might be a concern for very large inputs.
### Explanation
The core idea is to determine, for each index `i`, the length of the strictly increasing subarray that ends at `i`. We can store these lengths in an array, let's call it `dp`.

`dp[i]` is calculated as follows:
- `dp[0] = 1`.
- For `i > 0`, if `nums[i] > nums[i-1]`, the increasing sequence continues, so `dp[i] = dp[i-1] + 1`.
- Otherwise, a new increasing sequence starts, so `dp[i] = 1`.

This `dp` array can be computed in `O(n)` time.

With the `dp` array, we can check if a subarray of length `k` starting at index `a` is increasing in `O(1)` time. The subarray `nums[a..a+k-1]` is strictly increasing if and only if the length of the increasing subarray ending at `a+k-1` is at least `k`. That is, `dp[a+k-1] >= k`.

Now, we can iterate through all possible starting indices `a` from `0` to `n - 2k`. For each `a`, we check two conditions:
1. Is the first subarray `nums[a..a+k-1]` increasing? This is true if `dp[a+k-1] >= k`.
2. Is the second subarray `nums[a+k..a+2k-1]` increasing? This is true if `dp[a+2k-1] >= k`.

If both conditions are met for any `a`, we return `true`. If the loop finishes, we return `false`.

```java
class Solution {
    public boolean solve(int[] nums, int k) {
        int n = nums.length;
        if (2 * k > n) {
            return false;
        }

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

        // Check for two adjacent increasing subarrays of length k
        for (int a = 0; a <= n - 2 * k; a++) {
            // Check first subarray: nums[a...a+k-1]
            boolean firstIsIncreasing = (dp[a + k - 1] >= k);
            // Check second subarray: nums[a+k...a+2k-1]
            boolean secondIsIncreasing = (dp[a + 2 * k - 1] >= k);

            if (firstIsIncreasing && secondIsIncreasing) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Get the length of the array, `n`. If `2*k > n`, return `false`.
- Create an integer array `dp` of size `n`.
- Initialize `dp[0] = 1`.
- Loop `i` from `1` to `n-1`:
  - If `nums[i] > nums[i-1]`, set `dp[i] = dp[i-1] + 1`.
  - Else, set `dp[i] = 1`.
- Loop `a` from `0` to `n - 2*k`:
  - Check if `dp[a + k - 1] >= k`.
  - Check if `dp[a + 2*k - 1] >= k`.
  - If both are true, return `true`.
- If the loop completes, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
    int mx = 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)) {
        mx = Math.max(mx, Math.max(cur / 2, Math.min(pre, cur)));
        pre = cur;
        cur = 0;
      }
    }
    return mx >= k;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool hasIncreasingSubarrays(vector<int> &nums, int k) {
    int mx = 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]) {
        mx = max({mx, cur / 2, min(pre, cur)});
        pre = cur;
        cur = 0;
      }
    }
    return mx >= k;
  }
};

```

### Python

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

```