2302. Count-Subarrays-With-Score-Less-Than-K

This one was a hard question but boy did it feel good to solve. The comments are lowkey goated on this one so I will let them do the job!

(Maybe I’ll come back and explain the process more in depth later)

class Solution(object):
    def countSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # everytime u add, you double the curr sum and add new_length * i
        # sliding window
        # 2 1 4 3 5
        #       l
        #       r

        # note: length of curr = r - l + 1
        # curr 3
        # curr_sum 4
        # total 2 (r - l)

        # update r until curr is more than/equal to k
        # -> curr += curr_sum + (new_length * r)
        # update l when r is this
        # -> curr -= (curr_sum + (new_length * l))

        # 9.16s to whiteboard
        r = -1
        res = 0
        curr = 0
        curr_sum = 0
        for l in range(len(nums)):
            while r < len(nums) and curr < k:
                r += 1
                if r < len(nums):
                    curr += curr_sum + (r - l + 1) * nums[r]
                    curr_sum += nums[r]

            res += r - l
            curr -= (curr_sum + (r - l) * nums[l])
            curr_sum -= nums[l]

        return res

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 36m 9s