Adjacent Increasing Subarrays Detection I solution and explanation
Google
9 more videos on this problem
Adjacent Increasing Subarrays Detection I | Simple and Intuitive | Leetcode 3349 | codestorywithMIKcodestorywithMIK · 26:51 · 8K views
3349 & 3350. Adjacent Increasing Subarrays Detection I & II | Binary Search | DPAryan Mittal · 16:00 · 3K views
3349. Adjacent Increasing Subarrays Detection I | Leetcode Daily - PythonLeetcode Daily · 7:12 · 958 views
3349. Adjacent Increasing Subarrays Detection I (Leetcode Easy)Programming Live with Larry · 7:03 · 423 views
Leetcode 3349 | Adjacent Increasing Subarrays Detection I | Weekly Contest 423 Solutions | CodefodCodeFod · 7:32 · 373 views
Adjacent Increasing Subarrays Detection I | LeetCode 3349 - Pythonimpoldev · 10:09 · 346 views
LeetCode Daily 3349 | Adjacent Increasing Subarrays Detection I | Easy | Solution WalkthroughDaily Dose Of LeetCode · 14:12 · 269 views
3349. Adjacent Increasing Subarrays Detection ICodeVia · 4:27 · 118 views
Leetcode 3349 Adjacent Increasing Subarrays Detection IAlgorithmicIQ · 12:11 · 60 views
Adjacent Increasing Subarrays Detection I - Leetcode 3349ThinkOutsideTheBox · 12:40 · 59 views
The 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]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
Approach overview
Problem Overview: You are given an integer array and a value k. The task is to determine whether the array contains two adjacent strictly increasing subarrays, each of length k. In other words, check if there exists an index i where nums[i..i+k-1] and nums[i+k..i+2k-1] are both strictly increasing sequences.
Approach 1: Two Pointers for Check (O(n) time, O(1) space)
This method scans the array and measures the length of strictly increasing segments using two pointers. Start from the left and expand the right pointer while nums[r] > nums[r-1]. This gives the length of a continuous increasing run. If a run length is at least 2k, or if two consecutive runs each have length at least k, you can form two adjacent increasing subarrays. The algorithm only tracks boundaries and lengths, so no extra data structures are required.
The key insight: strictly increasing subarrays must lie inside increasing runs. Instead of checking every possible pair explicitly, compute run lengths and verify whether the required adjacent segments exist.
Approach 2: Sliding Window Technique (O(n) time, O(1) space)
The sliding window approach checks windows of size k while maintaining whether each window is strictly increasing. Move a window across the array and track violations where nums[i] <= nums[i-1]. Two consecutive windows are valid if both satisfy the increasing condition and the second starts exactly after the first.
To optimize, maintain a running count of increasing comparisons inside the window. As the window slides forward, update the count instead of recomputing the entire window. This converts a naive O(nk) check into an O(n) scan while keeping constant space.
This technique is a common pattern in sliding window problems where local order constraints must be verified efficiently.
Recommended for interviews: The two‑pointer run-length scan is typically what interviewers expect. It directly models how increasing sequences behave and produces a clean O(n) solution with constant memory. A sliding window implementation also works and demonstrates familiarity with two pointers and window maintenance patterns. Showing the brute reasoning first (checking segments) and then optimizing to a single pass highlights strong problem-solving skills.
Approach 1: Using Two Pointers for Check
This approach uses a single loop and checks both subarrays simultaneously to see if they are strictly increasing. By maintaining two pointers, one for the first subarray and one for the potential adjacent subarray, we can efficiently determine if there exists any pair of strictly increasing adjacent subarrays.
def is_strictly_increasing(nums, start, k):
for i in range(start, start + k - 1):
if nums[i] >= nums[i + 1]:
return False
return True
def check_adjacent_increasing_subarrays(nums, k):
n = len(nums)
for a in range(n - 2 * k + 1):
if is_strictly_increasing(nums, a, k) and is_strictly_increasing(nums, a + k, k):
return True
return Falsepublic class Solution {
private boolean isStrictlyIncreasing(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 checkAdjacentIncreasingSubarrays(int[] nums, int k) {
int n = nums.length;
for (int a = 0; a <= n - 2 * k; a++) {
if (isStrictlyIncreasing(nums, a, k) && isStrictlyIncreasing(nums, a + k, k)) {
return true;
}
}
return false;
}
}#include <vector>
bool isStrictlyIncreasing(const std::vector<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;
}
bool checkAdjacentIncreasingSubarrays(const std::vector<int>& nums, int k) {
int n = nums.size();
for (int a = 0; a <= n - 2 * k; ++a) {
if (isStrictlyIncreasing(nums, a, k) && isStrictlyIncreasing(nums, a + k, k)) {
return true;
}
}
return false;
}function isStrictlyIncreasing(nums, start, k) {
for (let i = start; i < start + k - 1; i++) {
if (nums[i] >= nums[i + 1]) {
return false;
}
}
return true;
}
function checkAdjacentIncreasingSubarrays(nums, k) {
const n = nums.length;
for (let a = 0; a <= n - 2 * k; a++) {
if (isStrictlyIncreasing(nums, a, k) && isStrictlyIncreasing(nums, a + k, k)) {
return true;
}
}
return false;
}#include <stdbool.h>
bool isStrictlyIncreasing(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;
}
bool checkAdjacentIncreasingSubarrays(int nums[], int numsSize, int k) {
for (int a = 0; a <= numsSize - 2 * k; a++) {
if (isStrictlyIncreasing(nums, a, k) && isStrictlyIncreasing(nums, a + k, k)) {
return true;
}
}
return false;
}public class Solution {
private bool IsStrictlyIncreasing(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 bool CheckAdjacentIncreasingSubarrays(int[] nums, int k) {
int n = nums.Length;
for (int a = 0; a <= n - 2 * k; a++) {
if (IsStrictlyIncreasing(nums, a, k) && IsStrictlyIncreasing(nums, a + k, k)) {
return true;
}
}
return false;
}
}A Python function to verify strict increase over k elements from a start index, applied in a loop to find consecutive subarrays. It returns true on finding such a pair or false if none exist.
Time Complexity: O(n * k)
Space Complexity: O(1)
Approach 2: Using Sliding Window Technique
The sliding window technique can provide a more efficient approach by iterating through the array once and maintaining running comparisons. Continuously evaluate if the latest element extends an increasing pattern and reset boundaries where necessary.
def check_adjacent_increasing_subarrays(nums, k):
count = 0
for i in range(len(nums) - 1):
if nums[i] < nums[i + 1]:
count += 1
if count >= 2 * k - 1:
return True
else:
count = 0
return Falsepublic class Solution {
public boolean checkAdjacentIncreasingSubarrays(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] < nums[i + 1]) {
count++;
if (count >= 2 * k - 1) {
return true;
}
} else {
count = 0;
}
}
return false;
}
}#include <vector>
bool checkAdjacentIncreasingSubarrays(const std::vector<int>& nums, int k) {
int count = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] < nums[i + 1]) {
count++;
if (count >= 2 * k - 1) {
return true;
}
} else {
count = 0;
}
}
return false;
}function checkAdjacentIncreasingSubarrays(nums, k) {
let count = 0;
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] < nums[i + 1]) {
count++;
if (count >= 2 * k - 1) {
return true;
}
} else {
count = 0;
}
}
return false;
}#include <stdbool.h>
bool checkStrictlyIncreasing(int nums[], int start, int end) {
for (int i = start; i < end; i++) {
if (nums[i] >= nums[i + 1]) {
return false;
}
}
return true;
}
bool checkAdjacentIncreasingSubarrays(int nums[], int numsSize, int k) {
int count = 0;
for (int i = 0; i < numsSize - 1; ++i) {
if (nums[i] < nums[i + 1]) {
count++;
if (count >= k * 2 - 1) {
return true;
}
} else {
count = 0;
}
}
return false;
}public class Solution {
public bool CheckAdjacentIncreasingSubarrays(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] < nums[i + 1]) {
count++;
if (count >= 2 * k - 1) {
return true;
}
} else {
count = 0;
}
}
return false;
}
}In this Python implementation, a linear sweep counts ascending pairs and resets at each disorder. Once reaching the critical mass of rising element links, it sanctions as meeting the conditions for adjacent increasing subarrays.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Single Pass
According to the problem description, we only need to find the maximum length of adjacent increasing subarrays mx. If mx \ge k, then there exist two adjacent strictly increasing subarrays of length k.
We can use a single pass to calculate mx. Specifically, we maintain three variables: cur and pre represent the length of the current increasing subarray and the previous increasing subarray respectively, while mx represents the maximum length of adjacent increasing subarrays.
Whenever we encounter a non-increasing position, we update mx, assign cur to pre, and reset cur to 0. The update formula for mx is mx = max(mx, \lfloor \frac{cur}{2} \rfloor, min(pre, 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 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).
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;
}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
}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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Two Pointers for Check | Time Complexity: O(n * k) |
| Using Sliding Window Technique | Time Complexity: O(n) |
| Single Pass | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers (Run Length Scan) | O(n) | O(1) | Best general solution. Efficient single pass when checking increasing runs. |
| Sliding Window Technique | O(n) | O(1) | Useful when explicitly validating fixed-size windows or practicing window-based patterns. |
Frequently asked questions
Is Adjacent Increasing Subarrays Detection I easy or hard?
The problem is classified as Easy. The main challenge is recognizing that strictly increasing subarrays must lie inside larger increasing runs. Once you track those runs, checking whether two adjacent segments of length k exist becomes straightforward.
Adjacent Increasing Subarrays Detection I Python/Java solution
Python and Java implementations usually follow the same O(n) logic: iterate through the array, track the current increasing run length, and verify whether two adjacent segments of size k can be formed. The code typically uses simple loops and integer counters without extra memory.
How to solve Adjacent Increasing Subarrays Detection I in O(n)?
Scan the array and track the length of strictly increasing segments. Each time the order breaks, record the segment length and reset the counter. If a segment can contain two adjacent subarrays of size k (length >= 2k) or two consecutive segments each reach length k, return true. This avoids checking every possible subarray pair.
What is the best approach for Adjacent Increasing Subarrays Detection I?
The most efficient approach is a single-pass two-pointer scan that measures lengths of strictly increasing runs. Once the run lengths are known, you can check whether two adjacent segments of size k exist inside those runs. This runs in O(n) time with O(1) extra space and is typically the expected interview solution.
Is Adjacent Increasing Subarrays Detection I asked at Google/Amazon/Meta?
Problems involving increasing sequences, two pointers, and sliding windows frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of detecting ordered subarrays in O(n) time is a common interview theme.
What data structure is used in Adjacent Increasing Subarrays Detection I?
The problem mainly uses basic array traversal with pointer variables. No advanced data structures are required. Techniques like two pointers or a sliding window operate directly on the array while maintaining counters for increasing relationships.
What is the time complexity of Adjacent Increasing Subarrays Detection I?
The optimal time complexity is O(n), where n is the length of the array. The algorithm performs a single linear scan while checking increasing relationships between adjacent elements. Space complexity remains O(1) because only a few counters or pointers are stored.