Reputation: 193
Does anybody have any idea how to solve the next problem:
We have an array, for example let it be a = {1, 0, -1, -2, -1, 0, 1, 2, 3, 4, 5, 1}.
What the algorithm should find is the size of the smallest difference between indices of the same numbers. In this example (array a) difference of the indices of ones is 6-0=0 and 11-6=5, diff of the indices of zeroes is 5-1=4, diff of indices of minus ones is 4-2=2 and so on. And the algorithm should return 2 because we can see it's the smallest diff of indices of the same numbers.
Is there any way to solve this problem in time complexity better than O(n^2)?
Upvotes: 2
Views: 495
Reputation: 573
Several other answers propose sorting (element, index) pairs which can be done in O(n*logn). However, it is possible to do better, in just O(n) time. There is no need to sort the array, or to keep all the (element, index) pairs, as the minimum can be found greedily.
Loop through the array once and store the last index of each element in a hash.
int smallestDifference(int[] a) {
Map<Integer, Integer> lastIndex = new HashMap<>();
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
if (lastIndex.contains(a[i])) {
minDiff = Math.min(minDiff, i - lastIndex.get(a[i]));
}
lastIndex.put(a[i], i);
}
return minDiff;
}
Insert/get from the hash is O(1) so that gives you O(n) for the whole array.
Upvotes: 3
Reputation: 26121
First, you can add indexes to your sequence (O(N)):
> L = [1, 0, -1, -2, -1, 0, 1, 2, 3, 4, 5, 1].
[1,0,-1,-2,-1,0,1,2,3,4,5,1]
> LI = lists:zip(L, lists:seq(1, length(L))).
[{1,1},
{0,2},
{-1,3},
{-2,4},
{-1,5},
{0,6},
{1,7},
{2,8},
{3,9},
{4,10},
{5,11},
{1,12}]
Then you sort it (O(N log N)):
> LS = lists:sort(LI).
[{-2,4},
{-1,3},
{-1,5},
{0,2},
{0,6},
{1,1},
{1,7},
{1,12},
{2,8},
{3,9},
{4,10},
{5,11}]
Then you find distances of all same values (O(N)):
> LD = (fun F([{X, P1}|[{X,P2}|_]=T]) -> [{P2-P1, X, {P1, P2}} | F(T)]; F([_|T]) -> F(T); F([]) -> [] end)(LS).
[{2,-1,{3,5}},{4,0,{2,6}},{6,1,{1,7}},{5,1,{7,12}}]
Then you find minimal distance (O(N)):
> lists:min(LD).
{2,-1,{3,5}}
It means minimal distance 2 of value -1 between positions 3 and 5 and result complexity is O(N log N). (Example code is in Erlang.)
Upvotes: 1
Reputation: 6727
Make vector<pair<int, int>>
, which would store original vector's values with their respective indices. For each value v whose index is i, add (v,i) to the vector.
Sort the vector (by value then index).
Then go through sorted vector and find the smallest (or largest, if you want) distance between same valued elements.
This takes O(n log n) steps.
Upvotes: 2
Reputation: 41625
This is written in the Go programming language.
func smallestIndexDifference(numbers []int) (mindiff int, exists bool) {
var prev map[int]int // The previous index where this number was found
for i, number := range numbers {
prevIndex, found := prev[number]
if found {
diff := i - prevDiff
if !exists || diff < mindiff {
exists, mindiff = true, diff
}
}
prev[number] = i
}
return
}
This is completely untested, but if it works at all, it works in O(n log n).
Upvotes: 0
Reputation: 2660
The following algo will work in O(nlogn)
1) Make a map of <int,vector<int> > .
2) Let the number be the key and the indexes be the vector.
3) sort the vector for all the keys.
4) Now find the minimum difference for all the difference between indices.
For example : For array 1 2 3 2 1 3
1 -> [0,4]
2 ->[1,3]
3 -> [2,5]
Here we can see that 3-1 = 2 will give the minimum difference in indexes.
Upvotes: 0