code_fille's blog

By code_fille, history, 3 years ago, In English,

Given an array of integers and a range find the count of subarrays whose sum lies in the given range. Do so in less than O(n^2) complexity.

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

»
3 years ago, # |
Rev. 6   Vote: I like it +10 Vote: I do not like it

let us call the range [ l, r ] build the prefix sum array for the given array, let us call it B (B[0]=0 for empty prefix)

now
B[i] - B[j] where 0 ≤ j < i
gives all the sums of subarrays that end in ith element

So, in order for the sum of subarray [ j + 1...i ] to be between l and r the following should be true:

l ≤ B[i] - B[j] ≤ r
=>
l - B[i] ≤  - B[j] ≤ r - B[i]
=>
B[i] - l ≥ B[j] ≥ B[i] - r

so for each B[i], we should find the number of B[j] s that are in the previous range and j < i, which is done in a segment tree

total complexity: O(nlogn)

NOTE If the values are all positive you can use binary search for O(nlogn)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How could segment tree be used to find the possible values of j?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Array C , C[i] is the number of B[j]'s which are equal to i
      You need a segment tree to perform 2 types of queries:
      1) add 1 to C[x]
      2) get the sum of C[x] : s<=x<=e

      So for each B[i] you query for the sum of C[x] between B[i]-r and B[i]-l Then you add 1 to C[B[i]]

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        B[i] can be negative ..how it is possible to store in array?

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Then compress the values

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I was trying to solve this question. I tried to compress the values. But it is giving WA. Here is the code. Please help me.

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              You will have at most N+2 different values (Including L and R), compress them.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Can you please have a glance at my code?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                For each B[i], I have to put B[i]-l and B[i]-r. I have to compress n*2*n values.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Were you able to solve that question ? If yes, can you please share the code? I am also getting W.A.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, I solved it Here is the code

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    If the values are all positive you can solve in O(N) using only 3 pointers.

    Note: You can also solve in O(NlogN) without segment tree, just using divide-and-conquer idea.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you elaborate how divide and conquer could be used?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        B — partial sum, B[0] = 0.

        Now we are going to split our verctor a into 2 parts with size N / 2 each.

        2 cases are possible:

        1) l, r < N / 2 or l, r > N / 2: We can find the answer recursively for the left part and for the right part.

        2) l < N / 2 and r > N / 2: We can find the answer in O(N) using 3 pointers but only if the left part sorted and the right part sorted too. But you can maintain these parts sorted by using merge sort algorithm.

        The algorithm is very similar to the algorithm for counting inversions in O(NlogN) time. You can find the explanation on coursera: link

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For segment tree , Is the time complexity is (n*log(sum of all array elements)) ? correct me if i am wrong.

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      correct me if i am wrong.

      Wrong? You didn't state anything.

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As JoudZouzou said ,when we use segment tree to solve the problem total complexity: O(nlogn) but here the logn is not the size of input but it is log of the sum of the array elements

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Your solution is quite beautiful :)

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Instead of segment tree, binary search can also be used( inbuilt functions lower_bound() and upper_bound()) to solve this problem in O(nlgn). Here is the code in c++:

Function to return the count- 

int numRange(vector<int> &A, int B, int C) {
    int i,j=0,n=A.size();
//store prefix sum
    vector<long long int> psum(n,0);
    for(i=0;i<n;i++)
    {
        psum[i]=((i==0)?0:psum[i-1])+A[i];
    }

   //for each i as start index, find the end points that satisfy the range
    for(i=0;i<n;i++)
    {
        auto l=lower_bound(psum.begin(),psum.end(),(i==0?0:psum[i-1])+B);
        auto r=upper_bound(psum.begin(),psum.end(),(i==0?0:psum[i-1])+C);
        j+=r-l;
        
    }
    return j;
}
 
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please provide such type of problem for more practice? :)

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Note: This works only for positive integers.

I think following expression may help: (For a range [L,R])

Number of subarrays having sum less than or equal to R - Number of subarrays having sum less than or equal to L-1

For finding required number of subarrays refer this: Subarrays with sum less than k