Can I find the max/min value in an unsorted Array in sub linear time?

Question

Is it possible? If not, given an array of size n, how do I know if its better to just sort the array?

Answer 1

With just the unsorted array, there is no way to do this in sub-linear time. Since you don't know which element is the largest and smallest, you have to look at them all, hence linear time.

The best sort you'll find will be worse than that, probably relative to n log n so it will be "better" to do the linear scan.

There are other ways to speed up the process if you're allowed to store more information. You can store the minimum and maximum using the following rules:

• When adding a value to an empty list, set min and max to that value. Constant time O(1).
• When adding a value to a non-empty list, set min or max to that value if appropriate. Constant time O(1).
• When deleting a value from the list, set min or max to 'unknown' if the value being deleted is equal to the current min or max. Constant time O(1). You can also make this more efficient if you store both the min/max and the counts of them. In other words, if your list has seven copies of the current maximum and you delete one, there's no need to set the maximum to unknown, just decrement the count. Only when the count reaches zero should you mark it unknown.
• If you ask for the minimum or maximum for an empty list, return some special value. Constant time O(1).
• If you ask for the minimum or maximum for a non-empty list where the values are known, return the relevant value. Constant time O(1).
• If you ask for the minimum or maximum for a non-empty list where the values are unknown, do a linear search to discover them then return the relevant value. Linear time O(n).

By doing it that way, probably the vast majority of retrieving min/max are constant time. It's only when you've removed a value which was the min or max does the next retrieval require linear time for one retrieval.

The next retrieval after that will again be constant time since you've calculated and stored them, assuming you don't remove the min/max value in the interim again.

---

Pseudo-code for just the maximum could be as simple as:

def initList ():
    list = []
    maxval = 0
    maxcount = 0

In that initialisation code above, we simply create the list and a maximum value and count. It would be easy to also add the minimum value and count as well.

To add to the list, we follow the rules above:

def addToList (val):
    list.add (val) error on failure

    # Detect adding to empty list.
    if list.size = 1:
        maxval = val
        maxcount = 1
        return

    # If no maximum known at this point, calc later.
    if maxcount = 0:
        return

    # Adding less than current max, ignore.
    if val < maxval:
        return

    # Adding another of current max, bump up count.
    if val = maxval:
        maxcount += 1
        return

    # Otherwise, new max, set value and count.
    maxval = val
    maxcount = 1

Deleting is quite simple. Just delete the value. If it was the maximum value, decrement the count of those maximum values. Note that this only makes sense if you know the current maximum - if not, you were already in the state where you were going to have to calculate it so just stay in that state.

The count becoming zero will indicate the maximum is now unknown (you've deleted them all):

def delFromList (val):
    list.del (val) error on failure

    # Decrement count if max is known and the value is max.
    # The count will become 0 when all maxes deleted.
    if maxcount > 0 and val = maxval:
        maxcount -= 1

Getting the maximum is then a matter of knowing when it needs to be calculated (when maxcount is zero). If it doesn't need to be calculated, just return it:

def getMax ():
    # raise exception if list empty.
    error if list.size = 0

    # If maximum unknown, calculate it on demand.
    if maxcount = 0:
        maxval = list[0]
        for each val in list:
            if val = maxval:
                maxcount += 1
            elsif val > maxval:
                maxval = val
                maxcount = 1

    # Now it is known, just return it.
    return maxval

All that pseudo-code uses seemingly global variables, list, maxval and maxcount. In a properly engineered system, they would of course be instance variables so that you can run multiple lists side-by-side.