Introduction :

In this tutorial, we will learn how to find all elements in an integer array bigger than all other elements present to the right of that element. For example :

[1,2,5,3,1,0]

In this array, 5,3,1 and 0 are elements greater than all right elements.

We will learn three different ways to solve this problem.

Approach 1: Using brute force :

Using brute force approach, we can solve this problem.

Use two for loops one inside another. The outer loop will iterate through the elements one by one. The inner loop will iterate through all right elements to the element that is iterate by the outer loop.

The inner loop will check if any element is greater than the current element or not. If no elements are found, it will print the current element pointed by the outer loop.

C program :

The C program using brute force method is as below :

#include <stdio.h>
#include <stdlib.h>
#define SIZE 6

int main()
{
    //1
    int numArray[SIZE] = {1, 2, 5, 3, 1, 0};

    //2
    int i, j;

    //3
    for (i = 0; i < SIZE; i++)
    {
        //4
        for (j = i + 1; j < SIZE; j++)
        {
            //5
            if (numArray[j] > numArray[i])
            {
                break;
            }
            //6
            if (j == SIZE - 1)
            {
                printf("%d ", numArray[i]);
            }
        }

        //7
        if (i == SIZE - 1)
        {
            printf("%d\n", numArray[i]);
        }
    }

    return 0;
}

Explanation :

The commented numbers in the above program denote the step numbers below:

1. numArray is the given array. You can change the numbers of this array to anything you want.
2. i and j are two variables initialized to use in the loops.
3. The outer loops iterate through the array values one by one.
4. For each value pointed by the outer loop, the inner loop iterates others to its right.
5. If any larger number is found, exit from the inner loop.
6. If no larger number is found, print the current value pointed by the outer loop.
7. This if statement is for printing the last element of the array. The last element will always be there because we don’t have any element to the right of it.

The time complexity of this method is O(n^2) and it is not a recommended way to solve because for a large array it will take a huge amount of time to complete

Approach 2 : O(n) with extra space :

We can also solve this problem in O(n) time complexity and with an extra space. Below algorithm we will use for that :

1. Create one extra array of the same size as the original array holding numbers. Create one index pointer variable to point to the current index in the second array.
2. Iterate through the elements one by one.
3. For each element, check in the second array if any larger value exists. If yes, remove it and check the element to its left. If not, add this element to the array.
4. Finally, the second array will hold the required numbers.

C program :

#include <stdio.h>
#define SIZE 6

int main()
{
    //1
    int numArray[SIZE] = {1, 2, 5, 3, 1, 0};
    int resultArray[SIZE] = {0};

    //2
    int resultArrayIndex = 0;
    int i;

    //3
    resultArray[0] = numArray[0];

    //4
    for (i = 1; i < SIZE; i++)
    {
        //5
        while (resultArrayIndex >= 0)
        {
            //6
            if (resultArray[resultArrayIndex] < numArray[i])
            {
                resultArrayIndex--;
            }
            else
            {
                break;
            }
        }

        //7
        resultArray[resultArrayIndex + 1] = numArray[i];
        resultArrayIndex++;
    }

    //8
    for (i = 0; i < resultArrayIndex + 1; i++)
    {
        printf("%d ", resultArray[i]);
    }

    return 0;
}

Explanation :

The commented numbers in the above program denote the step numbers below:

1. numArray is the array holding the numbers. resultArray is the array to hold the final result.
2. resultArrayIndex is assigned to 0. This variable will point to the current index position of the array resultArray.
3. Add the first element of the array numArray to the resultArray.
4. Run one for loop starting from the second element and iterate through each element one by one.
5. Check for each element in the resultArray.
6. If it is smaller than the number pointed by the loop, decrement the value of resultArrayIndex i.e. decrement the pointer variable. If not, exit from the loop.
7. Add the current element to the array resultArray.
8. Finally, print out the contents of the resultArray.

The complexity of this program is O(n) for both space and time. This is an optimized solution than the previous one but we have one more way to solve it. Let me show you how :

Approach 3: Using one for loop and without using extra space:

This is the most efficient solution and the easiest to solve. Algorithm :

1. Scan the items of the array from right to left.
2. Create one variable to assign the current largest number. Initialize it as -1.
3. For each element, check if it is bigger than the largest number or not. If yes, print its value and update the largest number variable. If not, move to the next value.

That’s it.

C program :

#include <stdio.h>
#define SIZE 6

int main()
{
    //1
    int numArray[SIZE] = {1, 2, 5, 3, 1, 0};

    //2
    int i;
    int largestNumber = -1;

    //3
    for (i = SIZE - 1; i >= 0; i--)
    {
        //4
        if (numArray[i] > largestNumber)
        {
            printf("%d ", numArray[i]);
            largestNumber = numArray[i];
        }
    }

    return 0;
}

Explanation :

The commented numbers in the above program denote the step numbers below:

1. numArray is the given array.
2. Create one integer variable i to use in the loop for iteration and one variable largestNumber to store the current largest number. Initialize it to -1.
3. Run one for loop to scan all items from right to left.
4. If the current item is bigger than largestNumber, print it and assign its value to largestNumber.

The time complexity of this solution is O(n).

Conclusion :

In this tutorial, we have learned how to find all elements in an array bigger than its right elements. We have learned three different ways to solve it. Try to execute these solutions with different arrays and drop one comment below if you have any queries.

You might also like:

• C program to convert hour to minute and seconds value
• C nanosleep method explanation with example
• How to delete an empty directory in C
• How to copy a file in C programming
• C getc and putc methods explanation with example
• C program to find the hypotenuse of a right-angled triangle
• C program to print all printable characters
• How to read an octal value using scanf in C
• How to find the square root of a number in C