The questions says assume no duplicates but the example has duplicates
Assume the peak element has no duplicate.
if mid == len(arr) - 1
Why is it guaranteed that if at the very end of array, the value is the peak?
The initial description of mountain array does not match the test and gives the impression that the mountain is symmetrical and claims that the stepping is monotonic. If my understanding is correct, the sequences in the third test case cannot be legitimately described as monotonic. I think you could improve the question by adding a different example in the heading. Nice question, either way.
The array elements monotonically increase from the first element to
A[k], and then monotonically decreases fromA[k + 1]to the last element of the array.
For the third test case [0, 10, 0], both [0, 10] and [10, 0] are monotonic.
mid === arr.length - 1 (line 7; javascript)
it what case does this actually occur?
sorry for the back-to-back message. i understand it now for a sample case - [0, 1, 5].
i think i was getting mixed up calculating with the value at the index instead of the using the index itself.
I understand the purpose is too use binary search. Can someone help me to understand why this “Peak of Mountain” type problem cant be solved doing the following in Python
- Calling max() on the array. peak = max(arr)
- Create a hash map of array values and index. Array values being the “key”. mountain = dict(zip( arr, range(0, len(arr) -1))
- Pull the key ( min(array) ) to get the index. mountain.get(peak)
Would this be frowned upon in a coding interview? Is using the max and zip functions considered shortcuts here with very obvious drawbacks I am missing.
Thanks for any insight.
There’s an issue with this question.
“0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 1 0” is a mountain array by the given definition, however, by using the solution given, it will return 2 (first “2”'s index), however, the answer really should be 16 (first “3”).
Could use some better explanation of why we need mid == arr.size() - 1 in the first check. Adding it helps pass the test case for [0 1 5] but that is also an invalid test case because it is not monotonic as the question specifies.
Thank you for pointing out. We’ve fixed the solution.
The given solution assumes that if you’re on a flat land (consecutive duplicates), we should look to the right (only look to left if arr[mid] > arr[mid+1]). That doesn’t seem like a correct assumption since we could have a case like: “0 1 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0” where the peak is to the left of the flat land. Running this test case with the given solution says the expected output is 16, but it should be 3. Am I missing something?
I don’t think the given solution work for a mountain array ‘0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 1 0’
Hi, the question assume there is only one peak element and no ‘flat land’. “The array elements monotonically increase from the first element to A[k], and then monotonically decreases from A[k + 1] to the last element of the array”
“The array elements monotonically increase from the first element to A[k], and then monotonically decreases from A[k + 1] to the last element of the array” so the question assumes there is no flat land.
Yes, the array should be strictly increasing/decreasing.
The Python solution fails to check the edge case where the “peak” is at the last element of the array; I put this in as a custom test case for my solution and discovered this.
That is not a valid case.
The time complexity of your solution is O(n). Moreover it consumes O(n) memory. Binary search does it in log(n) time with O(1) space.
In fact you solution is slower than the naive solution, which iterate once over the array and finds the peak manually. Even if your solution works, it is very sub-optimal as it is overly complicated so I would not expect a positive feedback during the interview.