I have 3 lists:

Added spaces between commas for better understanding of groupby that I'll be using.

a=[1,1,1,1    ,2,2,2    ,3,3,3,3,3,3,    4,4]
b=['l2','l5','l1','l1'    ,'l5','l2',''    , 'l1','l3','l6','l2','l5','l1'  , 'l5','l1']
c=['z','z','a','s'     ,'z','z','a',    's','z','z','a','s','d'  , 's','' ]

In list 'a' I have groups, and according to those groups I want to make changes in my list 'c' with respect to list 'b'.

List 'a' has group of 1s, so for indexes of those 1s I am checking list 'b' and wherever I find string 'l5', I want to make all the further indexes of that group empty string ( '' ) in list 'c'.

For example:

If list 'a' has [1,1,1,1] and list b has ['l2','l5','l1','11']. I want to make indexes after 'l5' i.e. index 2 and 3 empty in list c. Expected output of list c would be:

c= ['z','z','','']

I have written a code for this which works perfectly fine but I think this works in time complexity of O(n^2). Is there any way to optimize this code and and to make this work in O(n) time to make it faster?

Here's my code:

a=[1,1,1,1    ,2,2,2    ,3,3,3,3,3,3,    4,4]
b=['l2','l5','l1','l1'    ,'l5','l2',''    , 'l1','l3','l6','l2','l5','l1'  , 'l5','l1']
c=['z','z','a','s'     ,'z','z','a',    's','z','z','a','s','d'  , 's','' ]

from itertools import groupby
g= groupby(a) 
m=0           
for group,data in g:
    n = len(list(data))   #length of each group
    m =n                  #this stores the sum of length of groups (To get the last index of each group)
    while m:
        h=m-n     #to get the beginning index of each group(total-length_of_currentgroup)
        nexxt=0
        for i in range(h,m):  #this loops for each group (where h is start and m is ending index of each group)
            if b[i]=='l5' and nexxt==0:
                nexxt=i 1
        while nexxt<m and nexxt!=0:
            c[nexxt] = ''
            nexxt =1
        break
print(c)

Output:

['z', 'z', '', '', 'z', '', '', 's', 'z', 'z', 'a', 's', '', 's', '']

Is there any way to write this in O(N) time?

CodePudding user response：

Yes, it is possible to optimize this code and make it run in O(n) time. The key to doing this is to avoid using nested loops, which can be time-consuming as the size of the input increases.

One way to optimize this code is to use a dictionary to store the group number and the index of the last occurrence of the string 'l5' in the corresponding group. Then, we can iterate over the list c once and check if the current index is greater than the stored index of the last occurrence of 'l5' in the corresponding group. If it is, we can set the current element in c to an empty string.

Here is an example of how this could work:

# Create a dictionary to store the group number and the index of the last occurrence of 'l5'
last_index = {}

# Iterate over the groups in 'a'
for group, data in groupby(a):
  # Get the length of the current group
  n = len(list(data))
  
  # Iterate over the elements in 'b' for the current group
  for i in range(m, m   n):
    # If the current element in 'b' is 'l5', update the last_index dictionary
    if b[i] == 'l5':
      last_index[group] = i
  
  # Increment the current index
  m  = n

# Iterate over the elements in 'c'
for i in range(len(c)):
  # If the current index is greater than the stored index of the last occurrence of 'l5' in the corresponding group, set the element to an empty string
  if i > last_index.get(a[i], 0):
    c[i] = ''

# Print the updated list 'c'
print(c)

This code should run in O(n) time because we only iterate over the lists a and b once each, and we only iterate over the list c once.