Count Subarrays with Distant Sums Python solution?

In Python, compute the prefix sums with itertools.accumulate, sort and deduplicate them to build ranks, and use a list-based Fenwick tree with bisect for rank lookups. Sweep the prefix array once, querying and then updating the tree at each step. The code runs in O(n log n) time and is available in the FleetCode solution set.

Is Count Subarrays with Distant Sums easy or hard?

It is rated Hard, with an acceptance rate of about 32.8%. The difficulty comes from turning the subarray condition into a prefix sum counting query and then handling that query efficiently with a dynamic data structure. Once you see the prefix sum reduction, the BIT implementation is standard.

How to solve Count Subarrays with Distant Sums in O(n log n)?

Compute prefix sums, compress their values into ranks, and sweep the array from left to right. For each prefix value, query the Binary Indexed Tree for how many earlier prefixes fall inside the valid range, add that count to the answer, and then insert the current prefix into the tree.

What is the best approach for Count Subarrays with Distant Sums?

The best approach is prefix sums combined with a Binary Indexed Tree over coordinate-compressed prefix values. It converts each subarray sum into a difference of two prefix sums and counts valid earlier prefixes with a range query. The overall solution runs in O(n log n) time with O(n) space.

What data structure is used in Count Subarrays with Distant Sums?

The main structure is a Binary Indexed Tree (Fenwick tree) that stores counts of prefix sum values by compressed rank. A sorted array of compressed prefix values supports the binary search step. A segment tree can replace the BIT for the same range counting job, with slightly higher constant factors.

What is the time complexity of Count Subarrays with Distant Sums?

The optimal solution runs in O(n log n) time because each element triggers one BIT update and one range query, and each costs O(log n). The brute force approach runs in O(n^2) time. Both use O(n) space for the prefix sums and the compressed coordinates, except brute force, which uses O(1) extra space.

Is Count Subarrays with Distant Sums asked at Google, Amazon, or Meta?

This problem is tagged as Hard and covers prefix sums, Binary Indexed Trees, segment trees, and binary search. Problems with this tag set are common in interviews at large tech companies, but check FleetCode's company filters for the current frequency data before you plan around it.

Description Hints 4 Solution Video 42:42

4051. Count Subarrays with Distant Sums

Hard32.8% acceptance

You are given an integer array nums and two integers goal and k.

A subarray nums[i..j] is considered distant if the absolute difference between its sum and goal is at least k.

Return the number of distant subarrays.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,1], goal = 4, k = 1

Output: 5

Explanation:

The distant subarrays for k = 1 are:

`i`	`j`	`nums[i..j]`	Sum	`abs(sum - goal)`
0	0	`[1]`	1	3
1	1	`[2]`	2	2
2	2	`[1]`	1	3
0	1	`[1, 2]`	3	1
1	2	`[2, 1]`	3	1

Thus, the answer is 5.

Example 2:

Input: nums = [2,-1,3], goal = 2, k = 2

Output: 2

Explanation:

The distant subarrays for k = 2 are:

`i`	`j`	`nums[i..j]`	Sum	`abs(sum - goal)`
1	1	`[-1]`	-1	3
0	2	`[2, -1, 3]`	4	2

Thus, the answer is 2.

Example 3:

Input: nums = [-3,1,2], goal = 0, k = 3

Output: 2

Explanation:

The distant subarrays for k = 3 are:

`i`	`j`	`nums[i..j]`	Sum	`abs(sum - goal)`
0	0	`[-3]`	-3	3
1	2	`[1, 2]`	3	3

Thus, the answer is 2.

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= goal <= 10⁹
0 <= k <= 10⁹

Topics

Hints open one at a time

Hint 1

1a (Fenwick Tree). If k = 0, every subarray is distant. Otherwise, for a current prefix sum s and an earlier prefix sum p, the subarray is distant when p <= s - goal - k or p >= s - goal + k.

Hint 2

1b (Fenwick Tree). Compress the prefix sums and process them from left to right. Use a Fenwick tree to count earlier prefix sums in these two ranges, querying before inserting the current prefix sum.

Hint 3

2a (Merge Sort). Count the complementary subarrays whose sums satisfy goal - k < sum < goal + k, then subtract this count from n * (n + 1) / 2. Handle k = 0 directly.

Hint 4

2b (Merge Sort). Apply merge sort to the prefix sums. At each merge, use two pointers across the sorted halves to count differences strictly between the two bounds.

42:42

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def distantSubarrays(self, nums: list[int], goal: int, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,1]
4
1

Input

[2,-1,3]
2
2

Input

[-3,1,2]
0
3

Your code is saved on this device.Solution