Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2488.html

2488. Count Subarrays With Median K

• Difficulty: Hard.
• Related Topics: Array, Hash Table, Prefix Sum.
• Similar Questions: Number of Subarrays with Bounded Maximum, Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold.

Problem

You are given an array nums of size n consisting of **distinct **integers from 1 to n and a positive integer k.

Return the number of non-empty subarrays in **nums that have a median equal to **k.

Note:

The median of an array is the **middle **element after sorting the array in **ascending **order. If the array is of even length, the median is the **left **middle element.

• For example, the median of [2,3,1,4] is 2, and the median of [8,4,3,5,1] is 4.

• A subarray is a contiguous part of an array.

  Example 1:

Input: nums = [3,2,1,4,5], k = 4
Output: 3
Explanation: The subarrays that have a median equal to 4 are: [4], [4,5] and [1,4,5].

Example 2:

Input: nums = [2,3,1], k = 3
Output: 1
Explanation: [3] is the only subarray that has a median equal to 3.

  Constraints:

• n == nums.length

• 1 <= n <= 105

• 1 <= nums[i], k <= n

• The integers in nums are distinct.

Solution (Java, C++, Python)

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int countSubarrays(int[] nums, int k) {
          int n = nums.length;
          int i = 0;
          for (int j = 0; j < n; ++j) {
              if (nums[j] == k) {
                  i = j;
                  break;
              }
          }
          int ans = 1;
          int[] d = new int[n << 1 | 1];
          int mi = 0, mx = 0;
          for (int j = i + 1; j < n; ++j) {
              if (nums[j] < k) {
                  ++mi;
              } else {
                  ++mx;
              }
              if (mx - mi >= 0 && mx - mi <= 1) {
                  ++ans;
              }
              ++d[mx - mi + n];
          }
          mi = 0;
          mx = 0;
          for (int j = i - 1; j >= 0; --j) {
              if (nums[j] < k) {
                  ++mi;
              } else {
                  ++mx;
              }
              if (mx - mi >= 0 && mx - mi <= 1) {
                  ++ans;
              }
              ans += d[mi - mx + n] + d[mi - mx + 1 + n];
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int countSubarrays(vector<int>& nums, int k) {
          int n = nums.size();
          int i = 0;
          for (int j = 0; j < n; ++j) {
              if (nums[j] == k) {
                  i = j;
                  break;
              }
          }
          int ans = 1;
          int d[n << 1 | 1];
          memset(d, 0, sizeof d);
          int mi = 0, mx = 0;
          for (int j = i + 1; j < n; ++j) {
              if (nums[j] < k) ++mi;
              else ++mx;
              if (mx - mi >= 0 && mx - mi <= 1) ++ans;
              ++d[mx - mi + n];
          }
          mi = 0, mx = 0;
          for (int j = i - 1; ~j; --j) {
              if (nums[j] < k) ++mi;
              else ++mx;
              if (mx - mi >= 0 && mx - mi <= 1) ++ans;
              ans += d[mi - mx + n] + d[mi - mx + n + 1];
          }
          return ans;
      }
  };
  

• class Solution:
      def countSubarrays(self, nums: List[int], k: int) -> int:
          i = next(i for i, v in enumerate(nums) if v == k)
          n = len(nums)
          ans = 1
          d = defaultdict(int)
          mi = mx = 0
          for j in range(i + 1, n):
              if nums[j] < k:
                  mi += 1
              else:
                  mx += 1
              if 0 <= mx - mi <= 1:
                  ans += 1
              d[mx - mi] += 1
          mi = mx = 0
          for j in range(i - 1, -1, -1):
              if nums[j] < k:
                  mi += 1
              else:
                  mx += 1
              if 0 <= mx - mi <= 1:
                  ans += 1
              ans += d[mi - mx] + d[mi - mx + 1]
          return ans
  
  

• func countSubarrays(nums []int, k int) int {
  	i, n := 0, len(nums)
  	for nums[i] != k {
  		i++
  	}
  	ans := 1
  	cnt := make([]int, n<<1|1)
  	x := 0
  	for j := i + 1; j < n; j++ {
  		if nums[j] > k {
  			x++
  		} else {
  			x--
  		}
  		if x >= 0 && x <= 1 {
  			ans++
  		}
  		cnt[x+n]++
  	}
  	x = 0
  	for j := i - 1; j >= 0; j-- {
  		if nums[j] > k {
  			x++
  		} else {
  			x--
  		}
  		if x >= 0 && x <= 1 {
  			ans++
  		}
  		ans += cnt[-x+n] + cnt[-x+1+n]
  	}
  	return ans
  }
  

• function countSubarrays(nums: number[], k: number): number {
      const i = nums.indexOf(k);
      const n = nums.length;
      const cnt = new Array((n << 1) | 1).fill(0);
      let ans = 1;
      let x = 0;
      for (let j = i + 1; j < n; ++j) {
          x += nums[j] > k ? 1 : -1;
          ans += x >= 0 && x <= 1 ? 1 : 0;
          ++cnt[x + n];
      }
      x = 0;
      for (let j = i - 1; ~j; --j) {
          x += nums[j] > k ? 1 : -1;
          ans += x >= 0 && x <= 1 ? 1 : 0;
          ans += cnt[-x + n] + cnt[-x + 1 + n];
      }
      return ans;
  }
  
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions