Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Better Approach 
3.1.
Algorithm
3.2.
Implementation  in C++
3.2.1.
Complexity Analysis
4.
Optimized Approach 
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is the best time complexity for any sorting algorithm?
5.2.
State some applications of array data structure.
5.3.
Which data types can be stored in an array?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find all elements in an array which have at-least two greater elements.

Author Tarun Singh
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will try to strengthen our understanding of a single-dimensional 'Array' data structure problem. We will try to understand how to approach any array data structure problem through the problem. The examples presented will help you clear your concepts, a detailed algorithm will provide you with an immediate solution, and the implementation part will give you a thorough understanding of every step. So, let's get started with the problem statement and some quick examples.

Recommended topic, kth largest element in an array and  Euclid GCD Algorithm

Problem statement

Firstly, we will have a look at what precisely the problem says.

We are given an array of 'n' elements. In that array, we have to find all elements with at least two greater elements. 

Sample Examples

Input:

n=7, nums[] = {12, 17, 14, 20, 37, 61, 75}

Output:

Elements satisfying the problem statement: arr[] = {12, 14, 17, 20, 37}

 

Input:

n=5, nums[]= {9, 15, 14, 8, 13}

Output: 

Elements satisfying the problem statement arr[] = {9, 8, 13}

Brute Force Approach

In the brute force approach, we will take the largest and the second largest element to the end of the array, i.e., we sort the array and print the first n-2 elements. The time complexity of this approach will be O(N^2), and it will take constant space.

Algorithm

1. Our main aim is to take the largest and the second largest element to the end of the array.

2. If we succeed in doing so, we will print the first n-2 elements of the array, n being the size of the array.

3. Take the input for the number of elements for the array.

4. Take the input for the elements of the array.

5. Initialize a for loop starting from 0 to n-1.

6. Inside the for loop in step5, initialize a for loop starting from 0 to n-1.

7. The outer loop will learn n times, and so will the inner loop.

8. For every inner loop, we will swap the adjacent element if it is less than its previous element. The following code will be used to swap:

for(j=0;j<n-1;j++) {     
	if(a[j]>a[j+1]) {      
		tmp=a[j];    
		a[j]=a[j+1];    
		a[j+1]=tmp;
	}
}

 

9. After the above process is complete, we will get the desired array.

10. We will print the first n-2 elements.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // Taking input for number of elemnts
    int n;
    scanf("%d", &n);
    // taking input for value of element
    int a[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - 1; j++)
        { // taking largest and second largest element to the end of the array
            if (a[j] > a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    // printing first N-2 elements
    for (int i = 0; i < n - 2; i++)
    {
        printf("%d ", a[i]);
    }

    return 0;
}

 

Input: 

n=7, a[]={12, 17, 14, 20, 37, 61, 75}

 

Output:

a[] = {12, 14, 17,20, 37}

 

Complexity Analysis

The time complexity will be O(n^2) as we loop through the array one inside another.

The space complexity will be O(1). as we did not use any extra data structure for any operation. 

Read More - Time Complexity of Sorting Algorithms

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Better Approach 

In this approach, we will first sort the given array and print first N-2 elements. We will use the sort function for sorting the array. The time complexity of this approach will be O(N*log(N)), and it will take constant space. 

Algorithm

  1. Our main aim is to reduce the time complexity of the above approach. For this, we use the array sorting technique.
  2. If we succeed in doing so, we will print the first n-2 elements of the array, n being the size of the array.
  3. Take the input for the number of elements for the array.
  4. Take the input for the elements of the array.
  5. Sort the array using the “sort” function.
    sort(a, a + n); a being name of the array and n the size of array.
  6. Now we print the array using a simple for loop up to n-2 elements.

Implementation  in C++

#include <bits/stdc++.h>
using namespace std;
int main()
{ // Taking input for number of elements
    int n;
    cin >> n;
    int a[n];
    // Taking input for value of elements
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    // using the sort function for sorting the array
    sort(a, a + n);
    // printing the n-2 elements with satisy the condition
    for (int i = 0; i < n - 2; i++)
        cout << a[i] << " ";
}


Input: 

n=7, a[] = {2, 6, 8, 9, 0, 6, 7}

 

Output:

a[] = {0, 2, 6, 6, 7}

 

Complexity Analysis

The time complexity will be O(N*log(N)), as we sorted the array which takes O(N*log(N)) time complexity.

The space complexity will be O(1), as we did not use any extra data structure for any operation. 

Optimized Approach 

In the optimized approach, we will try to find the second largest element of the array and print all the elements less than it. We will try to reduce the time complexity from O(N*log(N)) to O(N) with constant space complexity.

Algorithm

1. Our aim is to find the second largest element of the array.

2.  By following Step1, we will print all the elements lesser than the second largest element.

3. We will take input for a number of elements of the array.

4. We will take input for elements of the array.

5. We will initialize two variables to hold the largest and second-largest elements of the array.

int max_one = INT_MIN, max_two = INT_MIN;

 

6. We will run a for loop with the following logic to calculate the second largest element of the array:

for (int i = 0; i < n; i++)
{
    if (a[i] > max_one)
	{
        max_two = max_one;
        max_one = a[i];
    }
    else if (a[i] > max_two) max_two = a[i];
}

 

7. While performing step6, we ensure that we get the desired result; now, we will proceed to print the elements less than the second largest element.

Must Read Algorithm Types

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int main()
{ // Taking input for number of elements
    int n;
    cin >> n;
    int a[n];
    // Taking input for value of elements
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    // intialising variables for largest and second largest element
    int max_one = INT_MIN, max_two = INT_MIN;
    for (int i = 0; i < n; i++)
    { // finding the second largest element
        if (a[i] > max_one)
        {
            max_two = max_one;
            max_one = a[i];
        }
        else if (a[i] > max_two) max_two = a[i];
    }
    // printing the n-2 elements with satisy the condition
    for (int i = 0; i < n; i++)
        if (a[i] < max_two)
            cout << a[i] << " ";
}

 

Input: 

n=5, a[] = {9, 15, 14, 8, 13}

 

Output:

a[] = {9, 8, 13}

 

Complexity Analysis

The time complexity will be O(N), as we looped through the array only once.

The space complexity will be O(1), as we did not use any extra data structure for any operation. 

Frequently Asked Questions

What is the best time complexity for any sorting algorithm?

The best time complexity for any sorting algorithm is O(N*log(N)). The worst-case complexity is O(N^2).

State some applications of array data structure.

  • Arrays can be used for sorting data.
  • Arrays can be used for CPU scheduling.
  • An array can store data elements of the same data type. 

Which data types can be stored in an array?

Arrays are data structures that store a list of elements of the same data type that may be retrieved using an index (element) number. The phrases array, list, vector, and sequence are interchangeable. Array elements can be of any data type.

Conclusion

In this article, we have analyzed how to find all elements in the array which have at-least two greater elements. We have gone through three different approaches to solving the problem; we have also discussed their algorithm, C++ code, and time and space complexity.

After reading about this array problem, are you not feeling excited to read/explore more articles on the topic of array and data structures and algorithms? Don't worry; Coding Ninjas has you covered. To learn, see Data Structures and AlgorithmsCompetitive Programming.

 

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Operating SystemUnix File SystemFile System RoutingFile Input/Output.JavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Find all triplets with zero-sum
Next article
Find Index of 0 to be replaced with 1 to get the Longest Continuous Sequence of 1s in a Binary Array
Live masterclass