anicicn
anicicn

Reputation: 193

Algorithm for finding the smallest index difference of equal numbers in array

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

Answers (5)

BKE
BKE

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

Hynek -Pichi- Vychodil
Hynek -Pichi- Vychodil

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

user31264
user31264

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

Roland Illig
Roland Illig

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

Priyansh Goel
Priyansh Goel

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

Related Questions