CODEWITHSUNDEEP
pythonarrays
Aritra Roychowdhury
Aritra Roychowdhury

Reputation: 11

i want to find out the index of the elements in an array of duplicate elements

a=[2, 1, 3, 5, 3, 2]

def firstDuplicate(a):
    for i in range(0,len(a)):
        for j in range(i+1,len(a)):                
            while a[i]==a[j]:
                num=[j]
                break
    print(num)

print(firstDuplicate(a))

The output should be coming as 4 and 5 but it's coming as 4 only

Upvotes: 0

Views: 94

Answers (2)

Engineero
Engineero

Reputation: 12948

You can find the indices of all duplicates in an array in O(n) time and O(1) extra space with something like the following:

def get_duplicate_indices(arr):
    inds = []
    for i, val in enumerate(arr):
        val = abs(val)
        if arr[val] >= 0:
            arr[val] = -arr[val]
        else:
            inds.append(i)
    return inds

get_duplicate_indices(a)
[4, 5]

Note that this will modify the array in place! If you want to keep your input array un-modified, replace the first few lines in the above with:

def get_duplicate_indices(a):
    arr = a.copy()  # so we don't modify in place. Drawback is it's not O(n) extra space
    inds = []
    for i, val in enumerate(a):
        # ...

Essentially this uses the sign of each element in the array as an indicator of whether a number has been seen before. If we come across a negative value, it means the number we reached has been seen before, so we append the number's index to our list of already-seen indices.

Note that this can run into trouble if the values in the array are larger than the length of the array, but in this case we just extend the working array to be the same length as whatever the maximum value is in the input. Easy peasy.

Upvotes: 1

user2390182
user2390182

Reputation: 73498

There are some things wrong with your code. The following will collect the indexes of every first duplicate:

def firstDuplicate(a):
    num = []  # list to collect indexes of first dupes
    for i in range(len(a)-1):  # second to last is enough here
        for j in range(i+1, len(a)):                
            if a[i]==a[j]:  # while-loop made little sense
                num.append(j)  # grow list and do not override it
                break  # stop inner loop after first duplicate
    print(num)

There are of course more performant algorithms to achieve this that are not quadratic.

Upvotes: 0

Related Questions