LeetCode in Kotlin

3748. Count Stable Subarrays

Hard

You are given an integer array nums.

A non-empty subarrays of nums is called stable if it contains no inversions, i.e., there is no pair of indices i < j such that nums[i] > nums[j].

You are also given a 2D integer array queries of length q, where each queries[i] = [li, ri] represents a query. For each query [li, ri], compute the number of stable subarrays that lie entirely within the segment nums[li..ri].

Return an integer array ans of length q, where ans[i] is the answer to the ith query.

Note:

• A single element subarray is considered stable.

Example 1:

Input: nums = [3,1,2], queries = [[0,1],[1,2],[0,2]]

Output: [2,3,4]

Explanation:

• For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [3, 1].
  • The stable subarrays are [3] and [1]. The total number of stable subarrays is 2.
• For queries[1] = [1, 2], the subarray is [nums[1], nums[2]] = [1, 2].
  • The stable subarrays are [1], [2], and [1, 2]. The total number of stable subarrays is 3.
• For queries[2] = [0, 2], the subarray is [nums[0], nums[1], nums[2]] = [3, 1, 2].
  • The stable subarrays are [3], [1], [2], and [1, 2]. The total number of stable subarrays is 4.

Thus, ans = [2, 3, 4].

Example 2:

Input: nums = [2,2], queries = [[0,1],[0,0]]

Output: [3,1]

Explanation:

• For queries[0] = [0, 1], the subarray is [nums[0], nums[1]] = [2, 2].
  • The stable subarrays are [2], [2], and [2, 2]. The total number of stable subarrays is 3.
• For queries[1] = [0, 0], the subarray is [nums[0]] = [2].
  • The stable subarray is [2]. The total number of stable subarrays is 1.

Thus, ans = [3, 1].

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i] = [li, ri]
• 0 <= li <= ri <= nums.length - 1

Solution

import kotlin.math.min

class Solution {
    fun countStableSubarrays(nums: IntArray, queries: Array<IntArray>): LongArray {
        val n = nums.size
        val preSum = LongArray(n + 1)
        val idx = IntArray(n)
        val end = IntArray(n)
        var cnt = 0
        var prv = -1
        for (i in 0..<n) {
            if (nums[i] >= prv) {
                cnt++
            } else {
                cnt = 1
            }
            prv = nums[i]
            preSum[i + 1] = preSum[i] + cnt
            idx[i] = cnt - 1
        }
        end[n - 1] = n - 1
        for (i in n - 2 downTo 0) {
            if (idx[i] + 1 == idx[i + 1]) {
                end[i] = end[i + 1]
            } else {
                end[i] = i
            }
        }
        val ans = LongArray(queries.size)
        for (l in queries.indices) {
            val i = queries[l][0]
            val j = queries[l][1]
            var res = preSum[j + 1] - preSum[i]
            val endIdx = min(end[i], j)
            res -= (endIdx - i + 1).toLong() * idx[i]
            ans[l] = res
        }
        return ans
    }
}

This site is open source. Improve this page.