There is an integer array ‘a’ of size ‘n’.
An element is called a Superior Element if it is greater than all the elements present to its right.
You must return an array all Superior Elements in the array ‘a’.
Note:
The last element of the array is always a Superior Element.
Example
Input: a = [1, 2, 3, 2], n = 4
Output: 2 3
Explanation:
a[ 2 ] = 3 is greater than a[ 3 ]. Hence it is a Superior Element.
a[ 3 ] = 2 is the last element. Hence it is a Superior Element.
The final answer is in sorted order.
The first line contains an integer, ‘n’.
The second line has ‘n’ integers denoting the array ‘a’.
You must return an array with all Superior elements.
You don’t need to print anything. Just implement the given function. Final answer will be printed in a sorted order.
4
1 2 2 1
1 2
Element present at the last index is '1' and is a superior element since there are no integers to the right of it.
Element present at index 2 (0-indexed) is '2' and is greater than all the elements to the right of it.
There are no other superior elements present in the array.
Hence the final answer is [1,2].
3
5 4 3
3 4 5
Try to solve this in O(n).
1 <= n <=10^5
1 <= a[i] <= 10^9
Time Limit: 1 sec
Simulate the problem statement.
Approach:
Algorithm:
Function int superiorNumber([int] A):
O( N^2 ), Where ‘N’ is given input.
We are using two loops. Outer is used to iterate on each element of the array, and the inner loop is used to iterate on the elements on its right. Also, we take N * log( N ) time for sorting the array. Hence, the overall time complexity will be O( N^2 ).
O( 1 ).
We are taking O( 1 ) extra space for the variables. Hence, the overall space complexity will be O( 1 ).
All tags
Sort by
Interview problems
JAVA || Iterate from right to left ans store the max element.
import java.util.*;
public class Solution {
public static List< Integer > superiorElements(int []a) {
// Write your code here.
// itterate from right to left ans store the max element.
ArrayList<Integer> list = new ArrayList<>();
list.add(a[a.length-1]);
for (int i=a.length-2; i>=0; i--) {
if (a[i] > list.get(list.size()-1)) {
list.add(a[i]);
}
}
return list;
}
}
Interview problems
SIMPLE BACKTRAVERSAL SOLUTION || O(n) TIME COMPLEXITY
vector<int> superiorElements(vector<int>&a) {
vector<int> ans;
int max = INT_MIN;
for(int i = a.size() - 1; i >=0; i--){
if(a[i] > max){
max = a[i];
ans.push_back(max);
}
}
return ans;
}
Interview problems
✨ Finding Superior Elements in an Array: An Optimal Approach 🚀
To solve this problem efficiently, we will iterate over the array from right to left and keep track of the maximum element found so far. This is because the "superior elements" are those that are greater than all elements to their right, and by traversing from the end, we can easily keep track of the maximum element seen.
Step-by-Step Approach:
2. Add the Last Element:
3. Traverse the Array Backwards:
4. Return the Result:
Example Trace
Let's take the input array a = {2, 7, 5, 3, 6, 4, 8, 1} and trace the solution:
Initialization:
Iterate from Right to Left:
Result:
Interview problems
C++ optimal solution
vector<int> superiorElements(vector<int>&a) {
// Write your code here.
vector<int> ans;
int maxi=INT_MIN;
int n=a.size();
for(int i=n-1;i>=0;i--)
{
if(a[i]>maxi)
{
ans.push_back(a[i]);
}
maxi=max(maxi,a[i]);
}
return ans;
}
Interview problems
Simplest O(N) solution in Java
import java.util.*;
public class Solution {
public static List< Integer > superiorElements(int []a) {
// Write your code here.
List<Integer>arr=new ArrayList<Integer>();
int max=a[a.length-1];
arr.add(max);
for(int i=a.length-2;i>=0;i--)
{
if(a[i]>max)
{
max=a[i];
arr.add(max);
}
}
return arr;
}
}Interview problems
Easy and Simple C++ Solution
vector<int> superiorElements(vector<int>&a) {
// Write your code here.
vector<int> ans;
int maxi = INT_MIN;
int n = a.size();
for(int i = n-1;i>=0;i--){
if(a[i]>maxi){
ans.push_back(a[i]);
}
maxi = max(maxi, a[i]);
}
sort(ans.begin(),ans.end());
return ans;
}
Interview problems
This is the Unique Optimal Solution where great programmers don't know.
vector<int> superiorElements(vector<int>&a) {
int i=0;
int n=a.size();
while(i<n-1){
if(a[i]<=a[i+1]){
a.erase(a.begin()+i);
n=a.size();
if(i>0) i--;
}
else i++;
}
reverse(a.begin(),a.end());
return a;
}
Interview problems
Optimal Solution of Superior Element problem in C++
vector<int> superiorElements(vector<int>&a) {
vector<int> ans;
int n = a.size();
int maxi = INT_MIN;
for(int i=n-1; i>=0; i--){
if(a[i] > maxi){
ans.push_back(a[i]);
}
maxi = max(maxi, a[i]);
}
return ans;
}
// Time complexity: o(n) for identifying the leader ( line 6 - 11)
// space complexity: o(n) for returning the answer
Interview problems
Solution for finding Superior Elements
An element is called a Superior Element if it is greater than all the elements present to its right. import java.util.*;
public class Solution {
public static List< Integer > superiorElements(int []a) {
ArrayList<Integer> ans = new ArrayList<>();
int n = a.length;
int maximum= -1;
for(int i=n-1; i>=0; i--){
if(a[i] > maximum){
// If value of element is greter than max
// max value will be replaced with bigger element
// element will be added to list
maximum = a[i];
ans.add(a[i]);
}
}
return ans;
}
}
Interview problems
C++ Most Efficient & Easy solution in O(n)
vector<int> superiorElements(vector<int>&a) {
vector<int> ans;
int n = a.size();
int max = a[n-1];
ans.push_back(a[n-1]);
for(int i=n-2; i>=0; i--){
if(a[i] > max){
max = a[i];
ans.push_back(a[i]);
}
}
return ans;
}
