O(n) Solution + explanation


#1

The trick here is to calculate the number of continuous subsequences less than (B-1)
and number of continuous subsequences less than ©

then the answer would be : calc© - calc(B-1).

now we change the problem to just find the number of continous subsequences lesser than a given K. we can do that using two pointer :

public int numRange(int[] A, int B, int C) {
    int x = countSubarrayLessThan(A, B - 1);
    int y = countSubarrayLessThan(A, C);
    return y - x;
}

static int countSubarrayLessThan(int arr[], int k) {
    int start = 0, end = 0;
    int count = 0, sum = arr[0];

    while (start < arr.length && end < arr.length) {
        if (sum <= k) {
            end++;
            if (end >= start)
                count += end - start;
            if (end < arr.length)
                sum += arr[end];
        } else {
            sum -= arr[start];
            start++;
        }
    }

    return count;
}

#2

Great solution! thanks


#3

Why count+=end-start and not count++?


#4

@jagzmz
Consider the following:
k = 15 and a subsequence of [1,2,3] in the context of the solution posted
The counts get increased as follows:
count += (1-0 = 1)
count += (2- 0 = 2)
count += (3- 0 = 3)

notice the additional possibilities at each step:
[1] => 1
[1,2] = [2], [1,2]
[1,2,3] = [3], [2,3], [1,2,3]

Since we know that [1,2] is less than 15 then 2 must be less than 15 too
Since we know that [1, 2, 3] is less than 15 then [2,3], [3] must be less than 15 too

I can’t find the math for this. Im not sure if there is a general formula. hopefully someone can post it.


#5

The suggested solution returns 54 for following input:

21 80 97 78 45 23 38 38 93 83 16 91 69 18 82 60 50 61 70 15 6 52 90
99
269

I have 56 sequences as solutions in my Python code:

==> 1 - 177: [80, 97]
==> 2 - 255: [80, 97, 78]
==> 3 - 175: [97, 78]
==> 4 - 220: [97, 78, 45]
==> 5 - 243: [97, 78, 45, 23]
==> 6 - 123: [78, 45]
==> 7 - 146: [78, 45, 23]
==> 8 - 184: [78, 45, 23, 38]
==> 9 - 222: [78, 45, 23, 38, 38]
==> 10 - 106: [45, 23, 38]
==> 11 - 144: [45, 23, 38, 38]
==> 12 - 237: [45, 23, 38, 38, 93]
==> 13 - 192: [23, 38, 38, 93]
==> 14 - 169: [38, 38, 93]
==> 15 - 252: [38, 38, 93, 83]
==> 16 - 268: [38, 38, 93, 83, 16]
==> 17 - 131: [38, 93]
==> 18 - 214: [38, 93, 83]
==> 19 - 230: [38, 93, 83, 16]
==> 20 - 176: [93, 83]
==> 21 - 192: [93, 83, 16]
==> 22 - 190: [83, 16, 91]
==> 23 - 259: [83, 16, 91, 69]
==> 24 - 107: [16, 91]
==> 25 - 176: [16, 91, 69]
==> 26 - 194: [16, 91, 69, 18]
==> 27 - 160: [91, 69]
==> 28 - 178: [91, 69, 18]
==> 29 - 260: [91, 69, 18, 82]
==> 30 - 169: [69, 18, 82]
==> 31 - 229: [69, 18, 82, 60]
==> 32 - 100: [18, 82]
==> 33 - 160: [18, 82, 60]
==> 34 - 210: [18, 82, 60, 50]
==> 35 - 142: [82, 60]
==> 36 - 192: [82, 60, 50]
==> 37 - 253: [82, 60, 50, 61]
==> 38 - 110: [60, 50]
==> 39 - 171: [60, 50, 61]
==> 40 - 241: [60, 50, 61, 70]
==> 41 - 256: [60, 50, 61, 70, 15]
==> 42 - 262: [60, 50, 61, 70, 15, 6]
==> 43 - 111: [50, 61]
==> 44 - 181: [50, 61, 70]
==> 45 - 196: [50, 61, 70, 15]
==> 46 - 202: [50, 61, 70, 15, 6]
==> 47 - 254: [50, 61, 70, 15, 6, 52]
==> 48 - 131: [61, 70]
==> 49 - 146: [61, 70, 15]
==> 50 - 152: [61, 70, 15, 6]
==> 51 - 204: [61, 70, 15, 6, 52]
==> 52 - 143: [70, 15, 6, 52]
==> 53 - 233: [70, 15, 6, 52, 90]
==> 54 - 163: [15, 6, 52, 90]
==> 55 - 148: [6, 52, 90]
==> 56 - 142: [52, 90]

Interestingly the interviewbit expects 59!!!