Can we improve worst time complexity of this question? [Solved]

help
, ,
2

As S_i < 10^5, I think we can use a BIT?

I think this should work:

Code 
BIT bit(MAXA);
for(int i = 0; i < n; i++) {
	ans += bit.get(max(0, A[i] - k), min(A[i] + k, MAXA));
	bit.add(A[i]);
}

[EDIT] The code is for \le k, if you want < k, then modify the query range appropriately.

4 Likes
3

I am confused if sorting will work. But My approach would be contribution towards the sum.

Let’s say we need to find sub arrays which end at i, then this means first element of the subarray must be in range (a[i]-k,a[i]+k)

So you just need to add frequency of these range sum, for that you can maintain a frequency array and find sum in O(log(n)) using segment tree or BIT.

So overall complexity : O(nlog(n))

Algorithm:

for i in range [1,n]:
  ans += range_sum_query(max(0,a[i]-k+1),min(a[i]+k-1, MAX_LIMIT))
  update(a[i],1)
2 Likes
4

Can we do like that ( tell me if I m wrong ) , after sorting for each element by applying Binary search we will find the element X such that abs(X-current element) <=K ,Like this-

So overall complexity is O(nlogn + nlogn )

5

If you are sorting, how will you find subarrays, order must be maintained to find subarrays.

6

Bro we have to count all subarrays whose first and last element difference is less than or equal to K that means simple count all pairs whose abs difference is less than K

3 Likes
7

Shit yeah, this approach makes me feel dumb. I over-engineered a simple solution.

1 Like
8

Lmao , So can I use the approach which I mentioned later ?

9

Makes sense actually, I am looking if there is issue in code. Approach seems fine.

I think this will work fine

sort(all(arr))
long long ans = 0
for(int i = 0; i < n; ++i){
    int index = upper_bound(all(arr),a[i]+k-1) - arr.begin();
    ans += index - i - 1;
}

I think :sweat_smile:

1 Like
10

Yeah HashMap is enough i guess.

11 
Sort array
for  i = 0 to n :
     cnt += (i-max_index_from_0_to_i_such_that(abs(a[i] - a[index]) <=k)) +1
12

How?

13

Wait I will submit and tell u if it is right or wrong.

14

Yes this one seems right too.

1 Like
15

Sorting is predetermining the complexity bound of O(N log(n)).

Suppose if a desired sub-array ends at i. Then we only have to look for no. of times a[i]+k and a[i]-k occurs before i. If the numbers are in range we can create a frequency array, else we can use a HashMap. Either way complexity will be O(n).

EDIT 1: I didn’t read the part less than equal to. Sorry MY bad

1 Like
16

But how do you query a frequency array range sum in O(1)?
It’s not diff = k, it’s diff < k.

[EDIT]. Lol. Alright.

2 Likes
17

WA bro

7
11 5 3 2 25 50 1
3

Your : 4
Expected : 12

18

Yeah i edited my post. Oops i didn’t read it carefully.

19

Please tell me we just didn’t discuss solution to a live test :no_mouth:

1 Like
20

Nope not a live contest bro.
“Coding Ninjas”

I already gave test yesterday that Coding ninja wala test . I got 460 out of 500

21

Cool then :smile: Let me see