LeetCode 3349 - Adjacent Increasing Subarrays Detection I

The problem gives us an integer array nums and an integer k. We need to determine whether the array contains two adjacent subarrays, each of length k, such that both subarrays are strictly increasing.

leetcodeeasyarray

LeetCode Problem 3349

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem gives us an integer array nums and an integer k. We need to determine whether the array contains two adjacent subarrays, each of length k, such that both subarrays are strictly increasing.

A subarray is strictly increasing if every element is larger than the one before it. For example, [2, 5, 7] is strictly increasing because 2 < 5 and 5 < 7. However, [1, 3, 3] is not strictly increasing because 3 is not less than 3.

The two subarrays must also be adjacent. If the first subarray starts at index a, then the second subarray must start exactly at index a + k. This means the two subarrays sit directly next to each other without overlapping and without gaps.

For example, if k = 3 and the first subarray starts at index 2, then it covers indices [2, 3, 4]. The second subarray must start at index 5 and cover indices [5, 6, 7].

The input constraints are small:

  • 2 <= nums.length <= 100
  • 1 < 2 * k <= nums.length

The array length is at most 100, so even a quadratic solution would work comfortably. However, the problem is still designed to test careful reasoning about subarrays and increasing sequences.

An important observation is that a strictly increasing subarray of length k requires exactly k - 1 consecutive increasing comparisons. For example:

  • [1, 2, 3, 4] is increasing because:

  • 1 < 2

  • 2 < 3

  • 3 < 4

Some edge cases are important to consider:

  • Arrays containing equal values, since equality breaks strict increasing order.
  • Cases where only one of the two adjacent subarrays is increasing.
  • The minimum valid array size, where 2 * k == n.
  • Situations where increasing runs overlap, but the required adjacent partition does not work.
  • Negative values, since comparisons must still behave correctly.

The problem guarantees that 2 * k <= nums.length, so there is always enough room for two adjacent subarrays of length k.

Approaches

Brute Force Approach

The most direct solution is to try every possible starting index for the first subarray.

Suppose the first subarray starts at index start. Then:

  • The first subarray is nums[start : start + k]
  • The second adjacent subarray is nums[start + k : start + 2 * k]

For each candidate pair, we check whether both subarrays are strictly increasing.

To verify a subarray of length k, we compare each adjacent pair inside it. If every comparison satisfies nums[i] < nums[i + 1], then the subarray is strictly increasing.

This approach is correct because it explicitly tests every valid adjacent pair of subarrays.

The time complexity is:

  • There are O(n) possible starting positions.
  • Each check examines up to k elements for each subarray.

So the total complexity is O(n * k).

Since n <= 100, this is already fast enough.

Optimal Approach

We can improve the implementation by precomputing information about increasing runs.

The key observation is that for every index i, we can compute the length of the strictly increasing sequence starting at i.

For example, in:

[2, 5, 7, 8, 1]

The increasing lengths are:

[4, 3, 2, 1, 1]

This means:

  • Starting at index 0, we can form an increasing sequence of length 4
  • Starting at index 1, length 3
  • Starting at index 2, length 2

Once we know these lengths, checking whether a subarray of length k is strictly increasing becomes very easy:

increasingLength[i] >= k

Then for every possible starting index start, we only need to verify:

increasingLength[start] >= k
and
increasingLength[start + k] >= k

This reduces repeated work and makes the solution cleaner.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * k) O(1) Explicitly checks every pair of adjacent subarrays
Optimal O(n) O(n) Precomputes increasing run lengths for fast validation

Algorithm Walkthrough

  1. Create an array called increasingLength with the same size as nums.
  2. Initialize the last position with value 1, because a single element is always an increasing sequence of length 1.
  3. Traverse the array from right to left.
  4. For each index i, compare nums[i] and nums[i + 1].
  5. If nums[i] < nums[i + 1], then the increasing sequence continues, so:
increasingLength[i] = increasingLength[i + 1] + 1
  1. Otherwise, the increasing sequence breaks, so:
increasingLength[i] = 1
  1. After preprocessing, iterate through all valid starting positions for the first subarray.
  2. For each start, check:
  • Whether the first subarray is increasing:
increasingLength[start] >= k
  • Whether the second adjacent subarray is increasing:
increasingLength[start + k] >= k
  1. If both conditions are true, return True.
  2. If no valid pair exists after checking all positions, return False.

Why it works

The preprocessing step correctly computes the maximum strictly increasing run beginning at every index. A subarray of length k is strictly increasing if and only if the increasing run starting there has length at least k.

By checking both start and start + k, we guarantee that the two subarrays are adjacent and independently strictly increasing. Since every valid starting position is examined, the algorithm cannot miss a correct answer.

Python Solution

from typing import List

class Solution:
    def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        # increasing_length[i] represents the length of the
        # strictly increasing sequence starting at index i
        increasing_length = [1] * n

        # Build increasing lengths from right to left
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                increasing_length[i] = increasing_length[i + 1] + 1

        # Check every possible adjacent pair of subarrays
        for start in range(n - 2 * k + 1):
            if (
                increasing_length[start] >= k
                and increasing_length[start + k] >= k
            ):
                return True

        return False

The implementation begins by creating the increasing_length array. Every position starts with value 1 because a single element always forms an increasing sequence of length 1.

The loop that runs from right to left builds the increasing run lengths dynamically. If the current element is smaller than the next one, the increasing run can be extended. Otherwise, the run resets to length 1.

After preprocessing, the second loop checks every valid starting position for two adjacent subarrays of length k. Instead of repeatedly scanning subarrays, the algorithm simply checks whether the precomputed increasing lengths are large enough.

As soon as a valid pair is found, the function returns True. If no valid pair exists, it returns False.

Go Solution

func hasIncreasingSubarrays(nums []int, k int) bool {
	n := len(nums)

	// increasingLength[i] stores the length of the
	// strictly increasing sequence starting at index i
	increasingLength := make([]int, n)

	for i := 0; i < n; i++ {
		increasingLength[i] = 1
	}

	// Build increasing lengths from right to left
	for i := n - 2; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			increasingLength[i] = increasingLength[i+1] + 1
		}
	}

	// Check every possible adjacent pair
	for start := 0; start <= n-2*k; start++ {
		if increasingLength[start] >= k &&
			increasingLength[start+k] >= k {
			return true
		}
	}

	return false
}

The Go implementation follows exactly the same logic as the Python solution.

One difference is that Go requires explicit slice allocation using make. The increasingLength slice is initialized with size n, and each position is manually assigned value 1.

Go slices naturally handle dynamic indexing similarly to Python lists. Integer overflow is not a concern here because the maximum array length is only 100.

Worked Examples

Example 1

nums = [2,5,7,8,9,2,3,4,3,1]
k = 3

First, compute increasing_length.

Index Value increasing_length
9 1 1
8 3 1
7 4 1
6 3 2
5 2 3
4 9 1
3 8 2
2 7 3
1 5 4
0 2 5

Final array:

[5,4,3,2,1,3,2,1,1,1]

Now check possible starting positions.

start First Run Length Second Run Length Valid
0 5 2 No
1 4 1 No
2 3 3 Yes

At start = 2:

  • First subarray: [7,8,9]
  • Second subarray: [2,3,4]

Both are strictly increasing, so the answer is True.

Example 2

nums = [1,2,3,4,4,4,4,5,6,7]
k = 5

Compute increasing_length.

Index Value increasing_length
9 7 1
8 6 2
7 5 3
6 4 4
5 4 1
4 4 1
3 4 1
2 3 2
1 2 3
0 1 4

Final array:

[4,3,2,1,1,1,4,3,2,1]

Possible starting positions:

start First Run Length Second Run Length Valid
0 4 1 No

No valid adjacent pair exists, so the answer is False.

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to build increasing lengths and one pass to check candidates
Space O(n) Stores the increasing length array

The preprocessing loop visits each element exactly once, and the validation loop also scans the array once. Since both operations are linear, the total time complexity is O(n).

The additional array increasing_length requires O(n) extra memory.

Test Cases

from typing import List

class Solution:
    def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        increasing_length = [1] * n

        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                increasing_length[i] = increasing_length[i + 1] + 1

        for start in range(n - 2 * k + 1):
            if (
                increasing_length[start] >= k
                and increasing_length[start + k] >= k
            ):
                return True

        return False

sol = Solution()

assert sol.hasIncreasingSubarrays(
    [2,5,7,8,9,2,3,4,3,1], 3
) == True  # provided example with valid adjacent runs

assert sol.hasIncreasingSubarrays(
    [1,2,3,4,4,4,4,5,6,7], 5
) == False  # provided example with equality breaking increase

assert sol.hasIncreasingSubarrays(
    [1,2,3,4], 2
) == True  # minimum two adjacent increasing subarrays

assert sol.hasIncreasingSubarrays(
    [1,1,1,1], 2
) == False  # all equal values

assert sol.hasIncreasingSubarrays(
    [1,2,1,2], 2
) == True  # both adjacent subarrays increasing

assert sol.hasIncreasingSubarrays(
    [5,4,3,2,1], 2
) == False  # strictly decreasing array

assert sol.hasIncreasingSubarrays(
    [-5,-4,-3,-2,-1,0], 3
) == True  # negative values still increasing

assert sol.hasIncreasingSubarrays(
    [1,2,3,1,2,3], 3
) == True  # exactly two adjacent increasing blocks

assert sol.hasIncreasingSubarrays(
    [1,2,3,4,5,6], 3
) == True  # long increasing run contains adjacent blocks

assert sol.hasIncreasingSubarrays(
    [1,2,3,2,3,4], 3
) == True  # two separate increasing subarrays

assert sol.hasIncreasingSubarrays(
    [1,2,2,3,4,5], 3
) == False  # equality breaks first candidate
Test Why
[2,5,7,8,9,2,3,4,3,1], k=3 Validates the provided positive example
[1,2,3,4,4,4,4,5,6,7], k=5 Validates the provided negative example
[1,2,3,4], k=2 Tests smallest valid successful case
[1,1,1,1], k=2 Ensures equality breaks strict increase
[1,2,1,2], k=2 Tests short adjacent increasing pairs
[5,4,3,2,1], k=2 Tests fully decreasing input
[-5,-4,-3,-2,-1,0], k=3 Verifies handling of negative values
[1,2,3,1,2,3], k=3 Tests exact adjacent partition
[1,2,3,4,5,6], k=3 Tests continuous long increasing run
[1,2,3,2,3,4], k=3 Tests separated increasing regions
[1,2,2,3,4,5], k=3 Ensures duplicate values invalidate a run

Edge Cases

One important edge case occurs when the array contains duplicate values. Since the condition requires strictly increasing order, equal adjacent values immediately invalidate a subarray. For example, [1,2,2,3] is not strictly increasing because 2 < 2 is false. The implementation handles this correctly because it only extends an increasing run when nums[i] < nums[i + 1].

Another important case is when the array length is exactly 2 * k. In this situation, there is only one possible pair of adjacent subarrays to check. A buggy implementation might accidentally skip this case due to incorrect loop bounds. The solution correctly iterates with:

range(n - 2 * k + 1)

which includes the single valid starting position.

A third edge case is a fully increasing array such as [1,2,3,4,5,6] with k = 3. Even though the array forms one long increasing sequence, the problem only requires two adjacent increasing subarrays, which are still present. The preprocessing approach naturally handles this because long increasing runs produce large values in increasing_length.

Another subtle case involves decreasing or partially decreasing arrays. For example, [5,4,3,2,1] contains no increasing subarrays of length greater than 1. The preprocessing array becomes entirely filled with 1s, so all candidate checks fail correctly.

Finally, negative numbers can sometimes expose comparison bugs if implementations incorrectly assume positivity. Since the algorithm only relies on relative comparisons using <, it works correctly regardless of whether values are positive, negative, or mixed.