Java O(1) space O(n) time solution, step by step explanation


  • 0
    Z

    Hi there! I am sharing my solution for O(1) space and O(n) time and step by step explanation. First off let's consider O(n) space and O(n) time solution. The main idea of this solution is the fact that maximum h index cannot exceed the number of publications. i.e size of the input array. Thus we can keep frequency array of size n+1. Where n is size of the input array. Why n+1? Well, because we need one cell to keep frequency of numbers (citations) that are greater or equal to the size of array. The rest of the solution can be understood from the code below.

    public class Solution {
        public int hIndex(int[] citations) {
            if(citations == null || citations.length == 0) return 0;
            int freq[] = new int[citations.length+1];
            for(int c:citations){
                if(c>=citations.length){
                    freq[citations.length]++;
                    continue;
                }
                freq[c]++;
            }
            int left = 0;
            int h = 0;
            int n = citations.length;
            for(int i = 0;i<freq.length;i++){
                for(int j = 0;j<freq[i];j++){
                    if(n == i){
                        h = i;
                    }
                    n--;
                }
                if(n == i){
                    h = i;
                }
            }
            return h;
        }
    }
    

    Well, we have used frequency array of size n+1. Which caused external memory of complexity O(n). Now, what if we reuse the input array for keeping frequencies? That is the idea. But how? Well, we know that all the numbers in the input array are non-negative. It means that, we can use negative numbers to denote frequencies. For instance, if citations[i] = -2, then number i occurs 2 times in the array. Ok, what about 0 and the numbers that have 0 frequency? Well, let's substitute 0 frequency with some impossibly small number (Integer.MIN_VALUE for ex.). That's it. For detailed understanding, please find commented code below.

    public class Solution {
        final int MAX = Integer.MIN_VALUE;
        public int hIndex(int[] citations) {
            if(citations == null || citations.length == 0) return 0;
            int i = 0;
            int n = citations.length;
            int big = 0; // frequency of citations that are greater or equal to the size of array
            while(i<n){
                if(citations[i]<0) { // if citations[i] is less than zero, which means this position has met already,
                    i++;             // then continue and consider next citation
                    continue;
                }
                if(citations[i] == i){ // if citation is already at its supposed position, assign frequency to 1 (i.e -1),
                    citations[i] = -1; // then continue
                    i++;
                    continue;
                }
                if(citations[i]>=n){  // if citation is more that or equal to the array size then increment big, mark this positions freq by 0 (i.e MAX)
                    citations[i] = MAX;
                    big++;
                    i++;
                    continue;
                }
                        
                int j = citations[i];
                if(citations[j] != MAX && citations[j]< 0) { // if citations[j] has already been met, then increment frequency, then mark current position by dummy frequency (MAX)
                    citations[j]--;
                    citations[i] = MAX;
                    i++;
                    continue;
                }
                swap(citations, i, j); // otherwise, swap, then assign to supposed position frequency 1 (-1).
                citations[j]= -1;
            }
            // the slice of code below calculates h analogically to the previous solution
            int left = n;
            int h = 0;
            for(i = 0;i<citations.length;i++){ 
                for(int j = 0;citations[i] !=MAX && j<-citations[i];j++){
                    if(left == i){
                        h = i;    
                    }
                    left--;
                }
                if(left == i) h = i;
            }
            for(int j = 0;j<big;j++){
                if(left == n){
                    h = n;
                }
                left--;
            }
            if(big != 0 && left == n) h = n;
            return h;
        }
        
        public void swap(int arr[], int i, int j){
            int tmp = arr[i];
            arr[i]  = arr[j];
            arr[j] = tmp;
        }
    }
    
    

    P.S: I beg pardon for terrible code:=) If you have improved it in terms of readability or something else, please comment below.


Log in to reply
 

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