Skip to main content
Talentd

Adjacent Increasing Subarrays Detection I - Solution & Explanation

EasyArray19 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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

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.

This function first checks if a subarray starting at the given index with length k is strictly increasing. The main function iterates through the array with initial index such a way that enough elements remain for two subarrays of length k. If at any such index both subarrays are strictly increasing, it returns true.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * k), where n is the length of the array. The two pointer approach still checks each element of both subarrays.
Space Complexity: O(1), as no additional space is used apart from a few counters.

Try this approach in the editor →

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.

The solution uses a counter that increments through every consecutive pair increase. Two adjacent subarrays need k-1 increases each plus the adjacent element, hence k*2-1 successful increments confirm the presence of two such subarrays.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Two Pointers for Check

Time Complexity: O(n * k), where n is the length of the array. The two pointer approach still checks each element of both subarrays.
Space Complexity: O(1), as no additional space is used apart from a few counters.

Using Sliding Window Technique

Time Complexity: O(n)
Space Complexity: O(1)

Single Pass—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointers (Run Length Scan)O(n)O(1)Best general solution. Efficient single pass when checking increasing runs.
Sliding Window TechniqueO(n)O(1)Useful when explicitly validating fixed-size windows or practicing window-based patterns.

Video Solution

Adjacent Increasing Subarrays Detection I | Simple and Intuitive | Leetcode 3349 | codestorywithMIK • codestorywithMIK • 8,038 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Adjacent Increasing Subarrays Detection I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays