Reducing nested-loops of a python question on array

intially you can create a dictiory of unique number and append all the index of each number and then in second loop you can get the diffrence of each integar.

for _ in range(int(input())):
    num=int(input())
    a=list(map(int,input().split()))[:num]
    sum=0
    nums = {}
    for i in range(len(a)):
        j=a[i]
        if j not in nums:
            nums[j] = []
        
        nums[j].append(i)
    
    for key in nums:
        sum += abs(nums[key][-1] - nums[key][0])
    print(sum)

This answer uses the same reasoning as others: that is storing the indices as a list of values in a dictionary, but uses a few built-in functions and methods to reduce code and make it 'cleaner'.

In [11]: array = [1, 2, 3, 3, 2]

In [12]: indices = {}

In [13]: for ix, num in enumerate(array, start=1):
    ...:     indices.setdefault(num, []).append(ix)
    ...:

In [14]: total = 0

In [15]: for num, ixes in indices.items():
    ...:     if len(ixes) == 1:
    ...:         continue
    ...:     else:
    ...:         total += abs(ixes[-1] - ixes[0])
    ...:

In [16]: total
Out[16]: 4

enumerate is a function that creates a sequence of tuple pairs from a given sequence like a list. The first element is an "index" (by default, set to 0, but you can start from any integer) and the second is the actual value from the original sequence.

setdefault is a method on a dictionary that returns the value for a given key, but if that key doesn't exist, inserts the key and sets as its default value the item passed in as the second parameter; in this case, it's an empty list to store the indices.

items is again a method on dictionaries with which one can loop through one key-value pair at a time.

Sounds like hackerrank. As usual, most of the provided information of the problem is irrelevant and can be forgotten as soon as seen.

You need:

• the index when an element occures first: you add it as negative to the total and put it into the dictionary
• if the value is already in the dict, update the position only
• at the end you sum all values of the dict and add it to your summation

Code:

num = 5
a = list(map(int,"1 2 3 3 2".split()))
s = 0
d = {}
for idx, num in enumerate(a):
  if num not in d:
      s -= idx
  d[num] = idx
  
print(s+sum(d.values()))

Output:

4

This uses a dictionary and strictly 2 loops - one over the n given numbers and one over u distinct numbers inside it if you ignore the int-conversion step wich already loops once over all of them.

Space:

• the total sum and 1 index for each unique number which makes it worstcase O(n+1) in space (each number is also unique)

Time:

• normally you get O(n + u) wich is less then the worst case (all numbers are unique) which would be O(2*n). 2 is only a factor - so it is essentially O(n) in time.

If you still have time-problems, using a collections.defaultdict(int) should be faster.

Solution 1 (dict): One way to it is by using a dictionary for each item, saving all indices and get the difference of last and first occurence for each item. See below:

def get_sum(a):
    d={i:[] for i in set(a)}
    for i in range(len(a)):
        d[a[i]].append(i)
    sum=0
    for i in d.values():
        sum+=i[-1]-i[0]
    return sum
   

Solution 2 (reversed list): Another way is to use the reversed list and use list.index(item) for both original and reverse list and get the difference. See below:

def get_sum2(a):
   m=a[::-1]
   return sum(len(m)-m.index(i)-1-a.index(i) for i in set(a))

Output:

>>>get_sum([1,2,3,3,2])

4

>>>get_sum2([1,2,3,3,2])

4