Adjacent Increasing Subarrays Detection I Solution in C++

Problem Description

So, you think you can just stroll through an array of numbers and find increasing subarrays like it’s a walk in the park? Well, think again! The problem at hand is to determine if there exists a subarray of length at least k where the elements are strictly increasing. Imagine you’re at a party, and you’re trying to find a group of friends who are all taller than you. If you can find at least k friends who are taller than you in a row, you’re golden!

In technical terms, given an array of integers nums and an integer k, you need to check if there’s a contiguous subarray of length at least k where each element is greater than the previous one.

Code Solution


class Solution {
 public:
  bool hasIncreasingSubarrays(vector& nums, int k) {
    int increasing = 1;
    int prevIncreasing = 0;

    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] > nums[i - 1]) {
        ++increasing;
      } else {
        prevIncreasing = increasing;
        increasing = 1;
      }
      if (increasing / 2 >= k || min(prevIncreasing, increasing) >= k)
        return true;
    }

    return false;
  }
};

Approach

The approach here is as straightforward as it gets. We traverse through the array while keeping track of the length of the current increasing sequence. If we find a number that is greater than the previous one, we increment our count. If we hit a number that isn’t greater, we check if the length of the increasing sequence (or the previous one) is at least k. If it is, we return true. If we finish traversing the array without finding such a sequence, we return false.

Time and Space Complexity

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

Real-World Example

Imagine you’re at a concert, and you’re trying to find a group of friends who are all taller than you to stand with. If you can find at least k friends in a row who are taller, you can finally see the stage! This problem is akin to that scenario, where you’re trying to find a sequence of increasing heights (or numbers) in an array.