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
Nice approach, I got to learn something new from it.
Is
prev
on 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.
similar leetcode problem
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.
I rename k the thing you call "n" in the problem description. I assume k <= n (n is the size of the array in the code below).
You can go from L to R and keep track in a set of pair of {val, idx}. As soon as the loop index i is i >= k you start look backward in the array. The goal is to find the already seen number so that it is as close as possible to a[i] and has an index j<=i-k. I did this thing with binary search lower bound. When doing lower bound you either find and element greater than a[i] or equal. So if you find equal the answer is 0 and you are done, if you find a greater one, you go one step below with the set iterator and check also this case to be compared with the current a[i]. When doing binary search on set of pair i look for the pair {a[i], -inf} which basically is I want the index as small as possible, but this part smells a bit, maybe there is a better way.
I leave a code snippet. Maybe its buggy, but I am pretty sure about the idea. Also there is most likely a better way of retrieving this element than doing lower bound, but I don't know such a method, if somebody knows I would be pleased to know it.
[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).
I actually don't know how to even implement it I just know the complexity and something like that exists, I really don't understand why people downvote, if the stuff doesn't work then comment so it will help both sides, thanks for the advice.
Well maybe this can work for you, I reworded the problem and used the solve function for at least 'k' indexes apart. First we preset the map from kth index onwards in the array as preprocessing and initialize r = k and l = 0. In a loop can find the lower and upper bound for each element and check from their differences to update the answer, we delete element from the r-th index next as it's no longer valid next iteration and erase it from the map if it's frequency becomes 0, and we also add the l-th index element if it's valid next iteration (increment l along with it), increment r and move on solving it. This approach uses Two Pointers and Ordered Maps, hope this helps: