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

help
, ,
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

22

actually we can submit our solution after contest too.

23

How is answer 12?

Pairs:
1,2
1,3
2,3
3,5

24

Also i was thinking if sorting is done can’t we use two pointer approach.

First in the sorted array low will represent a starting position and high will represent the number which is just less than or equal to a[low]+k.
All numbers in range [low,high] will make a pair with low.

25

Each element is also count in subarray too as self-self = 0 <=K

26

Ok my bad I forgot to take screenshot of explaination -

Screenshot_2020-08-01 Coding Ninjas(3)

27

Bro this is actually I did after sort take two pointers but in worst case it will be N2

28

Two pointer in sorted array will be O(N).