CODEWITHSUNDEEP
javaarraysalgorithm
codewarrior
codewarrior

Reputation: 1034

find predecessor of a given element from an array

How to find the predecessor of a given number from a given array of numbers? For example, if the given array contains -2,1,0,3
and the input number is 0, then the predecessor is -2.

I wrote the following code:

public static int getPredecessor(int[] inpArr, int key) {
    int minDiff = key<=0 ? (key-inpArr[0]) : key;
    int predecessor = key;
    for(int i=0;i<inpArr.length;i++) {
        if(inpArr[i] < key && (key - inpArr[i])<=minDiff)
        {
            minDiff = key - inpArr[i];
            predecessor = inpArr[i];
        }   
    }
    return predecessor;
}

What I have done is basically keep track of the minimum difference between the supplied number and each number in the array; whenever the minimum difference is encountered, that particular number in the array is stored as the predecessor. If the final return statement is going to return the same number as the input number, then it means no predecessor was found in the given array.

My question is:
can the code be optimized in any way? It runs in O(n) time and O(1) space complexities.

Upvotes: 2

Views: 2674

Answers (2)

codewarrior
codewarrior

Reputation: 1034

The code above doesn't work for cases like inpArr=[-5,-2] and key=-4, inpArr=[-5,-2,-3], key=+1. So corrected it. Here's the corrected code.

public static int getPredecessorv2(int[] inpArr, int key) {
    int minDiff = Math.abs(key);
    int pred = key;
    if(inpArr[0] < key) {
        minDiff = key - inpArr[0];
        pred = inpArr[0];
    } 
    for(int i=0;i<inpArr.length;i++) {
        if(inpArr[i] < key && (key - inpArr[i])<=minDiff)
        {
            minDiff = key - inpArr[i];
            pred = inpArr[i];
        }   
    }
    return pred;
}

Upvotes: 0

Simon
Simon

Reputation: 10841

For a single query on an unsorted array (as the example array is), O(N) time is the best that could be achieved because there must inevitably be a comparison with every element in the array.

Sorting the array first will cost O(N log N) time but, if many queries on the array are expected, each query could then be done by binary search in O(log N) time. Thus, the average cost of a query could be lower than O(N), if there are enough queries.

Alternatively, if many queries are expected to use the same small(ish) set of key values, memo-izing the result for each key using, for instance, a hash table would eventually provide an average O(1) performance per query at the cost of O(N) space.

Upvotes: 2

Related Questions