## Google Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

This solution does not work if array is (10,-10,10,-10) a=-10, b=10

And also when array is (100,-10,10,-10,10,-10) a=-1 b=1

very nice. But, I would use a hashtable (a set or dic) when it comes to find the range of numbers in our list of cumulative sums:

1. BST insertion is O(logn) vs O(1) for hashtable

2. When you find the subset of BST btw [a,b] you actually do a search for all elements in that range in your BST which is O(mlogn) m being the size of [a:b]. Instead if you do a contains in for all [a:b] elemts in a hashtable it will be m times O(1) operation.

It is very nice idea but I can't understand a few things

1) Why you do this

count += Math.abs(subSet.first().second - subSet.last().second)+1;

See, you have done

treeSet.add(new Pair(cumsum, i));

where i is index of element. It is NOT the index of cumsum in TreeSet and you put it into second field.

So the expression

'Math.abs(subSet.first().second - subSet.last().second)+1;' is equal to the number of ELEMENTS between Sa and Sb

Yes in case when cumsum is increasing because of only positive values it will be the same as size() but what about the negative values case? It will not work!

You can check this for example input {1,2,-3,4,5} a=-100,b=100

2) It seems there are some error in calculation

For instance for input { 5,2,4,7} a=0, b=10 your code will return 8 but the right answer is 6

@SJ : subset is guaranteed O(lgn) because it uses headSet and tailSet to find the range , both of them are O(lgn).

@mger1979 : count += Math.abs(subSet.first().second - subSet.last().second)+1;

I am doing this to avoid calling size() method as Java currently do linear scan when you call size(). Instead I made my life difficult and kept index of an element in the second field of pair. So, you can calculate size using n=end-start+1 by O(1) time.

You can add a dummy Pair (0, -1) in the Treeset and don't need to process for single element in each loop.

And count += Math.abs(subSet.first().second - subSet.last().second)+1;

should be count += subSet.size();

nice job. here is the c++ implementation:

{{

size_t countinrange(vector<int>& arr, int a, int b) {

size_t N = arr.size();

vector<int> cumsum(N,0);

multiset<int> sumset;

size_t count = 0;

for (size_t i = 0; i < N; i++) {

int ai = arr[i];

if (ai >= a && ai <= b) {

count++;

}

cumsum[i] = arr[i];

if (i > 0) cumsum[i] += cumsum[i-1];

int ub = cumsum[i] - a;

int lb = cumsum[i] - b;

auto lbIter = sumset.lower_bound(lb);

if (lbIter != end(sumset)) {

auto ubIter = sumset.upper_bound(ub);

for (auto iter = lbIter; iter != ubIter; iter++) {

count++;

}

}

sumset.insert(cumsum[i]);

}

return count;

}

}}

I could solve it with easier implementation in O(nlogn), thanks to @emb hint.

The idea is based on divide and conquer technique(like(almost the same as) what we do in merge sort).

Let's call prefix sums, S_i = arr[0]+arr[1]+..+arr[i]

Basically, I need to count all A<= (S_i - S_j) <=B and i>j, plus all A<=S_i<=B.

Now, let's think about it with divide and conquer(D&C) technique.

It means, assume we have split prefix sums array,S, into two equal parts.Also, assume each part is sorted individually.

Based on D&C, we can say we know the answer of left part and right part. We just need to find all S_i's in right part, and all S_j's in left part which satisfy A<= S_i - S_j <=B (note that since all S_i's are in right part so they already satisfy i>j).

We can find them with two approaches.

Approach 1)

For every i in right part, we can do two binary searches on left part array (which is sorted) and find a range which all of them satisfy the condition.(for more explanation, you could see my first solution based on BST)

In this approach the time complexity can be computed as following recurrence:

T(n) = 2T(n/2) + O(nlogn) --> Using Master theorem: T(n) = O(n*logn^2)

Approach 2)

In approach 1, we didn't take advantage of the fact that numbers in right part are also sorted.

So if for S_i we have p1 and p2 as a range that all numbers between [p1,p2] satisfy the condition, for finding the range for S_{i+1}, we just need to move p1 and p2 forward.(It needs a little bit playing with numbers to make sure that this fact is true!) So in this case we will visit all numbers of left part, twice (one for moving p1 and one for moving p2).

So the recurrence would be:

T(n) = 2T(n/2) + O(n) --> Using Master Theorem: T(n) = O(nlogn)

Very simple and cool question. Every time, I'm so excited about D&C solutions/problems :D

Here's my c++ implementation

```
int solve(int s,int e,int a,int b,vector<int> &arr)
{
if (e<s) return 0;
if (s==e) return (a<=arr[s] && arr[s]<=b);
int mid=(e+s)>>1;
int ans = solve(s,mid,a,b,arr) + solve(mid+1,e,a,b,arr);
int p1=s,p2=s;
for (int i=mid+1; i<=e;i++){
while (p1<=mid && (arr[i]-arr[p1])>=a)
p1++;
while (p2<=mid && (arr[i]-arr[p2])>b)
p2++;
// now for all k>=p2 we have arr[i]-arr[k]<=b
// and for all k<p1 we have arr[i]-arr[k]>=a
if (p2<=mid && p2<=p1)
ans+=(p1-p2);
}
//sort the array from (s,e)
vector<int> tmp;
p1=s,p2=mid+1;
while (p1<=mid && p2<=e){
if (arr[p1]<=arr[p2]){
tmp.push_back(arr[p1]);
p1++;
}
else{
tmp.push_back(arr[p2]);
p2++;
}
}
while (p1<=mid){
tmp.push_back(arr[p1]);
p1++;
}
while (p2<=e){
tmp.push_back(arr[p2]);
p2++;
}
for (int i=0;i<tmp.size();i++){
arr[i+s]=tmp[i];
}
return ans;
}
int countPartialSums(vector<int> &nums,int a,int b)
{
int N=nums.size();
for (int i=1;i<N;i++){
nums[i]=nums[i-1]+nums[i];
}
return solve(0,N-1,a,b,nums);
}
```

Thank you:)

Your posted questions are all interesting. It seems you select the nice ones :D

@MehradaAP, nice one. I came across the same approach as your second solution. However, I would like to point out that the run time analysis of the first solution is not correct. The use of master theorem there is wrong and master theorem won't apply for this case, since nlogn is not polynomially large than n^(log2(2)). Therefore, I doubt its efficiency.

@MehrdadAP , nice solution. I came up with the similar solution as your second one. However, I would like to point out that the use of master theorem for run time analyze of the first solution is wrong. Actually master theorem doesn't apply for this case as nlogn is not polynomially larger than n=n^(log2(2)). Therefore, I doubt what its real run time is.

@plutoman, Thanks.

There is another form of Master Theorem (in Wikipedia known as Generic Form and sometimes it's called Special Case) which includes the case that I used.

(See more explanation in Master Theorem page in Wikipedia)

Also, you could compute it without MT, using recurrence tree. It's the same as merge sort.

It can be solved in O(nlogn) using cumulative sum and balanced binary search tree.

Start iterating from left to right. When we are at position i, we need to have cumulative sum of elements from 0..(i-1) in a balanced binary search tree.

For simplicity assume that we have cumulative(prefix) sums in a sorted array.

x_1, x_2, x_3, ..., x_(i-1)

which x_k = arr[0] + arr[1]+...+arr[s] (note that X is a sorted array of prefix sums)

(More clarification on X:

Let's say we have prefix sums as S_i = arr[0]+arr[1]+...arr[i]

Now X, is sorted version of S. Therefore X_1 is the smallest S_i and X_2 is the second smallest S_i and so on)

Now, for finding all possible answers for position i, we need to find all x_j provided that a<=x_i - x_j <=b.

Since array is sorted, we can do binary search on (x_i - a) and (x_i - b).

pos1 = position of greatest number which is smaller or equal than (x_i - b).

pos2 = position of smallest number which is greater or equal than (x_i - a).

now all numbers in range of [pos1,pos2] satisfy a<=x_i - x_j <=b. So we can add (pos2-pos1+1) to final answer.

We can't use a set container (in c++) instead of binary search tree, since we want to know the position of a given number in set, which is not provided in c++ set. So basically we need to write our own set (red-black BST) and at each node keep the number of its children.

Time Complexity would be O(nlogn) since we need binary search for each position.

If I understood your algorithm correctly, it seems like there is a small problem with your approach - it will output more ranges than there are.

Example

```
array: arr[0]=1 arr[1]=-2 arr[2]=3
cumulative: x_0=1 x_1=-1 x_2=2
a = b = -3
expected answer: 0
```

with balanced tree we look for suitable pair for x_1 and see that x_2 suits, since x_1 - x_2 = -3 that is in our range. But there is no cumulative sum -3 in this array, since we can only subtract x_i from x_j if i > j

@emb, That's not my approach. x_i are sorted at each step.

It was my bad on definition of x_k.

Let me explain more with your example.

x_0 is not between [a,b] --> no answer

at position 1: we have: x_0 = 1 --> no answer

at position 2: we have: x_1=-1, x_0 =1 --> no answer

So answer =0.

As an another example:

count([-2,5,-1],-2,2)

position 0: -2<=-2<=2 --> ans +=1

position 1: x_0=-2 --> ans+=0

position 2: x_0=-2 , x_1 = 3 --> (x_2=2, so x_2 - x_0 and x_2-x_1 satisfiy) ans+=2

finally: ans = 3

Yeah, you are right, sorry. The algorithm is correct, though, there exist simpler approaches (writing a self-balancing tree is not so easy?)

@emb, I got it! we can sort all the prefix sums and then sort them and do what I said on a sorted array instead of a self-balanced binary search tree!

The point is we don't care about answer of each position, we care about total answer.

But then my pre-previous comment about extra ranges would apply :)

As for balancing trees, we could probably use skip-lists instead of them, since they are much simpler, but there is O(n*log(n)) solution that doesn't use any complex data structures.

I still don't get the overall algorithm. how it works.

at each i pos we need to do sort

this iteration is O(n)

sort is O(N*logn)

then overall time complexity is O(n^2) already .

did i miss something?

@emb, @MehrdadAP Can anybody explain how would you compute the cumulative prefix sums and update the tree at each iteration in constant time? Wouldn't it take O(n) time to do that at each iteration resulting in O(n*2) total time?

@Bug-E

en.wikipedia.org/wiki/Red%E2%80%93black_tree

insertion and search is not constant, it's log(n), so the overall algorithm is O(n*log(n))

Also here is a tip about simpler solution.

Suppose you have an array of partial sums

p1 p2 ... pn

Then you divide it in two equal parts by index.

p1 p2 ... pm and pm+1 .... pn

And then suppose you have both arrays sorted in increasing order.

What happens if we take one partial sum from left array and another from right?

Do you mean cumulative sum by partial sum?

Because then if we divide the cumulative sum array at an index and sort, how do we ensure contiguous results only (leading back to your first doubt in this algorithm).

or do you mean something else by partial sum...

Do you mean cumulative sum by partial sum?

Dividing cumulative array at an index and sorting..will it not make it difficult to show results for contiguous elements only.

And why divide at middle index...

Your algorithm is not right, because when you compare a<=x_i - x_j <=b, i is not guaranteed to be greater than j.

@MehrdadAP Could you please elaborate that with a step-by-step example. It is still difficult to understand what you are trying to do. Would appreciate that. Thanks!

Assuming the numbers between pos2 and pos1 to be monotonically increasing sequence seems wrong. Basically, pos2 - pos1 + 1 includes more subarrays than it should.

For instance, ([4, 100, -100, 3], 3, 7) = 2, but your algorithm would yield 4.

@Larry: it's guaranteed because based on what I said, when we are at position i, we just have prefix sums before i in the BST.

@myzn: I came up with another solution, and I tried to explain it more coherently. Part of new solution is the same as above solution. I hope it could help.

@Jar: Because the right answer is 4 :D

[4] [4,100,-100] [4,100,-100,3] [3]

Let's do it step by step for more clarification:

0: X_0 = 4 --> ans=1

1: X_0=4 -> pos1=pos2=null

2:X_0 = 4,X_1 = 104 -> pos1=pos2=null

3:X_0=4,X_1=4,X_2=104 -> X_4=7 so ans++ and pos1=0,pos2=1 so ans+=2

total ans = 4.

probably in case of equal numbers we need to define the pos1 and pos2 more accurate. But the whole idea works.

How you will handle the negative values ? in this case the cumulative array will not be increasing !

and if we deal with positive values only ,we can just use binary search instead of binary search tree to get the indices.

How about this algorithm:

1. find the min of the array. If the min <= 0, go to 2; otherwise go to 3.

2. add the abs(min) + 1 to each element so all elements > 0. add abs(min) + 1 to (a,b) so it becomes (a+abs(min)+1, b+abs(min)+1).

3. use the naive algorithm with early termination. When considering an element, if the sum of a sub array > b + min, then stop scanning forward.

The complexity is O(nk) where k is the number of sub arrays whose sum < b + abs(min) + 1. In the worst case it can be O(n^2) but now the complexity is output sensitive.

So we have an array

-4 2 -5 3 -1 and a=-1 b=0

min =-5 so new array is

1 7 0 8 4 a=4 b=5

and now I don't get it, will the naive algorithm account 2 -5 3, that is 7 0 8 ?

Isn't the problem is that when you add min to every element, the sum of range becomes sum(old_range) + min * len(old_range) and not sum(old_range) + min?

How about this:

1. find the min of the whole array. If min <= 0, go to 2. otherwise, go to 3.

2. add abs(min) + 1 to each element and (a, b) so that all element > 0 and the range becomes (a+abs(min)+1, b+abs(min)+1).

3. use naive algorithm with early termination. If the sum of a sub array > b+abs(min)+1, then stop scanning longer sub array.

The complexity is O(nk) where k is the number of subarray whose sum < b+abs(min)+1. It can be O(n^2) in worst case but is output sensitive.

Same idea as MehrdadAP, but with code.

```
static class RedBlackTree {
static class Node {
Node left, right;
int value, numLeft, numRight;
public Node(int val) {
value = val;
}
public void insert(Node n) {
// TODO: make sure that the tree is balanced while inserting
if (n.value < this.value) {
if (this.left == null) this.left = n;
else this.left.insert(n);
this.numLeft++;
} else {
if (this.right == null) this.right = n;
else this.right.insert(n);
this.numRight++;
}
}
}
Node head;
public void insert(int value) {
if (head == null) head = new Node(value);
else head.insert(new Node(value));
}
public int numBetween(int lower, int higher) {
return numBetween(lower, higher, Integer.MIN_VALUE, Integer.MAX_VALUE, head);
}
public int numBetween(int lower, int higher, int treeLower, int treeHigher, Node n) {
if (n == null) return 0;
if (treeLower >= lower && treeHigher <= higher) return 1 + n.numLeft + n.numRight;
int count = 0;
if (lower <= n.value && n.value <= higher) count++;
count += numBetween(lower, higher, treeLower, n.value, n.left);
count += numBetween(lower, higher, n.value, treeHigher, n.right);
return count;
}
}
public static int numSubarraysInRange(int[] ints, int a, int b) {
int sum = 0;
int min = Math.min(a, b), max = Math.max(a, b);
a = min;
b = max;
RedBlackTree tree = new RedBlackTree();
tree.insert(0);
int answer = 0;
for (int i = 0; i < ints.length; i++) {
sum += ints[i];
// Query the tree for the number of intervals between sum - b and sum - a
answer += tree.numBetween(sum - b, sum - a);
tree.insert(sum);
}
return answer;
}
```

```
public void findSubarray(int[] nums, int start, int end) {
int n = nums.length;
int j = 0, i = 0;
int sum = nums[0];
while (i < n) {
// Take out one from start
while (sum < start && end < sum && j < i) {
sum -= nums[j];
j++;
}
// Answer
if (start <= sum && sum <= end) {
if (j < i)
System.out.print(j + " - " + i);
else
System.out.print(j);
System.out.println("");
}
sum += nums[i];
i++;
// complete j if i is over
if (i == n && j < n - 1) {
j++;
i = j;
sum = nums[j];
}
}
}
```

```
public void findSubarray(int[] nums, int start, int end) {
int n = nums.length;
int j = 0, i = 0;
int sum = nums[0];
while (i < n) {
// Take out one from start
while (sum < start && end < sum && j < i) {
sum -= nums[j];
j++;
}
// Answer
if (start <= sum && sum <= end) {
if (j < i)
System.out.print(j + " - " + i);
else
System.out.print(j);
System.out.println("");
}
sum += nums[i];
i++;
// complete j if i is over
if (i == n && j < n - 1) {
j++;
i = j;
sum = nums[j];
}
}
}
```

Could someone explain me the algo with a clear example,i am not able to understand the x_k notation

public int count(int[] array, int min, int max) {

return count(array, 0, array.length-1, min, max);

}

private int count(int[] array, int s, int e, int min, int max) {

if( s == e ){

if( array[s]>=min && array[e]<=max ){

return 1;

} else {

return 0;

}

}

int mid = (e-s)/2 + s;

int[] sum = new int[e-mid];

for(int i=mid+1,j=0;i<=e;i++,j++){

if( j==0 ){

sum[j] = array[i];

} else {

sum[j] = array[i]+sum[j-1];

}

}

Arrays.sort(sum);

int count=0;

int total = 0;

for(int i=mid;i>=s;i--){

total += array[i];

count += range(sum, min-total, max-total);

}

return count+count(array, s, mid, min, max)+count(array, mid+1, e, min, max);

}

private int range(int[] array, int min, int max){

int a = Arrays.binarySearch(array,min);

int b = Arrays.binarySearch(array,max);

if( a>=0 && b<0){

while ( a-1>=0 && array[a-1] == array[a]){

a--;

}

return Math.abs(b)-a-1;

} else if( a>=0 && b>=0 ){

while ( a-1>=0 && array[a-1] == array[a]){

a--;

}

while ( b+1<array.length && array[b+1] == array[b]){

b++;

}

return b-a+1;

} else if( a<0 && b>=0 ){

while ( b+1<array.length && array[b+1] == array[b]){

b++;

}

return b-Math.abs(a)+2;

} else { // a<0 && b<0

return a-b;

}

}

```
public int count(int[] array, int min, int max) {
return count(array, 0, array.length-1, min, max);
}
private int count(int[] array, int s, int e, int min, int max) {
if( s == e ){
if( array[s]>=min && array[e]<=max ){
return 1;
} else {
return 0;
}
}
int mid = (e-s)/2 + s;
int[] sum = new int[e-mid];
for(int i=mid+1,j=0;i<=e;i++,j++){
if( j==0 ){
sum[j] = array[i];
} else {
sum[j] = array[i]+sum[j-1];
}
}
Arrays.sort(sum);
int count=0;
int total = 0;
for(int i=mid;i>=s;i--){
total += array[i];
count += range(sum, min-total, max-total);
}
return count+count(array, s, mid, min, max)+count(array, mid+1, e, min, max);
}
private int range(int[] array, int min, int max){
int a = Arrays.binarySearch(array,min);
int b = Arrays.binarySearch(array,max);
if( a>=0 && b<0){
while ( a-1>=0 && array[a-1] == array[a]){
a--;
}
return Math.abs(b)-a-1;
} else if( a>=0 && b>=0 ){
while ( a-1>=0 && array[a-1] == array[a]){
a--;
}
while ( b+1<array.length && array[b+1] == array[b]){
b++;
}
return b-a+1;
} else if( a<0 && b>=0 ){
while ( b+1<array.length && array[b+1] == array[b]){
b++;
}
return b-Math.abs(a)+2;
} else { // a<0 && b<0
return a-b;
}
}
```

```
public class GG_SubArraySumInRange {
// This java code uses segment tree. TC: O(n*lgn*lgn)
// O(n*lgn*lgn)
int getSubArr(int[] nums, int low, int high)
{
if(nums==null || nums.length==0)
return 0;
//get the sum array. O(n)
Sum[] sums = new Sum[nums.length];
for(int i=0; i<nums.length;++i) {
if(i==0) {
sums[i] = new Sum(nums[i], 0);
}
else {
sums[i] = new Sum(sums[i-1].val + nums[i], i);
}
}
//O(nlgn)
Arrays.sort(sums);
//build segment tree on the sorted sum array. O(nlgn)
TreeNode segTree = buildSegTree(sums, 0, sums.length-1, null);
TreeNode[] map = new TreeNode[nums.length];
//create a map of original index to its corresponding segment tree node. O(n)
populateMap(segTree, map);
int count = 0;
int prevSum = 0;
//O(n*lgn*lgn)
for(int i=0; i<nums.length; ++i)
{
// get updated range for searching in segment tree.
int low2 = low + prevSum;
int high2 = high + prevSum;
// search the segment for each updated range. O(lgn*lgn)
count += searchRange(sums, segTree, low2, high2);
prevSum += nums[i];
// After handling this num, excluding it from the segment tree. O(lgn)
excludeNode(map[i]);
}
return count;
}
// data structure for sum sorting.
class Sum implements Comparable<Sum> {
int val;
int ind; // the index in the original nums array.
Sum(int val, int ind)
{
this.val = val;
this.ind = ind;
}
public int compareTo(Sum s)
{
return this.val - s.val;
}
}
class TreeNode {
ArrayList<Integer> sumInd = new ArrayList<>();
int ind; // the original index in nums array.
boolean excluded; // indicate if current node is excluded.
TreeNode parent; // for segment tree update in O(lgn)
TreeNode left;
TreeNode right;
public TreeNode(TreeNode parent, int ind)
{
this.parent = parent;
this.ind = ind;
this.excluded = false;
this.left = this.right = null;
}
}
boolean isValid(int n, int low, int high) {
return low<=n && n<=high;
}
void excludeNode(TreeNode node)
{
node.excluded = true;
int st = node.sumInd.get(0);
int end = node.sumInd.get(node.sumInd.size()-1);
while(true)
{
node = node.parent;
if(node == null)
break;
int st1 = bs(node.sumInd, 0, node.sumInd.size()-1, st);
int end1;
if(st == end)
end1 = st1;
else
end1 = bs(node.sumInd, 0, node.sumInd.size()-1, end);
for(int i=end1; i>st1-1; --i)
node.sumInd.remove(i);
// if all children have been excluded, then current node is excluded also.
if(node.sumInd.size()==0)
node.excluded = true;
}
}
// regular binary search
int bs(ArrayList<Integer> sumInd, int st, int end, int target)
{
if(st>end)
return -1;
int mid = st + (end-st)/2;
if(target == sumInd.get(mid))
return mid;
if(target < sumInd.get(mid))
{
return bs(sumInd, st, mid-1, target);
}
return bs(sumInd, mid+1, end, target);
}
// populate the map for original indexes in nums to TreeNodes.
void populateMap(TreeNode segTree, TreeNode[] map)
{
//preorder dfs
if(segTree == null)
return;
if(segTree.ind != -1)
map[segTree.ind] = segTree;
populateMap(segTree.left, map);
populateMap(segTree.right, map);
}
TreeNode buildSegTree(Sum[] sums, int st, int end, TreeNode parent)
{
if(st > end)
return null;
if(st == end) {
TreeNode root = new TreeNode(parent, sums[st].ind);
root.sumInd.add(st);
return root;
}
int mid = st + (end-st)/2;
TreeNode root = new TreeNode(parent, -1);
root.left = buildSegTree(sums, st, mid, root);
root.right = buildSegTree(sums, mid+1, end, root);
for(int i=st; i<end+1; ++i) // this loop does not change tree build complexity O(nlgn)
root.sumInd.add(i);
return root;
}
int searchRange(Sum[] sums, TreeNode segTree, int low, int high) {
if(segTree == null)
return 0;
int lowSum = sums[segTree.sumInd.get(0)].val;
int highSum = sums[segTree.sumInd.get(segTree.sumInd.size()-1)].val;
if(high < lowSum || highSum < low)
return 0;
if(low <= lowSum && highSum <= high)
return segTree.sumInd.get(segTree.sumInd.size()-1) - segTree.sumInd.get(0) + 1;
int count = 0;
count += searchRange(sums, segTree.left, low, high);
count += searchRange(sums, segTree.right, low, high);
if(segTree.ind!=-1 && isValid(sums[segTree.ind].val, low, high))
{
count+=1;
}
return count;
}
}
```

I think it can be done in O(n) time.

Given an arr of len=5 such as {-2, 5, -1, -2, -1}, imagine all the sums you need to calculate organized like this, where each number on lines 1-4 is the sum of the length of numbers on line 0 if you draw a triangle to it. So the -1 on line 4 is a sum of all the numbers on line 0. And the -4 on line 2 is a sum of {-1, -2, -1} and the 4 on line 1 is a sum of {5, -1}

```
0: -2 5 -1 -2 -1
1: 3 4 -3 -3
2: 2 2 -4
3: 0 1
4: -1
```

You can rotate to its side and represent the above in an n x n matrix:

```
0 1 2 3 4
0 -2
1 3 5
2 2 2 -1
3 0 2 0 -2
4 -1 -4 1 -1 -1
```

And the algorithm to populate it and count the number of subarrays is something like

```
int[][] sums = new int[len][len];
int count = 0;
// populate the middle diagonal with arr, and along the way,
// check whether the number is between a and b
for (int i =0; i < len; i++) {
sums[i][i] = arr[i];
if (arr[i] >= a && arr[i] <= b) {
count++;
}
// now populate "lines" 1-4
for (int line=1; i < len; i++) {
int tmp = sums[line-1][line-1] + sums[line][line];
sums[line -1][line] = tmp;
if (tmp >= a && tmp <= b) {
count++;
}
}
System.out.println(count);
```

It takes two unnested for loops, so that's O(n);

This is my first time answering Career Cup. Please be nice:)

A simple O(nlgn) solution using cumsum and Java navigable set's subset operation. The idea is that if the number itself falls between the range than its a subset and we count it. Otherwise, if cumsum at the position of the element falls between the range then there is a subset from the start to this position and we count it.

Note that, there might be many other subarray's in between start and current position that can sum to the given range. We can check if A[i..j] sums to S by checking if cumsum[j]-cumsum[i] = S. In other words, at each position i, we can check if cumsum[j]-S was seen earlier in some previous position i < j. We can easily do this using a hash to track each of the cumsum at each position.

Now, question is how to track the range of sum? Idea is to put the cumsums seen so far in a TreeSet (i.e. BST order) and for a position i we find how many elements fall in the range

by finding number of elements in the subMap from (cumsum[i]-b) to (cumsum[i]-a) (think why?). So, we increase count by this number.

Below is a O(nlgn) implementation of this logic. Note that, treeset is handled in such a way that we don't have to call size() method that is O(n) itself. Instead I keep index and calculate size by using simple formula of (endIndex-startIndex+1) .

Overall time complexity O(nlgn), overall space complexity O(n).

- zahidbuet106 October 02, 2015