Efficient way to find the max number in an array

Question

This is an interview question There is an array of integers. The elements in the array can follow the following patterns.

1. numbers are in ascending order
2. numbers are in descending order
3. numbers increases in the beginning and decreases in the end
4. numbers decreases in the beginning and increases in the end

What is the efficient way to find the max number in the array?

• ChrisC: Are you after one way of handling all four possibilities, or four separate approaches?
• cppcoder: I was rather trying hard to find a generic way for all these patterns.Later the interviewer said, first find out the pattern and then find the max.

Answer 1

In that case, all you need to do is to determine whether it's (3). If not, the answer is max(first, last).

In the case that all elements are equal, you'll need to exhaustively search the array to show that there's not one high number somewhere in the middle. So I think it's O(n) to determine whether you're in (3).

• PengOne: +1: Yes. This is my solution but checking for case 3 first, which is more elegant I agree.
• Tony Delroy: Worth checking with the interviewer whether contents like "42" or "42 42" are even possible... they might not be classified as trivially ascending or descending for the purposes of the question, and there's certainly no increasing or decreasing going on....
• Patrick: It only needs to take O(log n) to determine whether you are in (3). See my answer: stackoverflow.com/questions/6742316/…
• Patrick87: How can you know whether you have 100 "7"s in a row or 99 "7"s split by an eight somewhere without eventually checking all 100 (n) numbers? You can't. If these are strictly increasing/decreasing, your O(log n) answer makes sense.
• Patrick: @Thomas I see what you are saying. Your algorithm does not have to inspect all of the list elements to determine if the maximum is in the middle. I guess I just assumed that this was a question about asymptotic efficiency as opposed to an optimization question. I didn't mean to say that your answer is trivial, I just meant that it would be trivial to find an O(n) solution.

Answer 2

Well, case by case you have

1. The last number.
2. The first number.
3. Move from beginning to end, stopping at first descent and printing previous number.
4. Compare first and last numbers.

If you don't know which case you're in, then you can test this while finding the max by doing the following (in C-like pseudocode):

for (int i=0; i<end; ++i) {
 if (array[i] < array[i+1]) {
 // CASE 1 or 3
 for (int j=i+1; j<end; ++j) {
 if (array[j] > array[j+1]) {
 // CASE 3
 return array[j];
 }
 }
 // CASE 1
 return array[end];
 }
}
// CASE 2 or 4
return max(array[0],array[end]);

• James McNellis: (3) does not require a linear search; a modified binary search for the inflection point will do.
• Ateş Göral: For 3, optimistically starting scanning at the middle will be more efficient (check middle element against adjacent elements and apply funky logic).
• hatchet - done with SOverflow: Determining which case it is may be an significant part of the problem. What if you have an array of 100 elements that all have a value of 1, then 2 for the 101st element, then another 100 1's?
• hatchet - done with SOverflow: pseudocode is not right. Consider 4, 5, 4, 2, 1 (case 3). Array[0] > Array[end], you'll return 4, but max is 5
• Patrick87: Indeed. See my solution. I think exhaustive search is required in the worst case of (3), if repeats are allowed.

Answer 3

You will be able to determine with type of array it is by inspecting the first two and last two elements

1. It is the last element
2. It is the first element
3. see below
4. It is the larger of the first and last elements

For 3, start by looking at two elements at the middle of the array, if they are still increasing the max is higher in the array, if they are decreasing, the max is lower in the array. Repeat in a binary search fashion

• Tony Delroy: "by inspecting the first two and last two elements"... trivial, but sometimes you only need to inspect 3 of those... e.g. "1 ... 6 5" must be case 3, "1 -1 ... 2" must be case 4.
• PengOne: But what if there are repeated elements? For example, the sequence 1,1,2,1,1

Answer 4

Since cases 1-3 all have one peak (value surrounded on both sides by values lower than itself or the edge of the array), and case 4 has two peaks both on the ends of the array, this problem can be solved rather simply in O(log n) time for all cases:

First, apply the 1D peak finding algorithm to find a peak in the array.

If the peak occurs in the middle of the array (not the first or last position), then this is case #3, and the peak is also the maximum.

If the peak is either the first or last element of the array, then this is one of cases 1, 2, or 4, and the array max is max(first, last).

Python-esque pseudo code:

def find-peak(list):
 mid=len(list)/2
 if (list[mid-1] > list[mid]:
 return find-peak(list[:mid-1])
 else if (list[mid+1] > list[mid]:
 return find-peak(list[mid+1:])
 else:
 return mid
def find-max(list):
 peak = find-peak(list)
 if peak==0 or peak==len(list)-1:
 return max(list[0], list[-1])
 else:
 return list[peak]

Answer 5

1.the last number 2.the first number 3.do binary-like search, pick a pivot,calculate the slope, just to decide next to go left or right 4.first or last number

Answer 6

The way to identify the four cases is straight forward if we assume the sequence do not have repeating number:

case 1: arr[0] < arr[1] && arr[end-1] < arr[end]
case 2: arr[0] > arr[1] && arr[end-1] > arr[end]
case 3: arr[0] < arr[1] && arr[end-1] > arr[end]
case 4: arr[0] > arr[1] && arr[end-1] < arr[end]

As mentioned in other answers, the way to find the max is straight forward too:

case 1: arr[end]
case 2: arr[0]
case 3: binary search, until found n that arr[n-1] < arr[n] > arr[n+1]
case 4: max(arr[0],arr[end])

Answer 7

The answer depends on what is meant by "efficiency." If you want fast code, look at someone else's answer. If you want to be efficient as a programmer you should probably just use a library call (like max_element() in C++.)

Answer 8

This problem reminds me of the Golden section algoritm for finding the minimum of an unimodular (ie.: decreasing then increasing) function. It is kind of a souped-up version of binary search that calculates the value of the function (ie.: inspects the array) in as few points as possible.

All you need to do now is translate it into a discrete version and add nome extra whistles to determine wether the function is concave or convex.