Given an unsorted array. The task is to find all the star and super star elements in the array. Star are those elements which are strictly greater than all the elements on its right side. Super star are those elements which are strictly greater than all the elements on its left and right side.
Note: Assume first element (A[0]) is greater than all the elements on its left side, And last element (A[n-1]) is greater than all the elements on its right side.
Input: The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains an Integer N denoting size of array and the second line contains N space separated elements.
Output: For each test case, print the space separated star elements and then in new line print super star elements. If no super star element present in array then print "-1".
Constraints: 1<=T<=200 1<=N<=106 1<=A[i]<=106
Example: Input:
2 6 4 2 5 7 2 1 3 8 6 5
Output:
7 2 1 7 8 6 5 8
My approach:
/*package whatever //do not write package name here */
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.Collections;
import java.util.Set;
import java.util.*;
class GFG {
private static void findElems (int [] arr)
{
int len = arr.length;
HashMap<Integer,Integer> stars = new HashMap<>();
stars.put(arr[len-1],len - 1);
int maxRight = arr[len - 1];
for (int i = len - 2; i >=0; i--)
{
if (arr[i] > maxRight)
{
stars.put(arr[i],i);
maxRight = arr[i];
}
}
int maxStar = Collections.max(stars.keySet());
int maxStarInd = (Integer)stars.get(maxStar);
int flag = 0;
for (int i = 0; i < len;i++)
{
if (i != maxStarInd)
{
if (arr[i] == maxStar)
{
flag = 1;
break;
}
}
}
Set <Integer> starSet = stars.keySet();
//Integer [] starKeys = starSet.toArray (new Integer[stars.size()]);
LinkedList <Integer> revSet = new LinkedList<>(starSet);
Collections.sort(revSet, Collections.reverseOrder());
Iterator<Integer> iter = revSet.iterator();
while (iter.hasNext())
{
System.out.print(iter.next() + " ");
}
System.out.println();
/* for (int i = starKeys.length - 1; i >= 0; i--)
{
System.out.println(starKeys[i]);
}
*/
if (flag == 0)
{
System.out.println(maxStar);
}
else
{
System.out.println(-1);
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int numTests = sc.nextInt();
for (int i = 0; i < numTests; i++)
{
int size = sc.nextInt();
int [] arr = new int[size];
for (int j = 0; j < size; j++)
{
arr[j] = sc.nextInt();
}
findElems(arr);
}
}
}
I have the following questions with regards to the above code:
How can I further improve my approach?
Is there a better way to solve this question?
Are there any grave code violations that I have committed?
Can space and time complexity be further improved?
Is my code very redundant?