I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time. The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication. Let the current state of the $Q$ be the sequence $(s_1,\ldots,s_n)$. I am interested in the product

$$\prod Q = s_1 \cdots s_n.$$

Question: Is it possible to maintain this product in amortized constant time as elements are added and removed?

up vote 7 down vote accepted

A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack.

See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. )


About how to maintain on stacks:

Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one stack, we need to maintain $s_1 s_2 \ldots s_n$; for the other, we need to maintain $s_n\ldots s_2 s_1$. We only consider the first case.

Let $p_k=s_1\ldots s_k$, then $p_n$ is the answer we need.

When pop, simply delete $p_n$ and $s_n$.

When push, $p_{n+1}=p_n s_{n+1}$.

  • 1
    Could you explain how it is easier with two stacks? – Huck Bennett Aug 16 '13 at 5:17
  • 1
    That's so great! I was stuck thinking about complicated tree solutions, so reading this solution was a wonderful surprise. – Geoffrey Irving Aug 16 '13 at 6:47
  • 1
    Thanks @GeoffreyIrving . I threw a gist up. Only gotcha I ran into was that you have to watch the order of multiplication when inserting to the outbox product stack. gist.github.com/chadbrewbaker/6253415 – Chad Brewbaker Aug 16 '13 at 20:52
  • 1
    This seems to require $O(n)$ extra space to store the 'partial products' - is that a necessity of the algorithm or do you know if there are solutions using $O(1)$ additional space? – Steven Stadnicki Aug 17 '13 at 1:05
  • 1
    @StevenStadnicki one can do it with $O(\sqrt{n})$ extra 'partial products' space. Basically only store the partial product from $x_1$ to $x_k$ where $k$ is a perfect square. (and apply some common amortization tricks) – Chao Xu Nov 13 '14 at 2:13

I would memoize the partial products:

{.}{..}{....}{........}{....}{..}{.}

On the incoming end you combine them as they grow to a size equal to their left neighbor. On the outgoing end you spit them in half until you get one element. Amoritized work is log(n) per update to maintain the total product.

  • 1
    If you go to a tree solution, there's no need for amortized complexity: worst case $O(\log n)$ is easy. – Geoffrey Irving Aug 16 '13 at 18:19
  • When you memoize the products like this you take a O(n) hit on the update where the big chunk in the middle gets split apart. – Chad Brewbaker Aug 16 '13 at 20:06
  • Yes, that is why I asked for amortized complexity. The $O(n)$ hit can be charged to insertions to restore $O(1)$ time. – Geoffrey Irving Aug 16 '13 at 20:36
  • 1
    Oh, I see. Yes, your tree solution is only amortized $O(\log n)$ time, but it's easy to make it worst case $O(\log n)$. Give each entry a unique fixed index, make a complete binary tree over all indices, and store only the portion of the tree that overlaps with the current queue. When you want to compute the product, traverse the current portion of the tree, which will have $O(\log n)$ depth. The tree structure changes in at most $O(\log n)$ places for insertions and removals. – Geoffrey Irving Aug 16 '13 at 20:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.