How can i improve time complexity of my python code?

Question

the goal of my code is encode numbers by adding each number to the next bigger number and if no bigger number was found i use the same number. [4,3,7,3,2,8,6,1,10,3] =>[11,10,15,11,10,18,16,11,10,3]

my code's time complexity is O(n²) and i think i can do O(n log n) i dont know tho what kinda algorithm should i use since i also want to find the first bigger element

i did try binary search but i realized that it goes from the middle not the first.

import queue 
q= queue.Queue()
a=[4,3,7,3,2,8,6,1,10,3]
for i in a:
    q.put(i)
encoded=[]
while q:
    current=q.get()
    for i in range(q.qsize()):
        if current<q.queue[i]:
            encoded.append(q.queue[i]+current)
            break

print(encoded)

Answer 1

Here is tree-based solution, If I count right should be O(n log n): sorted is O(n log n) + searching in tree is O(n log n) too:

class Tree:
    def __init__(self, index, value):
        self.index = index
        self.value = value
        self.left = None
        self.right = None

    def add(self, index, value, current_data=None):
        if index < self.index:
            if value < self.value:
                current_data = self.index, self.value

            if self.left is not None:
                return self.left.add(index, value, current_data)
            else:
                self.left = Tree(index, value)
                return current_data
        else:
            if self.right is not None:
                return self.right.add(index, value, current_data)
            else:
                self.right = Tree(index, value)
                return current_data

l = [4, 3, 7, 3, 2, 8, 6, 1, 10, 3]

a = sorted(enumerate(l), key=lambda k: k[1])[::-1]

root = Tree(a[0][0], a[0][1])
out = [None] * len(l)
out[a[0][0]] = a[0][1]

for idx, val in a[1:]:
    x = root.add(idx, val)
    if x is None:
        out[idx] = val
    else:
        out[idx] = val + x[1]

print(out)

Prints:

[11, 10, 15, 11, 10, 18, 16, 11, 10, 3]

---

l = [5, 3, 4, 7]  

# Output:
[12, 7, 11, 7]


l = [5, 3, 3, 4, 7, 6, 5, 6, 7, 6, 5]

# Output:
[12, 7, 7, 11, 7, 13, 11, 13, 7, 6, 5]

Answer 2

Here is an answer using the sortedcontainers module.

The idea is to work from the end to the start, and keep track of seen values in a sorted data structure which we can easily query to find the next biggest value.

from sortedcontainers import SortedList
l = [5, 3, 4, 7, 3, 2, 8, 6, 1, 10, 3]

seen = SortedList()
# Initialize an array of the right length.
answer = [None for _ in l]
# This counts down from the end of the array.
for i in range(len(l)-1, -1, -1):
    # bisect_right gives the last place in seen where this value
    # could go while maintaining order. What's there right now,
    # if anything, is the next biggest value.
    j = seen.bisect_right(l[i])
    if j == len(seen):
        # There is no next biggest value.
        answer[i] = l[i] + l[i]
    else:
        # There is a biggest value.
        answer[i] = l[i] + seen[j]
    # Register l[i] as possibly next biggest.
    seen.add(l[i])
print(answer)

Answer 3

New solution

O(n) solution with a monotonic stack. Go through the numbers, keep track of the indices that haven't seen a bigger value yet. Naturally their values are non-increasing, and we can handle them as a stack.

a = [4,3,7,3,2,8,6,1,10,3]

encoded = a[:]
s = []
for i, x in enumerate(a):
    while s and x > a[s[-1]]:
        encoded[s.pop()] += x
    s.append(i)

print(encoded)

Attempt This Online!

The 4 and the 3 (or rather their indices, but let's talk in terms of the elements) just go onto the stack, waiting for something bigger. Then the 7 is bigger, gets added to the 3 and the 4, pops them off the stack, and goes onto the stack itself. The next 3 and 2 just go onto the stack. Then the 8 gets added to the 2, 3 and 7, pops them off the stack, and goes onto the stack itself. (If the 8 had been 5, it would only add to and pop the 2 and the 3.) And so on.

Note that the inner loop runs at most n times overall. It pops, and you can't pop more than you append, which is n times.

Old solution

O(n) solution with a monotonic stack. Go backwards. For example, after processing 8,6,1,10,3 (backwards), the only possibly still relevant numbers are the 8 and the 10. All other numbers can never be the next bigger number for any earlier number. For example if the 6 is bigger than some earlier number, then the 8 is bigger as well, and it's earlier. So keep track of just all those possibly still relevant numbers in a stack. After those five numbers, the stack is s = [10, 8].

a = [4,3,7,3,2,8,6,1,10,3]

encoded = []
s = []
for x in reversed(a):
    while s and x >= s[-1]:
        s.pop()
    encoded.append(x + s[-1] if s else x)
    s.append(x)
encoded.reverse()

print(encoded)

Attempt This Online!

(Testing both solutions with each other on a long random input)

Answer 4

Here's a description of what you could do:

• Start with input [4, 3, 7, 3, 2, 8, 6, 1, 10, 3], which will be processed from the end.
• There will be an ascending sequence of large numbers that is initially empty. Let's say lookup = [].
• Look at the last element 3 from the input. There is no larger number in lookup, so this element remains unchanged. The value 3 is added to lookup, which is now [3].
• Look at the next element 10 from the input. There is no larger number in lookup, so this element remains unchanged. The value 10 is added to lookup but all smaller ones are discarded, making it [10].
• Look at the next element 1 from the input. The first larger number in lookup is 10, so that value changes to 1+10. The value 1 is added to lookup, making it [1, 10].
• Look at the next element 6 from the input. The first larger number in lookup is 10, so that value changes to 6+10. The value 6 is added to lookup but all smaller ones are discarded, making it [6, 10].
• Look at the next element 8 from the input. The first larger number in lookup is 10, so that value changes to 8+10. The value 8 is added to lookup but all smaller ones are discarded, making it [8, 10].
• Look at the next element 2 from the input. The first larger number in lookup is 8, so that value changes to 2+8. The value 2 is added to lookup, making it [2, 8, 10].
• ...

Now, let's look at the various steps in detail:

• Going through the input sequence is clearly O(n). This part is trivial and unavoidable.
• The next part is handling of the lookup list of larger numbers. There are multiple steps involved:
  • The first part is searching for a larger number than the current element. On an array (Python's list), that would be an O(log n) operation when implemented as binary search.
  • The next part is removing all elements less or equal to the current element from the lookup list. This part is easy, since we just determined the position of the first element to keep in the previous step. The key here is that this needs an array where elements at the front can quickly (O(1)) be removed. The easiest way is to use an array and just maintain a start index. In Python, this is a bit tricky, because its list type simply doesn't allow cheap removal from the front. As a simple workaround, just inverse the order of this sequence for the algorithm, so you can remove them from the back, which is cheap.
  • The last part is to add a new element to the front. This also must be implemented in O(1) complexity. Again, Python's list isn't great at this, unless you turn it around.

In summary, you get an algorithm that performs n times three operations with O(log n), O(1) and O(1) complexity. This is therefore O(n log n + 2n) or simply O(n log n).