Star Elements implementation in Java

Question

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

Answer 1

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.

Answer 2

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);
}