CODEWITHSUNDEEP
algorithmtime-complexity
user7461251
user7461251

Reputation:

time omplexity of finding two indices of same element in an array

I am trying to design an algorithm to find indices of two same element in an array. The input is an array and the output is two indices i & j such that array[i]=array[j]. time complexity must be O(nlogn).

here is what I tried

let i=0 to size_of_array{
    let j=i+1 to size_of_array{
        if array[j]=array[i]{
            print(i, j)
        }
    }
}

Nested loop is O(n^2), but if I try to design like this. what the time complexity would be?

n is the size of array my implementation would run O(n[(n-1)+(n-2)+(n-3)....+1]) times. Does it still O(n^2),Someone told me it is O(nlogn), why?

Upvotes: 0

Views: 73

Answers (3)

jgroenen
jgroenen

Reputation: 1326

You could use a map for inverse lookup

function findSame(theValues) {
  var inverseLookup = {};
  var theLength = theValues.length;
  for (var i = 0; i < theLength; ++i) {
    if (inverseLookup[theValues[i]] != undefined) {
      return ([inverseLookup[theValues[i]], i]);
    }
    inverseLookup[theValues[i]] = i;
  }
  return [];
}

console.log(findSame([1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9]));

for loop has O(n) time + inverseLookup has O(1) time + O(n) space (hash table)

Upvotes: 0

FabioL
FabioL

Reputation: 999

You can keep two array: one with the values (A) and one with the indices (I). A possible O(nlogn) algorithm could be:

  1. Sort values array A in parallel with index array I. (Time complexity: O(nlogn)).
  2. Scan A and compare every elements with its right neighbor, if a duplicate is found you can return the corresponding index in I. (Time complexity: O(n))

I implemented this idea in a python function:

import operator

def repeatedNumber(A):
    if len(A) <= 1:
        return -1

    # building the indices array
    indices = range(len(A))

    # join the two arrays
    zipped = zip(A, indices)

    # sort the arrays based on value
    zipped = sorted(zipped, key=operator.itemgetter(0))

    # scan the array and compare every pair of neighbor
    for i in range(len(zipped)):
        if zipped[i][0] == zipped[i + 1][0]:
            return zipped[i][1], zipped[i+1][1]


    return -1

You can try with some examples:

  • For A = [2,3,5,2,6] give (0, 3)
  • For A = [2, 3, 100, 6, 15, 40, 7, 3] give (1, 7)

Upvotes: 1

OmG
OmG

Reputation: 18838

As you know the time complexity of your algorithm is O(n^2). To get a better result you can sort the array first and then find the indices.

If you sort the array, two indices with the same value could be located beside each other. Hence, you can iterate over the sorted array, and report their original index of the two current neighbor indices in the sorted array.

The time complexity of sorting could be O(n log n) and then iterating over the array is O(n). Hence, this algorithm is O(n log n).

Upvotes: 0

Related Questions