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
569+ registered 
