Thursday, December 5, 2024
Google search engine
HomeData Modelling & AIJava Program for Number of local extrema in an array

Java Program for Number of local extrema in an array

You are given an array on n-elements. An extrema is an elements which is either greater than its both of neighbors or less than its both neighbors. You have to calculate the number of local extrema in given array. 
Note : 1st and last elements are not extrema.
Examples : 
 

Input : a[] = {1, 5, 2, 5}
Output : 2

Input : a[] = {1, 2, 3}
Output : 0

 

Approach :For calculating number of extrema we have to check whether an element is maxima or minima i.e. whether it is greater than both of its neighbors or less than both neighbors. For this simply iterate over the array and for each elements check its possibility of being an extrema.
Note: a[0] and a[n-1] has exactly one neighbour each, they are neither minima nor maxima.
 

Java




// Java to find
// number of extrema
import java.io.*;
 
class GFG {
     
    // function to find
    // local extremum
    static int extrema(int a[], int n)
    {
        int count = 0;
     
        // start loop from
        // position 1 till n-1
        for (int i = 1; i < n - 1; i++)
        {
     
            // only one condition
            // will be true at a 
            // time either a[i]
            // will be greater than
            // neighbours or less
            // than neighbours
     
            // check if a[i] is greater
            // than both its neighbours
            // then add 1 to x
            if(a[i] > a[i - 1] && a[i] > a[i + 1])
                count += 1;
             
            // check if a[i] is
            // less than both its
            // neighbours, then
            // add 1 to x
            if(a[i] < a[i - 1] && a[i] < a[i + 1])
                count += 1;
        }
     
        return count;
    }
     
    // driver program
    public static void main(String args[])
                            throws IOException
    {
        int a[] = { 1, 0, 2, 1 };
        int n = a.length;
        System.out.println(extrema(a, n));
    }
}
 
 
/* This code is contributed by Nikita Tiwari.*/


Output : 

2

Time Complexity: O(n) where n is size of input array. This is because a for loop is executing from 1 to n.

Space Complexity: O(1) as no extra space has been used.

Please refer complete article on Number of local extrema in an array for more details!

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.

Last Updated :
08 May, 2023
Like Article
Save Article


Previous

<!–

8 Min Read | Java

–>


Next


<!–

8 Min Read | Java

–>

Share your thoughts in the comments

Dominic Rubhabha-Wardslaus
Dominic Rubhabha-Wardslaushttp://wardslaus.com
infosec,malicious & dos attacks generator, boot rom exploit philanthropist , wild hacker , game developer,
RELATED ARTICLES

Most Popular

Recent Comments