CODEWITHSUNDEEP
pythonpython-3.x
Soham Nathani
Soham Nathani

Reputation: 29

How to find difference in positions of same element in list with O(n) complexity(for all elements)

i have to find the difference in position of same element (for all the elements) in O(n) complexity ? Suppose i have been given the list [1,3,0,1,3,0,1] then difference in position of 1 is 3,3,6 (difference between pair of all ones) for 0 is 3 for 3 is 3

I tried using dictionary to store indices but to find difference i have to iterate over all indices thus increasing complexity

Upvotes: 0

Views: 232

Answers (3)

learner-coder
learner-coder

Reputation: 307

If the given numbers repeat atmost 2 times than hashmap solution is best which will given answer in O(n).

If you have numbers being repeated more than 2 times than you can use hashmap ( element as key and its all indexes as list) and store all the indices of element into it. Now just iterate over the hashmap to calculate difference between all the occurrence (maximum or minimum as asked ).

ex: [1,0,1,3,3,0,1] Output - > [0,2] [3,1] [1,2]

This will take O(n) time iterating over the array and O(m) iterating over the hashmap where m is number of elements being repeated. So basically algorithm will work in linear time. 

def distance(lis,n):
    mp = dict()
    visited = dict() #only to store difference of first and second                               
                     #occurrence  difference
    answer = list()
    for i in range(n):
        if lis[i] in mp and not in visited:
            answer.append([lis[i],i-mp[lis[i]]])
            visited[lis[i]] = 1
        else:
            mp[lis[i]] = i

    return answer #contains number and difference as tuples

In case you want all the difference this is the most optimal case as you need to make pairs thus it cant be done in less than O(n**2).

Check this out for explanation Find all differences in an array in O(n)

def difference(a,n):
    mp = defaultdict(list)
    for i in range(n):
        for j in range(i+1,n):
            if a[i] == a[j]:
                mp[a[i]].append(j-i)
    return mp

Upvotes: 1

Harm Campmans
Harm Campmans

Reputation: 146

Let me start with the fact that the '6' in '3,3,6' is abundant information as it follows from the '3,3' before. So I am not aiming to include this in my output as it increases the output length quadratic over the number of pairs you will find of the same type. You can find all distances for neighbouring '1's in O(n), right? You can also do it for all neighbouring ones, twos and threes (or any fixed/limited number of numbers). You could simply repeat the entire algorithm 3 times. The problem is that you could have 'len(list)' number of different integers in your list and then it is impossible to do so in O(n). In the latter case your bookkeeping/memory would be of size O(n) and as you need to look at every element of your list and access your bookkeeping to request the last index of the identitcal numbers, you would need to access the right information in O(1),which is impossible I guess. Or is there a smart datastructure which allows this?

Upvotes: 0

Scott Boston
Scott Boston

Reputation: 153460

Use pandas and combinations from itertools:

import pandas as pd
from itertools import combinations

l = [1,3,0,1,3,0,1]
s = pd.Series(l)
s.groupby(s).apply(lambda x: [j-i for i,j in combinations(x.index, 2)]).to_dict()

Output:

{0: [3], 1: [3, 6, 3], 3: [3]}

Upvotes: 0

Related Questions