Given an sorted array = {1, 2, 3} provide getMin() method which returns minimum element and increment it by 1.

getMin(): return 1 and increment the min no by 1, array = {2, 2, 3}
getMin(): return 2 and increment the min no by 1, array = {3, 2, 3}
getMin(): return 2 and increment the min no by 1, array = {3, 3, 3}
getMin(): return 3 and increment the min no by 1, array = {4, 3, 3}

Any solution with time complexity O(1)?

CodePudding user response：

Simple way:

In addition to the sorted array, maintain a queue of integers (initially empty).

To implement the getMin() operation:

1. Take the smaller of next element in the array, or the element at the front of the queue.
2. Add 1 and put it at the end of the queue.

You may then notice that there are at most 2 different values in the queue at any time, so you can replace it with a few variables.

CodePudding user response：

We have two states for the array: either (1) the array is sorted, or (2) we have just incremented the first of a group of the smallest element.

If we have a smaller element ahead of a larger element, we increment the smaller element and maintain both (adjacent) pointers. If the next element is smaller, we advance both (adjacent) pointers; otherwise, move the pointers again to the start of the array since it is again sorted.

1 2 3
^ ^

2 2 3
^ ^

3 2 3
^ ^

3 3 3
^ ^

4 3 3
^ ^

4 4 3
  ^ ^
  
4 4 4
^ ^