2
$\begingroup$

I need to implement data strucure such as array, but with the following interface:

  • GetMin() - Returns the minimum from the array
  • IncRight(index) - Increases all values from specified index to the end of the array by 2
  • DecRight(index) - Decreases all values from specified index to the end of the array by 2

Assuming that the datastructure is already initialized, full of items (which are integers only) and we have already minimum found together with its index. So I "only" need to keep track the changes.

My goal is to all operations have amortized constant time complexity. The question is: Is it possible at all?

Anyway: How to implement such data structure with the best time complexity?

I know one more thing about the initial values: two adjacent values differs only by 1 (plus or minus).

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Is initialized array sorted? How do you access data? After increasing it (or decreasing) how queries look like? What have you tried so far? $\endgroup$
    – Evil
    Sep 28, 2016 at 16:27
  • 1
    $\begingroup$ It is not sorted. But two adjacent values differs only by 1 (plus or minus). I dont know anything about queries, they can be executed in random order and random times. I havent tried so much yet. $\endgroup$
    – Ondra Hrubý
    Sep 28, 2016 at 16:37
  • 3
    $\begingroup$ If you haven't tried much yet, it's premature to ask here. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. meta.cs.stackexchange.com/q/1284/755 might be worth reading as well. $\endgroup$
    – D.W. ♦
    Sep 28, 2016 at 17:09
  • 1
    $\begingroup$ I think we had a very similar question once... ah, this one. $\endgroup$
    – Raphael ♦
    Sep 28, 2016 at 22:20
  • 1
    $\begingroup$ An impending deadline (I assume for an exercise hand-in) is a reason to overhaul your work process, not to ask on the internet. $\endgroup$
    – Raphael ♦
    Sep 28, 2016 at 22:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.