## Find a number in an array

Question

Is there a solution for the following question that has O(n) efficiency?

You need to find a cell in an array such that all of the numbers before it are lower than it, and all the numbers after it are higher than it. You should ignore first and last cells.

For example, consider the following list:

```
1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11
```

In that case, the answer would be the number `7`

at index `5`

.

Show source

## Answers ( 5 )

Yes, it certainly

canbe done in`O(n)`

time. A couple of methods follow.The first one is more useful to find

allcandidate cells. Make a single`O(n)`

pass of the data setting two extra items per cell, hence`O(n)`

space (a non-trivial number of optimisation problems can be solved by trading space for time).The two items you need to calculate for each cell are the highest value to the left and the smallest value to the right. The first pass sets these items for all cells bar the one at the end where it doesn't make sense (pseudo-code obviously):

Then it's a simple matter of checking every cell (bar the first and last) to ensure that the value is both greater than (this answer assumes, as per your question, that "higher/lower" is

literal, not "greater/less than or equal to") the highest on the left and less than the lowest on the right:You can see the results of the initial pass below:

The

onlycandidate cell where the value is ordered (non-inclusive) with respect to the two values above and below it, is the`7`

marked with`^`

.Now keep in mind that's a relatively easy-to-understand solution that can find

multipleitems that satisfy the constraints. Given that you only needoneitem, it's possible to get better performance (though it's still O(n)).The basic idea is to traverse the array from left to right and, for each cell, you check whether everything on the left is lower and everything on the right is higher.

The first bit of that is easy since, by traversing left to right, you can remember the highest value encountered. The second bit seems to involve looking into the future somehow but there's a trick you can use to avoid this "temporal gymnastics".

The idea is to maintain both the highest value seen on the left of the current cell

andthe index of the current answer (which is initially set to a sentinel value).If the current answer is the sentinel value, the first cell that satisfies the "is greater than everything on the left" is chosen as the possible answer.

And, as long as that remains the case, that's the cell you opt for. However, as soon as you find one less than or equal to it on its right, it's no longer valid so you discard it and start searching again.

This searching happens from the

currentpoint, not back at the start, because:alreadyfound a lesser or equal cell; andnocell in that range is valid, they'reallgreater than or equal to this one.Once you've finished processing the non-end items, your answer will either be the sentinel or a cell that

almostsatisfies the constraints.I say "almost" because there's one final check required to ensure that the final item is greater than it, since you performed no checks on that item as part of the traversal.

Hence the pseudo-code for that beast is something like:

Since my pseudo-code is (heavily) based on Python, it's a fairly simple matter to provide a more concrete example of the code in action. First, the "find every possibility" option:

And the second, slightly more efficient option, but only able to find one possibility:

The output of both of those (though the latter example only shows the final line) shows basically what the pseudo-code was meant to illustrate:

Create one additional array that is calculated by going left to right on the source array. For any index N in this array, the value is the highest value observed between 0:N-1 in the first array.

Now create a second array that is formed by scanning from right to left where any value at index N represents the lowest value seen between N+1:end

Now you've basically got three arrays:

Now you just want to scan all three arrays together until you find an index where this condition holds true:

Code:

This is O(N) time.

This has

O(n) for both Time and Space Complexity and a single array Pass.Logic :Code :PS : From my analysis I feel this should be enough and work for all cases. Not sure if any case is missed out.

Here is an

O(n), one pass solution in Python. Port to Java is trivial:You'll need to run it a few times to generate a list that actually satisfies the condition.

DescriptionRestating objective: find index

iof an element in an arrayAsuch thatall A[j], j < i => A[j] < A[i] and all A[k], k > i => A[k] > A[i]. The first such element is one such element so we just find the first one.Given an index

x, ifxsatisfies the above condition thenA[x] > A[0..x-1] and A[x] < A[x+1..A.length]. It's sufficient to verify both those constraints for a givenx. NoteA[x] > A[0..x-1] <=> A[x] > max(A[0..x-1]). So we maintain the max value seen so far, find the firstxsatisfying condition 1 and iterate through the array verifying condition 2 is satisfied. If condition 2 is ever not validated we know the next possible candidate is beyond current index,y, becauseA[x..y-1] > A[x] => A[y] < A[x..y-1], and is greater than the max value seen so far.I wrote an implementation in

`c`

using the algorithm from`S.Pinkus`

's answer, with debugging information.## Code

find_mid_num.c:Compile:`gcc -Wall find_mid_num.c`

Execute:`./a.out`

Running result:TODO - Further improvements: