4 lines Java AC solution, 2ms


  • 1

    I compress it into 4 lines lol, it is an O(n) solution if Arrays.sort() is not consider

        public int hIndex(int[] citations) {
            Arrays.sort(citations);
            int len = citations.length, h = 0;
            for (int i = len - 1; i >= 0; i--) {if (citations[i] >= len - i) {h++;}}
            return h;
        }
    

    the more readable version

            public int hIndex(int[] citations) {
            if (citations == null || citations.length == 0) {return 0;}
            
            Arrays.sort(citations);
            int len = citations.length, h = 0;
    
            for (int i = len - 1; i >= 0; i--) {
                if (citations[i] >= len - i) {
                   h++;
                }
            }
            return h;
        }
    

  • 1
    O

    I had the same idea :) Just to share my thought process here.

    Before sort: [3, 0, 6, 1, 5], and it can be visualized as:

    ###
    (empty)
    ######
    #
    #####
    

    After sort: [0, 1, 3, 5, 6], and it became:

    (empty)
    #
    ###
    #####
    ######
    

    Obviously, the problem can be rephrased to - what is the max square can be drawn from the bottom left corner (width = height)?


  • 0

    @Oaixoul haha your explanation make sense


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.