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

April LeetCoding Challenge 26

Description

Count Subarrays With Fixed Bounds

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

• The minimum value in the subarray is equal to minK.
• The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Example 2:

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i], minK, maxK <= 106

Solution

class Solution {
public:
  long long countSubarrays(vector<int>& nums, int minK, int maxK) {
    long long answer = 0;
    int lastInvalid = -1;
    int prevMinKIndex = -1;
    int prevMaxKIndex = -1;

    for(int i = 0; i < nums.size(); ++i) {
      if(nums[i] < minK || nums[i] > maxK) {
        lastInvalid = i;
      }
      if (nums[i] == minK) {
        prevMinKIndex = i;
      }
      if (nums[i] == maxK) {
        prevMaxKIndex = i;
      }

      answer += max(0, min(prevMinKIndex, prevMaxKIndex) - lastInvalid);
    }

    return answer;
  }
};

// Accepted
// 53/53 cases passed (4 ms)
// Your runtime beats 38.42 % of cpp submissions
// Your memory usage beats 31.29 % of cpp submissions (94 MB)