Number Of Centered Subarrays · Interview Problem

Back to problems

Leetcode

number-of-centered-subarrays

Medium

Arrays

Two Pointers

Sliding Window

Prefix Sum

Number Of Centered Subarrays

Given an array and an index k, count the number of subarrays centered at k with conditions on min and max elements.

Acceptance 100%

Start Practice Editorial

Problem Statement

Core description from the backend problem record.

Description

You are given an integer array nums and an integer k. A subarray is called centered if the subarray includes the index k and the minimum element of the subarray is equal to the subarray's starting element and the maximum element of the subarray is equal to the subarray's ending element (or vice versa). Your task is to determine the number of such centered subarrays within the given array.

Input Format

An integer array nums.
An integer k representing an index in nums.

Output Format

Return the number of centered subarrays that include index k and satisfy the given conditions.

Constraints

1 <= nums.length <= 10^5
0 <= k < nums.length
Elements of nums are within reasonable integer bounds (e.g. -10^9 to 10^9).

Examples

Sample cases returned by the problem API.

Example 1

Input

nums = [1,3,2,4,5], k = 2

Output

Explanation

The centered subarrays at index 2 are [2], [3,2], and [2,4]. These satisfy the conditions that the minimum element is at one end and the maximum at the other, includes index 2.

Loading Preptin

Description

Input Format

Output Format

Constraints