SpartanWarrior's blog

By SpartanWarrior, history, 3 years ago, In English

Can someone please help me on how to approach this Problem

Thanking you in anticipation.

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for query you can use sparse table or segment tree

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Hint
Solution
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually am not able to understand with this is O(n). At first glance it seemed O(n^2) to me.

    What I thought was, for every j, the remove function in the tutorial in worst case removes no elements, which is analoguous here to moving the i pointer from j to the start (j times).

    So the no of iterations in the worst case: 1+2+3...n = O(n^2)

    Please let me know if I have made any mistake at any point... Would really appreciate the help...

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In tutorial, we can easily get max/min when adding an element, but it's hard to remove an element.

How does the tutorial solve it?

It uses two stacks to implement the queue, and get the result of max/min from two of the stack to get the result.

Can we just replace it with other merge function?