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

March LeetCoding Challenge 4

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
// 51/51 cases passed (107 ms)
// Your runtime beats 92.65 % of cpp submissions
// Your memory usage beats 90.2 % of cpp submissions (70.4 MB)