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
| java   | arrays   | algorithm   2016-12-23 02:12 5 Answers

Answers ( 5 )

  1. 2016-12-23 02:12

    Yes, it certainly can be done in O(n) time. A couple of methods follow.

    The first one is more useful to find all candidate 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):

    # Set current values.
    
    highLeftVal = cell[0]
    lowRightVal = cell[cell.lastIndex]
    
    # For running right and left through array.
    
    rightIdx = cell.lastIndex
    for each leftIdx 1 thru cell.lastIndex inclusive:
        # Left index done by loop, right one manually.
    
        rightIdx = rightIdx - 1
    
        # Store current values and update.
    
        highLeft[leftIdx] = highLeftVal
        if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]
    
        lowRight[rightIdx] = lowRightVal
        if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]
    

    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:

    for each idx 1 thru cell.lastIndex-1 inclusive:
        if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]
            print "Found value ", cell[idx], " at index ", idx
    

    You can see the results of the initial pass below:

    highLeft:   -  1  3  3  6  6  7  9  9 10 10
    cells   :   1  3  2  6  5  7  9  8 10  8 11
    lowRight:   2  2  5  5  7  8  8  8  8 11  -
                               ^
    

    The only candidate 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 multiple items that satisfy the constraints. Given that you only need one item, 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 and the 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 current point, not back at the start, because:

    • everything after the current answer up to but excluding this (lesser or equal) cell is higher than the current answerr, otherwise you would have already found a lesser or equal cell; and
    • this cell must therefore be less than or equal to every cell in that range since it's less than or equal to the current answer; therefore
    • no cell in that range is valid, they're all greater 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 almost satisfies 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:

    # Store max on left and start with sentinel.
    
    maxToLeft = cell[0]
    answer = -1
    
    for checking = 1 to cell.lastIndex-1 inclusive:
        switch on answer:
            # Save if currently sentinel and item valid.
            case -1:
                if cell[checking] > maxToLeft:
                    answer = checking
    
            # Set back to sentinel if saved answer is now invalid.
            otherwise:
                if cell[answer] >= cell[checking]:
                    answer = -1
    
        # Ensure we have updated max on left.
    
        if cell[checking] > maxToLeft:
            maxToLeft = cell[checking]
    
    # Final check against last cell.
    
    if answer != -1:
        if cell[cell.lastIndex] <= cell[answer]:
            answer = -1
    

    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:

    cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
    
    highLeft = [0] * len(cell)
    lowRight = [0] * len(cell)
    
    highLeftVal = cell[0]
    lowRightVal = cell[len(cell)-1]
    
    rightIdx = len(cell) - 1
    for leftIdx in range(1, len(cell)):
        rightIdx = rightIdx - 1
    
        highLeft[leftIdx] = highLeftVal
        if cell[leftIdx] > highLeftVal: highLeftVal = cell[leftIdx]
    
        lowRight[rightIdx] = lowRightVal
        if cell[rightIdx] < lowRightVal: lowRightVal = cell[rightIdx]
    
    print(highLeft)
    print(cell)
    print(lowRight)
    
    for idx in range(1, len(cell) - 1):
        if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
            print("Found value", cell[idx], "at index", idx)
    

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

    cell = [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
    maxToLeft = cell[0]
    answer = -1
    for checking in range(1, len(cell) - 1):
        if answer == -1:
            if cell[checking] > maxToLeft:
                answer = checking
        else:
            if cell[answer] >=cell[checking]:
                answer = -1
        if cell[checking] > maxToLeft:
            maxToLeft = cell[checking]
    
    if answer != -1:
        if cell[len(cell] - 1] <= cell[answer]:
            answer = -1
    
    if answer == -1:
        print ("Not found")
    else:
        print("Found value", cell[answer], "at index", answer);
    
    
    print(highLeft)
    print(cell)
    print(lowRight)
    
    for idx in range(1, len(cell) - 1):
        if cell[idx] > highLeft[idx] and cell[idx] < lowRight[idx]:
            print("Found value", cell[idx], "at index", idx)
    

    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:

    [0, 1, 3, 3, 6, 6, 7, 9, 9, 10, 10]
    [1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11]
    [2, 2, 5, 5, 7, 8, 8, 8, 8, 11, 0]
    Found value 7 at index 5
    
  2. 2016-12-23 02:12

    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.

    int arr1 = new int[source.length];
    int highest = MIN_INT;
    for (int i = 0; i < source.length; i++) {
        arr1[i] = highest;
        if (source[i] > highest) {
            highest = source[i];
        }
    }
    

    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

    arr2 = new int[source.length];
    int lowest = MAX_INT;
    for (int i = (source.length-1); i <= 0; i--) {
        arr2[i] = lowest;
        if (source[i] < lowest) {
            lowest = source[i];
        }
    }
    

    Now you've basically got three arrays:

    source: 1   3   2   6   5  7   9   8   10   8   11
    arr1:   MIN 1   3   3   6  6   7   9    9  10   10
    arr2:   2   2   5   5   7  8   8   8    8  11   MAX
    

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

    arr1[i] < source[i] < arr2[i] 
    
    where:
         0 < i < (source.length-1)
    

    Code:

    for (int i = 1; i < (source.length-1); i++) {
        if ((arr1[i] < source[i]) && (source[i] < arr2[i])) {
            return i; // or return source[i]
        }
    }
    

    This is O(N) time.

  3. 2016-12-23 05:12

    This has O(n) for both Time and Space Complexity and a single array Pass.

    Logic :

    1. Find first max and overall max number found till now, keep traversing the array until you find a value that is less than first_max.
    2. If you did, then leave first_max and all elements before this, as all those elements were more than my current element found.
    3. Now choose a first_max such that the next value should be greater than the overall_max that we kept finding.

    Code :

    // int[] arr = { 10, 11, 1, 2, 12, 13, 14};
    int[] arr = {  1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11};
    Integer firstMax = null;
    Integer overallMax = null;
    
    for (int i = 1; i < arr.length - 1; i++) {
        int currentElement = arr[i];
        if (firstMax == null) {
            if (overallMax == null) {
                firstMax = currentElement;
            } else if (overallMax != null && currentElement > overallMax) {
                firstMax = currentElement;
            }
        }
        if (overallMax == null || currentElement > overallMax) {
            overallMax = currentElement;
        }
        if (firstMax != null && currentElement < firstMax) {
            // We found a smaller element, so all max found so far is useless. Start fresh.
            firstMax = null;
        }
    }
    
    System.out.println(firstMax);
    

    PS : From my analysis I feel this should be enough and work for all cases. Not sure if any case is missed out.

  4. 2016-12-23 07:12

    Here is an O(n), one pass solution in Python. Port to Java is trivial:

    import random
    A = [random.randint(1, 10) for i in range(0, 5)] # Generate list of size 5.
    max_seen = A[0]
    candidate = None
    for i in range(1,len(A)):
      if candidate is None:
        if A[i] > max_seen:
          candidate = i
      else:
        if A[i] <= A[candidate]:
          candidate = None
      max_seen = max(max_seen, A[i])
    
    print("Given %s " % (A,))
    if candidate is not None and candidate != len(A)-1: # Ignore the last element as per spec.
      print("found: value=%d; index=%d\n" % (A[candidate], candidate))
    else:
      print("not found")
    

    You'll need to run it a few times to generate a list that actually satisfies the condition.


    Description

    Restating objective: find index i of an element in an array A such that all 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, if x satisfies the above condition then A[x] > A[0..x-1] and A[x] < A[x+1..A.length]. It's sufficient to verify both those constraints for a given x. Note A[x] > A[0..x-1] <=> A[x] > max(A[0..x-1]). So we maintain the max value seen so far, find the first x satisfying 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, because A[x..y-1] > A[x] => A[y] < A[x..y-1], and is greater than the max value seen so far.

  5. 2016-12-23 10:12

    I wrote an implementation in c using the algorithm from S.Pinkus's answer, with debugging information.


    Code

    find_mid_num.c:

    /**
     * Problem:
     *  there is an array of number, find an element which is larer than elements before it, and smaller than elements after it,
     *  refer:  http://stackoverflow.com/questions/41293848
     * 
     * Solution:
     *  loop through array, remember max value of previous loopped elements, compare it to next element, to check whether the first condition is met,
     *  when found an element met the first condition, then loop elements after it to see whether second condition is met,
     *  if found, then that's it; if not found, say at position 'y' the condition is broken, then the next candidate must be after y, thus resume the loop from element after y,
     *  until found one or end of array,
     * 
     * @author Eric Wang
     * @date 2016-12-23 17:08
     */
    #include <stdio.h>
    
    // find first matched number, return its index on found, or -1 if not found,
    extern int findFirstMidNum(int *arr, int len);
    
    int findFirstMidNum(int *arr, int len) {
        int i=0, j;
        int max=arr[0];
    
        while(i < len) {
            printf("\n");
            if(arr[i] <= max) {
                printf("give up [%d]-th element {%d}, 1st condition not met\n", i, arr[i]);
                i++;
                continue;
            }
            max = arr[i]; // update max,
    
            printf("checking [%d]-th element {%d}, for 2nd condition\n", i, arr[i]);
            j = i+1;
            while(j < len) {
                if(arr[j] <= max) {
                    printf("give up [%d]-th element {%d}, 2nd condition not met\n", i, arr[i]);
                    break;
                }
                j++;
            }
            printf("position after 2nd check:\ti = %d, j = %d\n", i, j);
    
            if(j==len && j>i+1) {
                return i;
            } else {
                max = arr[j-1]; // adjust max before jump,
                i = j+1; // jump
                printf("position adjust to [%d], max adjust to value {%d}, after 2nd check\n", i, arr[j-1]);
            }
        }
    
        return -1;
    }
    
    int main() {
        int arr[] = {1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11};
        int len = sizeof(arr)/sizeof(arr[0]);
        printf("\n============ Input array ============\n");
        printf("size:\t%d\n", len);
        printf("elements:\t{");
    
        int i;
        for(i=0; i<len; i++) {
            printf("%d, ", arr[i]);
        }
        printf("}\n\n");
    
        printf("\n============ Running info ============\n");
        int pos = findFirstMidNum(arr, len);
    
        printf("\n============ Final result============\n");
        if (pos < 0) {
            printf("Element not found.\n");
        } else {
            printf("Element found at:\n\t position [%d], with value: {%d}\n", pos, arr[pos]);
        }
        printf("\n");
    
        return 0;
    }
    

    Compile:

    gcc -Wall find_mid_num.c

    Execute:

    ./a.out

    Running result:

    ============ Input array ============
    size:   11
    elements:   {1, 3, 2, 6, 5, 7, 9, 8, 10, 8, 11, }
    
    
    ============ Running info ============
    
    give up [0]-th element {1}, 1st condition not met
    
    checking [1]-th element {3}, for 2nd condition
    give up [1]-th element {3}, 2nd condition not met
    position after 2nd check:   i = 1, j = 2
    position adjust to [3], max adjust to value {3}, after 2nd check
    
    checking [3]-th element {6}, for 2nd condition
    give up [3]-th element {6}, 2nd condition not met
    position after 2nd check:   i = 3, j = 4
    position adjust to [5], max adjust to value {6}, after 2nd check
    
    checking [5]-th element {7}, for 2nd condition
    position after 2nd check:   i = 5, j = 11
    
    ============ Final result============
    Element found at:
         position [5], with value: {7}
    

    TODO - Further improvements:

    • Check boundary elements.
    • Provide a variety function to find all such elements, not just first one.
◀ Go back