Find minimum absolute difference between 2 elements in an array that are at least n indices apart.
Example 1: num = [1, 1, 1, 1, 3, 3, 3, 3, 4, 4, 4, 6, 6, 6, 11, 11, 11, 11] n = 5 The answer should be 1
Example 2: num = [24, 1400, 1900, 1200, 98, 89, 123, 27] n = 2 The answer should be 3
I got the naive solution to this problem, not sure what the optimize solution should be I was wondering whether someone else would be able to show me how to solve it.
Multiset is enough.
Why do you need a multiset? A set could be enough
Is
prevon set iterators O(1)? I thought iterator operations like that on set iterators could be slow in the worst case.Actually nvm, iterator operations on set iterators are linear (https://cplusplus.com/reference/iterator/prev/) but we're only moving 1 element so it's O(1). It's the same deal as when you do
That
it++is O(1) each time.i think min suffix array will work
Yeah that is better than multiset.
no it is wrong
works for max
Let the size of the array be len.
So, for the 0th index, it can club to all the indices from n to len-1. Maintain a multiset for that and then find the lower and upper bound of the A[i] and maintain the answer. After every iteration remove the A[i+n] element from the multiset.
Sorry for my bad English.
If you choose some number, then it's best pair is either the minimum element that it can pair with or the maximum. Now start from the $$$n$$$'th element. It can pair up with element $$$0$$$. Element $$$n+1$$$ can pair with $$$0$$$ and $$$1$$$, $$$n+2$$$ with $$$0$$$, $$$1$$$ and $$$2$$$, ... . Now you can just hold the minimum and maximum for that prefix and update the answer as necessary. Time complexity $$$O(N)$$$ where $$$N$$$ is the size of the array, auxilary memory $$$O(n)$$$ where $$$n$$$ is the number in the problem.
This doesn't always work. For example : array = [1 2 3 4 5 2], n = 3 The minimum absolute difference is abs(2-2)=0. However, when you arrive at the second 2 then the minimum value is going to be 1 and the maximum value is going to be 5.
I'm sorry, I misread minimum for maximum in the problem statement.
[Deleted maybe my approach was wrong]
Don't learn topics much higher than your CP skills. Even if you understand how it works, you won't be able to apply it correctly in real problems nearly always(unless the problem is a very standard problem).