For each element, count how many given subarrays contain it

user_8568131 0
Viewed 321

While I was solving a problem in a coding contest, I found that I needed to do this: Given the pairs (i, j) indicating the indexes of a subarray; for each element, count how many subarrays contain it. For example:

We have the array [7, -2, -7, 0, 6], and the pairs are (0, 2), (1, 4), (2, 3), (0, 3), then the result array will be [2, 3, 4, 3, 1], since the first element is in the subarrays (0, 2), (0, 3), the second one is in (0, 2), (1, 4), (0, 3), etc.

One way of doing it would of course be manually counting, using an array and count, but that will likely give me TLE because the array size and number of pairs is too big to do it. I've also read somewhere else that you can use an extra array storing "stuff" inside it (add/subtract something for every subarray), and then traverse through that array to find out, but I don't remember where I read it.

Here's the original problem if you also have any improvements on my algorithm:

Given an array of size n, for each i-th element in the array (0 <= i <= n-1), count how many balanced subarrays contain that element. A balanced subarray is a subarray whose sum is equal to 0.

I have known a way to find subarrays with its sum to be equal to 0: https://www.geeksforgeeks.org/print-all-subarrays-with-0-sum/ . But the second task, which I have stated above, I haven't figured it out yet. If you have some ideas about this, please let me know and thank you very much.

arrays algorithm
1 Answers

You could take each pair and mark a +1 where it starts and -1 where it stops (in a separate array). These represent changes in the number of ranges that overlap a certain index. Then iterate that list to collect and accumulate those changes into absolute numbers (number of overlapping ranges).

Here is an implementation in JavaScript for the ranges you have given as example -- the content of the given list really is not relevant for this, only its size (n=5 in the example):

let pairs = [[0, 2], [1, 4], [2, 3], [0, 3]];
let n = 5;

// Translate pairs to +1/-1 changes in result array
let result = Array(n+1).fill(0); // Add one more dummy entry
for (let pair of pairs) {
    result[pair[0]]++;
    result[pair[1] + 1]--; // after(!) the range
}
result.pop(); // ignore last dummy entry

// Accumulate changes from left to right
for (let i = 1; i < n; i++) {
    result[i] += result[i-1];
}

console.log(result);

user_54598390
Related