Adjacent Increasing Subarrays Detection I
EasyPrompt
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]andnums[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
2is[7, 8, 9], which is strictly increasing. - The subarray starting at index
5is[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 <= 1001 < 2 * k <= nums.length-1000 <= nums[i] <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a helper function
isIncreasing(nums, start, k):- Loop
ifromstarttostart + k - 2. - If
nums[i] >= nums[i+1], returnfalse. - After the loop, return
true.
- Loop
- In the main function, get the length of the array,
n. - Loop
afrom0ton - 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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
Pros
Simple to understand and implement.
Low memory usage.
Cons
Can be inefficient for large
nandk, as it performs redundant comparisons for overlapping parts of subarrays in consecutive iterations.
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.
Algorithm
- Get the length of the array,
n. If2*k > n, returnfalse. - Create an integer array
dpof sizen. - Initialize
dp[0] = 1. - Loop
ifrom1ton-1:- If
nums[i] > nums[i-1], setdp[i] = dp[i-1] + 1. - Else, set
dp[i] = 1.
- If
- Loop
afrom0ton - 2*k:- Check if
dp[a + k - 1] >= k. - Check if
dp[a + 2*k - 1] >= k. - If both are true, return
true.
- Check if
- If the loop completes, return
false.
Walkthrough
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, ifnums[i] > nums[i-1], the increasing sequence continues, sodp[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:
- Is the first subarray
nums[a..a+k-1]increasing? This is true ifdp[a+k-1] >= k. - Is the second subarray
nums[a+k..a+2k-1]increasing? This is true ifdp[a+2k-1] >= k.
If both conditions are met for any a, we return true. If the loop finishes, we return false.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 >= kVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.