CODEWITHSUNDEEP
arraysalgorithmcompare
YAKOVM
YAKOVM

Reputation: 10153

Interview - find greater element for each array`s element

I was asked the following question during the interview (Unfortunately I couldn't find the answer better than N^2)

For a given array arr for unsigned int of size N,for each element (in the index i) I should return an element in the index j (j > i),such that arr[j] > arr[i] I.e. I should return array res in which res[i] has a arr[j],j>i,arr[j] > arr[i],j is min among all indices k ,such that arr[k] > arr[i] for example

arr[] = {3,1,4,2,5,7};
res[] = {2,2,4,4,5,-1};//-1 says no such index

Any proposition to do it in better time complexity? Thanks

Upvotes: 3

Views: 324

Answers (3)

Michal
Michal

Reputation: 2238

O(N) Time and O(N) Space Complexity:

Create empty stack, iterate the array from the right

for each iterated item: keep popping from the stack as long as item on the top is smaller than current, then if the stack becomes empty there's no bigger element on the right, if not that's your first bigger item on the right for current element, push current item on the stack

void GetFirstRight(int* arr, int size, int* res){
  stack<int> s;
  for (int i = size - 1; i >= 0; --i) {
    while (!s.empty() && s.top() <= arr[i]) s.pop();
    if (s.empty()) { 
      res[i] = -1;
    } else {
      res[i] = s.top();
    }
    s.push(arr[i]);
  }
}

Upvotes: 6

Abyss
Abyss

Reputation: 66

O(n) algorithm:

Maintain a stack of indexes that are still not solved. This will be sorted so that the minimum still unsolved value is on the top. As you reach a new element pop from the stack until the value of the new element is less than the value on top of the stack. For each that you pop, the answer is the current index. Then push on the current index. At the end, the result for anything still on the stack is -1.

Code (C++):

stack<int> unsolved;
int arr[] = {3,1,4,2,5,7}, N = 6;
int res[1234];

int main() {
    for (int i = 0; i < N; i++) {
        while (!unsolved.empty() && arr[unsolved.top()] < arr[i]) {
            res[unsolved.top()] = i;
            unsolved.pop();
        }
        unsolved.push(i);
    }
    while (!unsolved.empty()) {
        res[unsolved.top()] = -1;
        unsolved.pop();
    }
    // Print results
    for (int i = 0; i < N; i++) printf("%d%c", res[i], i==N-1 ? '\n' : ' ');

    return 0;
}

Output:

2 2 4 4 5 -1

Upvotes: 3

ashley
ashley

Reputation: 1175

Keep a parallel array b. make b[0]=0. Make a run to iterate thru the elements of a. as you go along, set the values of b to the differences of consecutive cells of a.

so, if 

a[0]=9
a[1]=4
a[2]=17
a[3]=2
a[4]=3
a[5]=6
a[6]=0
a[7]=3
a[8]=1
a[9]=1
a[10]=7

then, 

b[0]=0
b[1]=-5
b[2]=13
b[3]=-15
b[4]=1
b[5]=3
b[6]=-6
b[7]=3
b[8]=-2
b[9]=0
b[10]=6

All you should be concerned about is the (-) cells in the b array. Now, start iterating backwards on array b-- starting from b[10] in the above eg. Keep a currentMax value. initially set to the first max (+) on the array-- nothing you can do about the (-) entries at the end of the array. As you iterate backwards from b[b.length] down to b[0], do the following:

update currentMax: 

currentMax += <value at the current cell of **b**>

if (currentMax<0) then /* you've hit elements-with-no-indexes*/ then keep going till you find a positive b[i] entry, and when you find one, set the value of currentMax to it.

(+) values of currentMax indicate cells that the cell that reset currentMax is the index for all cells visited-so-far, (-) values are no-index cells.

In the above eg, 7 at a[10] is the index of all in a[3]..a[9], because -currentMax is the one initialized at cell 10 (and not reset afterwards) -the value of currentMax after all those additions is still (+) all the way up to cell 4 (cell 4 reflects the change from cell 3-to-4)

At b[3], currentMax falls below 0--meaning no index for cell 2. The value found at b[2] is positive while currentMax is negative-- so make at b[3], currentMax=13 and iterate on.

Linear in the array size-- takes O(n) time.

Upvotes: 0

Related Questions