2025-10-15 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 15

Description

Adjacent Increasing Subarrays Detection II

Given an array nums of n integers, your task is to find the maximum value of k for which there exist two adjacent subarrays of length k each, such that both subarrays are strictly increasing. Specifically, check if there are two subarrays of length k 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 the maximum possible value of k.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

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

Output: 3

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, and 3 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

Example 2:

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

Output: 2

Explanation:

  • The subarray starting at index 0 is [1, 2], which is strictly increasing.
  • The subarray starting at index 2 is [3, 4], which is also strictly increasing.
  • These two subarrays are adjacent, and 2 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

 

Constraints:

  • 2 <= nums.length <= 2 * 105
  • -109 <= nums[i] <= 109

Solution

class Solution {
  bool isOk(map<int, int> &increasing, int k) {
    for(auto [start, size] : increasing) {
      if(size >= 2 * k) return true;
      if(size < k) continue;
      if(increasing.count(start + size) && increasing[start + size] >= k) return true;
    }
    return false;
  }
public:
  int maxIncreasingSubarrays(vector<int>& nums) {
    map<int, int> increasing;
    int start = 0;
    int size = 1;
    int len = nums.size();
    for(int i = 1; i < len; ++i) {
      if(nums[i] > nums[i - 1]) {
        size += 1;
        continue;
      }
      increasing[start] = size;
      start = i;
      size = 1;
    }
    increasing[start] = size;
    int low = 1;
    int high = 1;
    for(auto [_start, size] : increasing) {
      if(size > high) high = size;
    }
    while(low < high) {
      int mid = (low + high + 1) / 2;
      if(isOk(increasing, mid)) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
    return low;
  }
};

// Accepted
// 1111/1111 cases passed (354 ms)
// Your runtime beats 5.54 % of cpp submissions
// Your memory usage beats 8.4 % of cpp submissions (204.9 MB)
Algorithm