Skip to content

3349. Adjacent Increasing Subarrays Detection I

Description

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

Solutions

Solution 1: Single Pass

According to the problem description, we only need to find the maximum length of adjacent increasing subarrays \(\textit{mx}\). If \(\textit{mx} \ge k\), then there exist two adjacent strictly increasing subarrays of length \(k\).

We can use a single pass to calculate \(\textit{mx}\). Specifically, we maintain three variables: \(\textit{cur}\) and \(\textit{pre}\) represent the length of the current increasing subarray and the previous increasing subarray respectively, while \(\textit{mx}\) represents the maximum length of adjacent increasing subarrays.

Whenever we encounter a non-increasing position, we update \(\textit{mx}\), assign \(\textit{cur}\) to \(\textit{pre}\), and reset \(\textit{cur}\) to \(0\). The update formula for \(\textit{mx}\) is \(\textit{mx} = \max(\textit{mx}, \lfloor \frac{\textit{cur}}{2} \rfloor, \min(\textit{pre}, \textit{cur}))\), meaning the adjacent increasing subarrays come from either half the length of the current increasing subarray, or the smaller value between the previous increasing subarray and the current increasing subarray.

Finally, we just need to check whether \(\textit{mx}\) is greater than or equal to \(k\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func hasIncreasingSubarrays(nums []int, k int) bool {
    mx, pre, cur := 0, 0, 0
    for i, x := range nums {
        cur++
        if i == len(nums)-1 || x >= nums[i+1] {
            mx = max(mx, max(cur/2, min(pre, cur)))
            pre, cur = cur, 0
        }
    }
    return mx >= k
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function hasIncreasingSubarrays(nums: number[], k: number): boolean {
    let [mx, pre, cur] = [0, 0, 0];
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        ++cur;
        if (i === n - 1 || nums[i] >= nums[i + 1]) {
            mx = Math.max(mx, (cur / 2) | 0, Math.min(pre, cur));
            [pre, cur] = [cur, 0];
        }
    }
    return mx >= k;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn has_increasing_subarrays(nums: Vec<i32>, k: i32) -> bool {
        let n = nums.len();
        let (mut mx, mut pre, mut cur) = (0, 0, 0);

        for i in 0..n {
            cur += 1;
            if i == n - 1 || nums[i] >= nums[i + 1] {
                mx = mx.max(cur / 2).max(pre.min(cur));
                pre = cur;
                cur = 0;
            }
        }

        mx >= k
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var hasIncreasingSubarrays = function (nums, k) {
    const n = nums.length;
    let [mx, pre, cur] = [0, 0, 0];
    for (let i = 0; i < n; ++i) {
        ++cur;
        if (i === n - 1 || nums[i] >= nums[i + 1]) {
            mx = Math.max(mx, cur >> 1, Math.min(pre, cur));
            pre = cur;
            cur = 0;
        }
    }
    return mx >= k;
};

Comments