Adjacent Increasing Subarrays Detection I

Easy
1845.

Adjacent Increasing Subarrays Detection I

Adjacent Increasing Subarrays Detection I is an easy coding problem on arrays, asked in Amazon and Google interviews.

Given an array nums and an integer k, decide whether there are two adjacent subarrays of length k that are both strictly increasing.

Formally, return true if some index a exists such that nums[a..a + k - 1] and nums[a + k..a + 2k - 1] are both strictly increasing, and false otherwise. The second subarray starts right where the first one ends.

Example 1

Input
nums = [2,5,7,8,9,2,3,4,3,1], k = 3
Output
true
Explanation
[7,8,9] starts at index 2 and [2,3,4] starts at index 5 — both strictly increasing and back to back.

Example 2

Input
nums = [1,2,3,4,4,4,4,5,6,7], k = 5
Output
false
Explanation
The repeated 4s break every run, and no run is long enough.

Example 3

Input
nums = [-3,-2], k = 1
Output
true
Explanation
Every single element is a strictly increasing subarray of length 1.

Constraints

  • 2 <= nums.length <= 100
  • 1 < 2 * k <= nums.length
  • -1000 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var hasIncreasingSubarrays = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Adjacent Increasing Subarrays Detection I — Solution

Adjacent Increasing Subarrays Detection I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Adjacent Increasing Subarrays Detection I is an easy coding problem on arrays, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array nums and an integer k, decide whether there are two adjacent subarrays of length k that are both strictly increasing.

Formally, return true if some index a exists such that nums[a..a + k - 1] and nums[a + k..a + 2k - 1] are both strictly increasing, and false otherwise. The second subarray starts right where the first one ends.

Example 1

Input: nums = [2,5,7,8,9,2,3,4,3,1], k = 3
Output: true
Explanation: [7,8,9] starts at index 2 and [2,3,4] starts at index 5 — both strictly increasing and back to back.

Example 2

Input: nums = [1,2,3,4,4,4,4,5,6,7], k = 5
Output: false
Explanation: The repeated 4s break every run, and no run is long enough.

Example 3

Input: nums = [-3,-2], k = 1
Output: true
Explanation: Every single element is a strictly increasing subarray of length 1.

Constraints

  • 2 <= nums.length <= 100
  • 1 < 2 * k <= nums.length
  • -1000 <= nums[i] <= 1000

Hints for Adjacent Increasing Subarrays Detection I

  1. Hint 1

    Break the array into maximal strictly increasing runs. Where can the two subarrays live?

  2. Hint 2

    Either both fit inside one run (it has length at least 2k), or the first ends a run and the second starts the next run.

  3. Hint 3

    Walking left to right with the length of the previous run prev and the current run cur, the best k is max(cur / 2, min(prev, cur)) — check it against k.

How to solve Adjacent Increasing Subarrays Detection I

Two back-to-back strictly increasing windows of length k either sit inside one maximal increasing run of length >= 2k, or straddle the boundary between two consecutive runs, each long enough on its side. Tracking the previous and current run lengths covers both cases in one pass.

Approach

  1. Keep prev = 0 (length of the previous run) and cur = 1 (length of the run ending here), and best = 0.
  2. For each i >= 1: if nums[i] > nums[i - 1] then cur += 1; otherwise prev = cur and cur = 1.
  3. After each step set best = max(best, cur / 2, min(prev, cur)) (integer division).
  4. Also apply the update once for the first element, then return best >= k.

Why it works

If both windows lie in one run of length L, any k <= L / 2 works. If they do not, the boundary between them must coincide with a break between two runs — otherwise the windows would lie in one run — and then the first window is a suffix of the earlier run and the second a prefix of the later one, so k <= min(prev, cur). Every pair of consecutive runs is seen with cur reaching its full length, so the maximum is found.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Strictly increasing: equal neighbours end a run.
  • Do not forget the case where both windows come from one long run (cur / 2).

Reference solution

Python

from typing import List

def hasIncreasingSubarrays(nums: List[int], k: int) -> bool:
    prev, cur, best = 0, 1, 0
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            cur += 1
        else:
            prev, cur = cur, 1
        best = max(best, cur // 2, min(prev, cur))
    return best >= k

Java

public static boolean hasIncreasingSubarrays(int[] nums, int k) {
    int prev = 0, cur = 1, best = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) cur++;
        else { prev = cur; cur = 1; }
        best = Math.max(best, Math.max(cur / 2, Math.min(prev, cur)));
    }
    return best >= k;
}

C++

bool hasIncreasingSubarrays(vector<int>& nums, int k) {
    int prev = 0, cur = 1, best = 0;
    for (size_t i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) cur++;
        else { prev = cur; cur = 1; }
        best = max(best, max(cur / 2, min(prev, cur)));
    }
    return best >= k;
}

JavaScript

var hasIncreasingSubarrays = function(nums, k) {
    var prev = 0, cur = 1, best = 0;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) cur++;
        else { prev = cur; cur = 1; }
        best = Math.max(best, Math.floor(cur / 2), Math.min(prev, cur));
    }
    return best >= k;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays