trjhtr

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:

1. How can I further improve my approach?




2. Is there a better way to solve this question?




3. Are there any grave code violations that I have committed?




4. Can space and time complexity be further improved?




5. Is my code very redundant?

Reference

How can I further improve my approach?

Is there a better way to solve this question?

Let's start by making some observations about the problem description and the possible inputs:

• The star elements will always be a strictly decreasing sequence


• There will always be one star element: the rightmost one


• The leftmost star may or may not be a super star

The posted code uses a map to find the star elements.
This is unnecessary, a list would be fine.
The loop you already have going from right to left could prepend the found star element to the list of stars.

After finding the stars, you need to check if the first star is a super star or not.
This is easy to verify, for example by a second scan of the array,
checking that precisely one element is equal,
and all other elements are strictly less than the leftmost star.

In this verification step,
you could avoid scanning the entire array if you know the index of the leftmost star, but such optimization is not really important,
because the order of time complexity of the solution will be the same.

This proposed solution uses fewer redundant data structures (a single list instead of a map and a set), and performs faster (no sorting).

Are there any grave code violations that I have committed?

The findElems method does too many things.
It finds the stars and super stars and prints them.
It would be better to organize programs in a way that one method does one thing.
Following the suggested sketch above,
there could be one function to find the stars,
one to verify if an element is a super star,
and one to print.
When organized that way,
the logical steps will be easier to understand,
and the solution will be much easier to test.

Can space and time complexity be further improved?

The suggested sketch above is better because it eliminates the sorting of the stars. That would be a significant improvement when the input set is a strictly decreasing sequence, where all elements are stars. In this extreme case the time complexity would be reduced from $O(n log n)$ to $O(n)$.
However, since the problem description says there are maximum 106 elements, this improvement would be hardly measurable, insignificant.

Is my code very redundant?

As mentioned earlier, the map and set can be replaced with a single list,
if you change the approach as I outlined.

Here's the most time efficient safe way that I came up with. I'll let you handle the printing details

public static void main(String args) 
 int arr1 = Arrays.asList("2 6 4 2 5 7 2 1 3 8 6 5".split(" ")).stream().mapToInt(Integer::parseInt).toArray();
 int arr2 = Arrays.asList("10 14 10 12 12 13 15 14".split(" ")).stream().mapToInt(Integer::parseInt).toArray();
 Main.findElems(arr1);
 Main.findElems(arr2);





private static void findElems (int arr) 
 class Helper 
 private int arr;
 private int maxFromLeft;
 private int maxFromRight;
 private List<Integer> indicesOfStars;
 private List<Integer> stars;
 private List<Integer> superstars;

 Helper(int arr) 
 this.arr = Arrays.copyOf(arr, arr.length);
 calcMaxLefts();
 calcMaxRights();
 recordStarIndices();
 recordStars();
 recordSuperstars();
 

 private void calcMaxLefts() 
 maxFromLeft = new int[arr.length];
 maxFromLeft[0] = arr[0];
 for (int i = 1; i < arr.length; i++) 
 maxFromLeft[i] = Integer.max(arr[i], maxFromLeft[i-1]);
 
 

 private void calcMaxRights() 
 maxFromRight = new int[arr.length];
 maxFromRight[arr.length-1] = arr[arr.length-1];
 for (int i = arr.length-2; i >= 0; i--) 
 maxFromRight[i] = Integer.max(arr[i], maxFromRight[i+1]);
 
 

 private boolean isGreaterThanAllToLeft(int index) 
 if (index == 0)
 return true;
 return arr[index] > maxFromLeft[index - 1];
 

 private boolean isGreaterThanAllToRight(int index) 
 if (index == (arr.length-1))
 return true;
 return arr[index] > maxFromRight[index + 1];
 

 private void recordStarIndices() 
 indicesOfStars = new ArrayList<>(arr.length);
 for (int i = 0; i < arr.length; i++) 
 if (isGreaterThanAllToRight(i)) indicesOfStars.add(i);
 
 

 private void recordStars() 
 stars = new ArrayList<>(indicesOfStars.size());
 for (int i : indicesOfStars) 
 stars.add(arr[i]);
 
 

 private void recordSuperstars() 
 superstars = new ArrayList<>(indicesOfStars.size());
 //superstars are also stars, so only check from stars
 for (int i : indicesOfStars) 
 if (isGreaterThanAllToLeft(i)) superstars.add(arr[i]);
 
 

 public List<Integer> getStars() 
 return Collections.unmodifiableList(stars);
 

 public List<Integer> getSuperstars() 
 return Collections.unmodifiableList(superstars);
 

 //END class Helper


 Helper helper = new Helper(arr);
 List<Integer> stars = helper.getStars();
 List<Integer> superstars = helper.getSuperstars();
 System.out.println("stars = " + stars);
 System.out.println("superstars = " + superstars);