CareerCup

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).

public static int subArrayWithSumInRange(int[] A, int a, int b){
	int count = 0;
	TreeSet<Pair> treeSet = new TreeSet<test.Pair>();
	int cumsum = 0;
	
	for(int i = 0; i< A.length; i++){
		cumsum+=A[i];
		
		if(A[i] >= a && A[i] <= b){
			count++;
		}

		NavigableSet<Pair> subSet = treeSet.subSet(new Pair(cumsum-b, i+1), true, new Pair(cumsum-a, i+1), false);
		if(!subSet.isEmpty()){
			count += Math.abs(subSet.first().second - subSet.last().second)+1;
		}
		treeSet.add(new Pair(cumsum, i));
	}
	
	return count;
}

private static class Pair implements Comparable<Pair>{
	public int first;
	public int second;
	
	public Pair(int first, int second){
		this.first = first;
		this.second = second;
	}

	@Override
	public int compareTo(Pair o) {
		if(this.first == o.first)
			return Integer.compare(this.second, o.second);
		else
			return Integer.compare(this.first, o.first);
	}

	@Override
	public String toString() {
		return "[" + first + "," + second + "]";
	}
}

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);
}

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.

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.

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;
    }

The algorithm is not right because you cannot make sure that when you compare a<=x_i - x_j <=b, i is guaranteed to be greater than 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];
			}
		}
	}

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;
    }
}

Assuming the array has unique numbers we need to only find the largest sequences.
Then the number of total sequences is n(n+1)/2.

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:)

Put suffix and prefix sums in a map. Then iterate the map to find what falls in the range. O(n)

Put suffix and prefix sums in a map. Then iterate the map.Put suffix and prefix sums in a map. Then iterate the map to find what falls in the range. O(n)