I have a list of numbers and I want to subtract every number from the smaller value after it but with the lowest possible complexity I have the list [7, 18 ,5 ,5 ,20 ,9 ,14 ,7 ,19]
The first lower value after 7 is 5 so it will subtract 7 from 5, the same for 18 the first lower value after it is 5, so it will subtract 18 from 5 and so on.
The output should be [2, 13, 5, 5, 11, 2, 7, 7, 19]
I have written a code that solves the problem but with O(N^2), but I was wondering if I could solve it with lower time complexity
l1=[7,18,5,5,20,9,14,7,19]
l2=[]
for i ,j in enumerate (list1):
k=0
for n in list1[i+1:]:
if n<j:
l2.append(j-n)
k=1
break
if k==0:
l2.append(j)
print(l2)
Advertisement
Answer
I am not sure what complexity this exactly is but it is not O(n^2)you can try this. You can use a stack.
list1=[7,18,5,5,20,9,14,7,19]
stack = [(0, list1[0])]
res = [0] * len(list1)
for idx, i in enumerate(list1[1:], 1):
while stack and stack[-1][-1] > i:
old_idx, old_i = stack.pop()
res[old_idx] = old_i - i
stack.append((idx, i))
for idx, i in stack:
res[idx] = i
print(res)
Output
[2, 13, 5, 5, 11, 2, 7, 7, 19]
Benchmark using %%timeit -n 10 -r 10 in jupyter, input list has been increased to show the efficiency.
list1=[7,18,5,5,20,9,14,7,19]
for _ in range(10):
list1 += list1
This Solution
2.06 ms ± 37.1 µs per loop (mean ± std. dev. of 10 runs, 10 loops each)
Original Code
209 ms ± 2.71 ms per loop (mean ± std. dev. of 10 runs, 10 loops each)
This solution is faster.
Edit according to @JérômeRichard comment this runs in linear time O(n).
This is O(n). Here is the proof: you cannot append more element to the stack than the number of element in the input list because of the append. You cannot remove more element from the stack than the number of appended elements. Both pop and append are (amortized) O(1) operations. Then final loop is running in O(n)
Commented Version for Better Understanding
list1=[7,18,5,5,20,9,14,7,19] # input list
# create an unbounded stack
# `stack` will have a tuple of elements in the form (index, value)
# add the first element in the input list to the stack along with the index
stack = [(0, list1[0])] # (index, value)
# result list to store the result
# size will be the same as that of the input list `list1`
res = [0] * len(list1)
# start iterating the rest of the elements `list1[1:]` as the first element is already in the stack
# start enumerate index from 1
for idx, i in enumerate(list1[1:], 1):
"""
how the while loop works
check if stack is not empty and if the top element in the stack `stack[-1][-1]` is greater than the current element `i`
if this condition is `True`, it essentially means that `i` is the right most minimum element for the top element in the stack
stack[-1] is the top element of the stack, so `stack[-1][-1]` will give the value of the top element in the stack
remember every element in `stack` is a tuple of form (index, value), the value `stack[-1][-1]` is needed to compare, index `stack[-1][0]` is used later
both these checks are constant time operations `O(1)`.
"""
while stack and stack[-1][-1] > i:
# pop the top element and get the old index and old value as `old_idx` and `old_i`
old_idx, old_i = stack.pop()
# subtract old element `old_i` with current element `i`
# `old_idx` is the index where the result of the above operation must be placed
# assign the result to the `old_idx`
res[old_idx] = old_i - i
# add the current element and its index in the stack for comparing that in next iteration
stack.append((idx, i))
# if there are any elements remaining in the stack then these elements do not have a minimum value to their right
# so just get their index and set the corresponding value in the `res` list, that will be their position
for idx, i in stack:
res[idx] = i
# result :)
print(res)