Count Subarrays with Distant Sums solution and explanation
The problem
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 <= 105-109 <= nums[i] <= 109-109 <= goal <= 1090 <= k <= 109
Approach overview
Problem Overview: You are given an array and must count the subarrays whose sums satisfy a distance condition. Every subarray sum is a difference of two prefix sums, so the problem reduces to counting valid pairs of prefix sum values.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Fix a left endpoint and extend the right endpoint one element at a time, keeping a running sum. At each step, check whether the current subarray sum meets the distance condition and increment the counter. This works for any input size you can afford to scan quadratically, and it is the fastest path to a correct answer during a contest. The weakness is that every pair of endpoints gets visited, so it breaks down once n reaches the tens of thousands.
Approach 2: Prefix Sums with a Binary Indexed Tree (O(n log n) time, O(n) space)
Build the prefix sum array P, where P[0] = 0 and P[i] is the sum of the first i elements. A subarray (l, r] has sum P[r] - P[l], so for each r you need to count the earlier prefix values P[l] that fall in a specific range relative to P[r]. Those earlier values arrive incrementally, so a static sorted array is not enough. Compress the prefix sum values to ranks, then store the inserted prefix values in a Binary Indexed Tree keyed by rank. Each query becomes a range count on the tree, and each insert is a point update. Binary search over the compressed values finds the rank boundaries for each query in O(log n) time. The prefix sum transformation is what turns the subarray condition into a lookup, and the tree handles the dynamic counting.
Recommended for interviews: Interviewers expect the prefix sum reduction plus a BIT or segment tree with coordinate compression. Writing the brute force first shows you understand the subarray structure. Moving to the prefix sum and BIT version shows you can convert a range condition into an ordered counting problem, and that is the skill being tested. Keep the binary search step for locating ranks clean and verify the boundary inclusivity against the problem statement before you submit.
Solution
Thinking
There are quadratically many subarrays, so
n = 10^5rules out enumeration. The complement of|sum - goal| \ge kis|sum - goal| < k; subtracting that count from the total is cleaner.Prefix sums turn a subarray sum into a difference of two points. For each right endpoint we need how many earlier prefix sums fall inside a numeric interval.
After sorting the prefix sums we binary-search the Fenwick indices, query the interval, then insert the current value.
Let s be the prefix-sum array of nums (s[0] = 0). The sum of the subarray nums[L..R-1] is s[R] - s[L], and it is distant if and only if |s[R] - s[L] - goal| \ge k.
There are \frac{n(n+1)}{2} nonempty subarrays. We count those that fail the condition, i.e. |s[R] - s[L] - goal| < k, and subtract that count from the total.
The inequality is equivalent to
$
s[R] - goal - k < s[L] < s[R] - goal + k
that is, s[L] lies in the closed interval [s[R] - goal - k + 1,\, s[R] - goal + k - 1].
Enumerate the prefix sums v = s[R] from left to right. Among the prefix sums already inserted, query how many fall in [a, b] and subtract that from the answer, then insert v. For discretization we sort s and locate Binary Indexed Tree indices by binary search.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of nums$.
class BinaryIndexedTree:
__slots__ = "n", "c"
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, delta: int) -> None:
while x <= self.n:
self.c[x] += delta
x += x & -x
def query(self, x: int) -> int:
s = 0
while x:
s += self.c[x]
x -= x & -x
return s
class Solution:
def distantSubarrays(self, nums: list[int], goal: int, k: int) -> int:
s = list(accumulate(nums, initial=0))
st = sorted(s)
n = len(nums)
ans = (1 + n) * n // 2
bit = BinaryIndexedTree(len(st) + 1)
for v in s:
a = v - goal - k + 1
b = v - goal + k - 1
l = bisect_left(st, a) + 1
r = bisect_left(st, b + 1)
if l <= r:
ans -= bit.query(r) - bit.query(l - 1)
bit.update(bisect_left(st, v) + 1, 1)
return ansclass BinaryIndexedTree {
private final int n;
private final long[] c;
BinaryIndexedTree(int n) {
this.n = n;
this.c = new long[n + 1];
}
void update(int x, long delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
long query(int x) {
long s = 0;
while (x > 0) {
s += c[x];
x -= x & -x;
}
return s;
}
}
class Solution {
public long distantSubarrays(int[] nums, int goal, int k) {
int n = nums.length;
long[] s = new long[n + 1];
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
long[] st = s.clone();
Arrays.sort(st);
long ans = (long) n * (n + 1) / 2;
BinaryIndexedTree bit = new BinaryIndexedTree(st.length + 1);
for (long v : s) {
long a = v - goal - k + 1L;
long b = v - goal + k - 1L;
int l = lowerBound(st, a) + 1;
int r = lowerBound(st, b + 1);
if (l <= r) {
ans -= bit.query(r) - bit.query(l - 1);
}
bit.update(lowerBound(st, v) + 1, 1);
}
return ans;
}
private int lowerBound(long[] nums, long target) {
int l = 0;
int r = nums.length;
while (l < r) {
int m = (l + r) >>> 1;
if (nums[m] < target) {
l = m + 1;
} else {
r = m;
}
}
return l;
}
}class BinaryIndexedTree {
int n;
vector<long long> c;
public:
BinaryIndexedTree(int n)
: n(n)
, c(n + 1) {}
void update(int x, long long delta) {
while (x <= n) {
c[x] += delta;
x += x & -x;
}
}
long long query(int x) {
long long s = 0;
while (x) {
s += c[x];
x -= x & -x;
}
return s;
}
};
class Solution {
public:
long long distantSubarrays(vector<int>& nums, int goal, int k) {
int n = nums.size();
vector<long long> s(n + 1);
for (int i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
vector<long long> st = s;
sort(st.begin(), st.end());
long long ans = 1LL * n * (n + 1) / 2;
BinaryIndexedTree bit(st.size() + 1);
for (long long v : s) {
long long a = v - goal - k + 1LL;
long long b = v - goal + k - 1LL;
int l = lower_bound(st.begin(), st.end(), a) - st.begin() + 1;
int r = lower_bound(st.begin(), st.end(), b + 1) - st.begin();
if (l <= r) {
ans -= bit.query(r) - bit.query(l - 1);
}
int pos = lower_bound(st.begin(), st.end(), v) - st.begin() + 1;
bit.update(pos, 1);
}
return ans;
}
};class BinaryIndexedTree {
private readonly n: number;
private readonly c: number[];
constructor(n: number) {
this.n = n;
this.c = new Array(n + 1).fill(0);
}
update(x: number, delta: number): void {
while (x <= this.n) {
this.c[x] += delta;
x += x & -x;
}
}
query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}
function distantSubarrays(nums: number[], goal: number, k: number): number {
const n = nums.length;
const s = new Array<number>(n + 1).fill(0);
for (let i = 0; i < n; i++) {
s[i + 1] = s[i] + nums[i];
}
const st = [...s].sort((a, b) => a - b);
let ans = (n * (n + 1)) / 2;
const bit = new BinaryIndexedTree(st.length + 1);
for (const v of s) {
const a = v - goal - k + 1;
const b = v - goal + k - 1;
const l = _.sortedIndex(st, a) + 1;
const r = _.sortedIndex(st, b + 1);
if (l <= r) {
ans -= bit.query(r) - bit.query(l - 1);
}
bit.update(_.sortedIndex(st, v) + 1, 1);
}
return ans;
}type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{
n: n,
c: make([]int, n+1),
}
}
func (t *BinaryIndexedTree) update(x, delta int) {
for x <= t.n {
t.c[x] += delta
x += x & -x
}
}
func (t *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += t.c[x]
x -= x & -x
}
return s
}
func distantSubarrays(nums []int, goal int, k int) int64 {
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
st := append([]int(nil), s...)
sort.Ints(st)
ans := n * (n + 1) / 2
bit := NewBinaryIndexedTree(len(st) + 1)
for _, v := range s {
a := v - goal - k + 1
b := v - goal + k - 1
l := sort.SearchInts(st, a) + 1
r := sort.SearchInts(st, b+1)
if l <= r {
ans -= bit.query(r) - bit.query(l-1)
}
bit.update(sort.SearchInts(st, v)+1, 1)
}
return int64(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Small inputs or quick verification of results |
| Prefix Sums + Binary Indexed Tree | O(n log n) | O(n) | General case and large constraints |
Frequently asked questions
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.