CODEWITHSUNDEEP
calgorithm
Christos Papoulas
Christos Papoulas

Reputation: 2568

How to find the number of elements in the array that are bigger than all elements after it?

I have a function that takes a one-dimensional array of N positive integers and returns the number of elements that are larger than all the next. The problem is exist a function to do it that in a better time? My code is the following:

int count(int *p, int n) {
    int i, j;
    int countNo = 0;
    int flag = 0;
    for(i = 0; i < n; i++) {
        flag = 1;
        for(j = i + 1; j < n; j++) {
            if(p[i] <= p[j]) {
                flag = 0;
                break;
            }
        }
        if(flag) {
            countNo++;
        }
    }
    return countNo;
}

My solution is O(n^2). Can it be done better?

Upvotes: 2

Views: 753

Answers (5)

Vivek Pradhan
Vivek Pradhan

Reputation: 4847

Yes, it can be done in O(N) time. I'll give you an approach on how to go about it. If I understand your question correctly, you want the number of elements that are larger than all the elements that come next in the array provided the order is maintained.

So:

Let len = length of array x

{...,x[i],x[i+1]...x[len-1]}

We want the count of all elements x[i] such that x[i]> x[i+1] 
and so on till x[len-1]

Start traversing the array from the end i.e. at i = len -1 and keep track of the largest element that you've encountered.

It could be something like this:

max = x[len-1] //A sentinel max

//Start a loop from i = len-1 to i = 0;

if(x[i] > max)
  max = x[i] //Update max as you encounter elements

//Now consider a situation when we are in the middle of the array at some i = j

{...,x[j],....x[len-1]}

//Right now we have a value of max which is the largest of elements from i=j+1 to len-1

So when you encounter an x[j] that is larger than max, you've essentially found an element that's larger than all the elements next. You could just have a counter and increment it when that happens.

Pseudocode to show the flow of algorithm:

 counter = 0
 i = length of array x - 1
 max = x[i]
 i = i-1
 while(i>=0){
      if(x[i] > max){
         max = x[i]   //update max
         counter++    //update counter
      } 
      i--
 }

So ultimately counter will have the number of elements you require.

Hope I was able to explain you how to go about this. Coding this should be a fun exercise as a starting point.

Upvotes: 1

Vagish
Vagish

Reputation: 2547

It can be done in O(n).

int count(int *p, int n) {
    int i, currentMax;
    int countNo = 0;
    currentMax = p[n-1];   
    for(i = n-1; i >= 0; i--) {

     if(currentMax < p[i])
     {
        countNo ++;
        currentMax = p[i];
     }
    }
    return countNo;
}

Upvotes: 1

Nikunj Banka
Nikunj Banka

Reputation: 11375

You can solve this problem in linear time(O(n) time). Note that the last number in the array will always be a valid number that fits the problem definition. So the function will always output a value that will be greater than equal to 1.

For any other number in the array to be a valid number it must be greater than or equal to the greatest number that is after that number in the array.

So iterate over the array from right to left keeping track of the greatest number found till now and increment the counter if current number is greater than or equal to the greatest found till now.

Working code

int count2(int *p, int n) {
    int max = -1000;  //this variable represents negative infinity. 
    int cnt = 0;
    int i;
    for(i = n-1; i >=0; i--) {
        if(p[i] >= max){
            cnt++;
        }
        if(p[i] > max){
            max = p[i];
        }
    }
    return cnt;
}

Time complexity : O(n)
Space complexity : O(1)

Upvotes: 4

Markus Jarderot
Markus Jarderot

Reputation: 89221

Walk backwards trough the array, and keep track of the current maximum. Whenever you find a new maximum, that element is larger than the elements following.

Upvotes: 1

amit
amit

Reputation: 178491

Create an auxillary array aux:

aux[i] = max{arr[i+1], ... ,arr[n-1] }

It can be done in linear time by scanning the array from right to left.

Now, you only need the number of elements such that arr[i] > aux[i]

This is done in O(n).

Upvotes: 1

Related Questions