Adjacent Increasing Subarrays Detection I

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.

Examples

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

Solution

Method 1 - Linear scan using increase-run lengths

Intuition

Instead of checking every k-length subarray explicitly (which can be O(n*k)), compute for each index the length of the consecutive increasing run starting at that index. A subarray of length k starting at i is strictly increasing iff incLen[i] >= k-1. So compute incLen in one pass (from right to left) and then check adjacent starts i and i+k in another pass — overall O(n).

Approach

1. Let n = len(nums). If 2*k > n, return false immediately (by constraints this won't happen).
2. Create an array incLen of length n filled with 0. For i from n-2 down to 0: if nums[i] < nums[i+1] then incLen[i] = incLen[i+1] + 1 else incLen[i] = 0.
3. A subarray of length k starting at i is strictly increasing iff incLen[i] >= k-1.
4. Iterate i from 0 to n - 2*k (inclusive). If incLen[i] >= k-1 and incLen[i+k] >= k-1, return true.
5. If no such pair is found, return false.

Complexity

• ⏰ Time complexity: O(n) – We compute incLen in a single pass and then scan possible starts once.
• 🧺 Space complexity: O(n) – We store the incLen array of length n.

Code

C++

#include <vector>
using std::vector;

class Solution {
public:
    bool hasIncreasingSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        if (2 * k > n) return false;
        vector<int> incLen(n, 0);
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) incLen[i] = incLen[i + 1] + 1;
            else incLen[i] = 0;
        }
        for (int i = 0; i <= n - 2 * k; ++i) {
            if (incLen[i] >= k - 1 && incLen[i + k] >= k - 1) return true;
        }
        return false;
    }
};

Go

package solution

type Solution struct{}

func (s *Solution) hasIncreasingSubarrays(nums []int, k int) bool {
    n := len(nums)
    if 2*k > n { return false }
    incLen := make([]int, n)
    for i := n-2; i >= 0; i-- {
        if nums[i] < nums[i+1] { incLen[i] = incLen[i+1] + 1 } else { incLen[i] = 0 }
    }
    for i := 0; i <= n-2*k; i++ {
        if incLen[i] >= k-1 && incLen[i+k] >= k-1 { return true }
    }
    return false
}

Java

class Solution {
    public boolean hasIncreasingSubarrays(List<Integer> nums, int k) {
        int n = nums.size();
        if (2 * k > n) return false;
        int[] incLen = new int[n];
        for (int i = n - 2; i >= 0; --i) {
            if (nums.get(i) < nums.get(i + 1)) incLen[i] = incLen[i + 1] + 1;
            else incLen[i] = 0;
        }
        for (int i = 0; i <= n - 2 * k; ++i) {
            if (incLen[i] >= k - 1 && incLen[i + k] >= k - 1) return true;
        }
        return false;
    }
}

Kotlin

class Solution {
    fun hasIncreasingSubarrays(nums: List<Int>, k: Int): Boolean {
        val n = nums.size
        if (2 * k > n) return false
        val incLen = IntArray(n)
        for (i in n - 2 downTo 0) {
            incLen[i] = if (nums[i] < nums[i + 1]) incLen[i + 1] + 1 else 0
        }
        for (i in 0..(n - 2 * k)) {
            if (incLen[i] >= k - 1 && incLen[i + k] >= k - 1) return true
        }
        return false
    }
}

Python

class Solution:
    def hasIncreasingSubarrays(self, nums: list[int], k: int) -> bool:
        n = len(nums)
        if 2 * k > n:
            return False
        inc_len = [0] * n
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                inc_len[i] = inc_len[i + 1] + 1
            else:
                inc_len[i] = 0
        for i in range(0, n - 2 * k + 1):
            if inc_len[i] >= k - 1 and inc_len[i + k] >= k - 1:
                return True
        return False

Rust

pub struct Solution;

impl Solution {
    pub fn hasIncreasingSubarrays(&self, nums: Vec<i32>, k: usize) -> bool {
        let n = nums.len();
        if 2 * k > n { return false; }
        let mut inc_len = vec![0usize; n];
        for i in (0..n-1).rev() {
            if nums[i] < nums[i+1] { inc_len[i] = inc_len[i+1] + 1 } else { inc_len[i] = 0 }
        }
        for i in 0..=n - 2 * k {
            if inc_len[i] >= k - 1 && inc_len[i + k] >= k - 1 { return true }
        }
        false
    }
}

Typescript

class Solution {
    hasIncreasingSubarrays(nums: number[], k: number): boolean {
        const n = nums.length;
        if (2 * k > n) return false;
        const incLen = new Array<number>(n).fill(0);
        for (let i = n - 2; i >= 0; --i) {
            incLen[i] = nums[i] < nums[i + 1] ? incLen[i + 1] + 1 : 0;
        }
        for (let i = 0; i <= n - 2 * k; ++i) {
            if (incLen[i] >= k - 1 && incLen[i + k] >= k - 1) return true;
        }
        return false;
    }
}