1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and how it improves upon the original) so that the author can learn from your thought process. \$\endgroup\$ – Vogel612 Jun 21 '18 at 19:35
  • \$\begingroup\$ Yes, because my time was very limited this morning, and I had quite a difficult time reading his/her code. I appreciate the comment, but the vote down seems quite harsh after the trouble I went to, and it makes me want to never help people on this website \$\endgroup\$ – Zachary Rudzik Jun 22 '18 at 2:44
  • 1
    \$\begingroup\$ I appreciate your help @ZacharyRudzik. \$\endgroup\$ – Anirudh Thatipelli Jun 22 '18 at 4:20
  • \$\begingroup\$ Anirudh Thatipelli. I understand your code until "int flag = 0;" Everything up to that point looks good in terms of performance. I don't see where you are recording the superstars. Your code is not very intuitive and could be greatly improved with comments explaining each step, whereas the code I wrote is broken into small pieces that have very descriptive names, but I too should have put comments in the code, but I was rushed this morning and didn't want to make you wait all day for an answer \$\endgroup\$ – Zachary Rudzik Jun 22 '18 at 6:55
  • 1
    \$\begingroup\$ @ZacharyRudzik In the first loop, I try to find all the stars by traversing the loop from right to left. In O(n) time, I get the stars. As I will have only 1 superstar which is the maximum of the stars. I want to check if there are more than 1 occurrences of it in the 2nd loop. I will make sure to write more comments and improve the readability of my program. Thanks for pointing out the HashMap problem. \$\endgroup\$ – Anirudh Thatipelli Jun 23 '18 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.