Count Subarrays With Fixed Bounds - LeetCode Daily Challenge

Problem Statement

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.

Try here before watching the video.

Prerequisite Video 1

Prerequisite Video 2

Video Solution

Java Code

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long subarrays = 0;
        int minIndex = -1, maxIndex = -1, outBoundIndex = -1;

        for(int end = 0; end < nums.length; end++) {
            if(nums[end] == minK) {
                minIndex = end;
            }

            if(nums[end] == maxK) {
                maxIndex = end;
            }

            if(nums[end] < minK || nums[end] > maxK) {
                outBoundIndex = end;
            }

            subarrays += Math.max(0, (Math.min(minIndex, maxIndex) - outBoundIndex));
        }

        return subarrays;
    }
}

C++ Code

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long subarrays = 0;
        int minIndex = -1, maxIndex = -1, outBoundIndex = -1;

        for(int end = 0; end < nums.size(); end++) {
            if(nums[end] == minK) {
                minIndex = end;
            }

            if(nums[end] == maxK) {
                maxIndex = end;
            }

            if(nums[end] < minK || nums[end] > maxK) {
                outBoundIndex = end;
            }

            subarrays += max(0, min(minIndex, maxIndex) - outBoundIndex);
        }

        return subarrays;
    }
};

Python Code

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        subarrays = 0
        minIndex = maxIndex = outBoundIndex = -1

        for end in range(len(nums)):
            if nums[end] == minK:
                minIndex = end

            if nums[end] == maxK:
                maxIndex = end

            if nums[end] < minK or nums[end] > maxK:
                outBoundIndex = end

            subarrays += max(0, min(minIndex, maxIndex) - outBoundIndex)

        return subarrays

Javascript Code

var countSubarrays = function(nums, minK, maxK) {
    let subarrays = 0;
    let minIndex = maxIndex = outBoundIndex = -1;

    for (let end = 0; end < nums.length; end++) {
        if (nums[end] === minK) {
            minIndex = end;
        }

        if (nums[end] === maxK) {
            maxIndex = end;
        }

        if (nums[end] < minK || nums[end] > maxK) {
            outBoundIndex = end;
        }

        subarrays += Math.max(0, Math.min(minIndex, maxIndex) - outBoundIndex);
    }

    return subarrays;
};

Go Code

func countSubarrays(nums []int, minK int, maxK int) int64 {
    var subarrays int64 = 0
    minIndex, maxIndex, outBoundIndex := -1, -1, -1

    for end := 0; end < len(nums); end++ {
        if nums[end] == minK {
            minIndex = end
        }

        if nums[end] == maxK {
            maxIndex = end
        }

        if nums[end] < minK || nums[end] > maxK {
            outBoundIndex = end
        }

        subarrays += int64(math.Max(0, float64(min(minIndex, maxIndex)-outBoundIndex)))
    }

    return subarrays
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Complexity Analysis

Time Complexity: O(N), where N is the number of elements in array nums. This is because we are iterating the entire array only once.
Space Complexity: O(1), we are not taking any extra space.