Can somebody explain the O(n) solution please


#1

Comment body goes here.


#2

Compute the prefix sum array S[i].
For each left start point, keep two pointers which indicate the right end points associated to the range B and C.
For each left start point, move the right pointers to the right to fit the range B and C on the prefix sum array. The key observation here is that you don’t need to restart the pointers from the left start point at each iteration, but from the previous values, so the total number of increments for the two pointers will be at most N.


#3

How can it be true if there are O(n^2) solutions, for example, an array that all values are 0 and the range is 0-1.


#4

Hi
I think that the prefix sum array is a nice idea but it doesn’t solve the problem.
This is becuase, for the input array of { 10, 5, 1, 0, 2 } and 6, 8 bounds, the answer is 3
( [5, 1], [5, 1 0], [5, 1, 0, 2] )
But
In your prefix sum, the array looks like this [10, 15, 16, 16, 18]
how do you deduce the answer 3 from it ?
I don’t see how.
(cause it is the sums that start with the first element. no sums that starts with the second, and third, …)


#5

sum(i…j) = S[j] - S[i-1]


#6

Thanks.
OK, understood.
So you start with the left index at position 0, and advance with the right index until it is bigger than C, and cumpute the sum(i…j) = S[j] - S[i-1]
How do you advance from there, with only moving the left index one place, and not return with the right index, back to left ?


#7

Input is 10, 5, 1, 0, 2, 4, 2, 0, 2, 1
B= 6, C= 8
the psum is 10 15 16 16 18 22 24 24 26 27
can’t figure it out, how to solve it in O(N)
anyone as C/C++ solution in O(N) ?


#8

Solution in O(N)

int Solution::numRange(vector &a, int b, int c) {

int n = a.size();

// sort(a.begin(),a.end());
int i = 0;
int j = 1;
int k = 1;
int ceilSum = a[0];
int ans = 0;
int floorSum = a[0];

while(i < n){
 //   cout<<floorSum<<" "<<ceilSum<<endl;
    while(k < n  &&  floorSum<b){
      
        floorSum += a[k];
         k++;
    }
    if(k == n && !(floorSum>=b && floorSum<=c) ){
        return ans;
    }
    if(j < k){
        j = k;
        ceilSum = floorSum;
    }
    while(j < n && ceilSum <= c && (floorSum>=b && floorSum<=c) ){
        
        ceilSum += a[j];
     //   cout<<" "<<j<<" "<<ceilSum<<endl;
        if(ceilSum > c){
            ceilSum -= a[j];
            break;
        }
        j++;
    }
//    cout<<endl;
   
    if((floorSum>=b && floorSum<=c))
    ans += j - k+1;
    floorSum -= a[i];
    ceilSum -= a[i];

// cout<<i<<" “<<k<<” “<<j<<” "<<ans<<endl;
i++;
}
return ans;
}
//


#9

Hi
Thanks a lot for the code
Interviewbit accepted it as a solution with expected run time.
I will go over it to figure out how you did it, and if it is indeed O(N)
Thanks for your contribution


#10

this is not in O(n) but in O(nlog(n))


#11

Here is an o(n) solution, the trick is to reduce this problem to finding sums less than a single number and then use it twice to find the answer:

public class Solution {
    
    public int count(ArrayList<Integer>A, int n, int k){
        int start = 0, end = 0;
        int count = 0;
        int sum = A.get(0);
        while(start < n && end < n){
            if( sum < k ){
                end++;
                if(start <= end){
                    count += end - start;
                }
                if(end < n){
                    sum += A.get(end);
                }
            }
            else{
                sum -= A.get(start);
                start++;
            }
        }
        return count;
    }
    
    public int numRange(ArrayList<Integer> A, int B, int C) {
        
        return count(A, A.size(), C + 1) - count(A, A.size(), B);
        
    }
}

#12

Damn man, Quite logical and easy solution.