Hacker rank Jesse and Cookies I am trying to solve a problem on Hacker Rank and the question is as follows:


  Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value \$K\$. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with:

sweetness =(1× Least sweet cookie + 2× 2nd least sweet cookie).

  
  He repeats this procedure until all the cookies in his collection have a sweetness \$\ge K\$. 
  You are given Jesse's cookies. Print the number of operations required to give the cookies a sweetness \$\ge K\$. Print \$−1\$ if this isn't possible.
  
  Input Format
  
  The first line consists of integers \$N\$, the number of cookies and \$K\$, the minimum required sweetness, separated by a space. 
  The next line contains \$N\$ integers describing the array \$A\$ where \$Ai\$ is the sweetness of the \$i\$th cookie in Jesse's collection.
  
  Constraints
  
  \$1\le N\le 10^6\$
    \$0\le K\le 10^9\$
    \$0\le Ai\le 10^6\$
  
  Output Format
  
  Output the number of operations that are needed to increase the cookie's sweetness \$\ge  k\$. 
  Output \$−1\$ if this isn't possible.


For this I have written code in Java like this:

    public class Solution {
        public int getMinStepsToGetK(long k,LinkedList&lt;Integer&gt; newList){
            Collections.sort(newList);
            int count=0;
            while(newList.getFirst()&lt;k){
                if(newList.size()&gt;=2){
                count++;
                int tempFirst = newList.removeFirst();
                int tempSecond = newList.removeFirst();
                newList.add(tempFirst+(tempSecond*2));
                Collections.sort(newList);
                }
                else{
                    return -1;
                }
            }
            return count;
        }
        public static void main(String[] args) {
            /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
            Solution newObj = new Solution();
            Scanner scanObj = new Scanner(System.in);
            int numOfCookies = scanObj.nextInt();
            long minSweetness = scanObj.nextLong();
            LinkedList&lt;Integer&gt; newList = new LinkedList&lt;Integer&gt;();
            for(int i=0;i&lt;numOfCookies;i++){
                newList.add(scanObj.nextInt());
            }
            System.out.println(newObj.getMinStepsToGetK(minSweetness,newList));
        }
    }


For the above code I am getting half of my test cases right and the other half is giving time out exception (taking more than 4 seconds to give output). My question is basically: where can I improve the performance of the code? Is there any other approach which I should go about?
Your algorithm can be summarized as follows:


  
  Fetch the list of cookies and sort in ascending order.
  Initialize a counter to zero
  If the smallest cookie is less than K,  then:
  
  
  (a) Increment the counter and combine this cookie with the next smallest cookie (or return -1 if there are fewer than 2 cookies left)
  (b) Remove the two smallest cookies from the list and add the new cookie to the list
  (c) Sort the list in ascending order again
  
  Otherwise, exit with the value of the counter
  Go back to step 3
  


Your code is taking a long time to run because you are sorting the entire list at step 3(c). This is unnecessary; since the list is already sorted (apart from the new value being added), you can just do a binary search in \$\mathcal{O}(\log(n))\$ time to find the correct position in which to insert the combined cookie. This is going to be much faster than sorting, which typically takes \$\mathcal{O}(n\log(n))\$ time.

An even better approach would be to use a min-heap data structure, which will keep track of the smallest element in a set in the most efficient way possible.



Addendum:

I converted your code to use a PriorityQueue data structure (Java's equivalent to a min-heap). I also created some test data using the following code:

perl -e '$n=100000;$h=$n/2;print "$n $h\n";for $i(0..$n){$r = int(rand()*$n); print "$r ";};print "\n";' &gt; testdata.txt


Your original code took 1 minute to process 100,000 items. With a priority queue, this went down to 0.7 seconds. Here's my code:

import java.util.*;

public class Solution2 {

  private static int getMinStepsToGetK(long k,PriorityQueue&lt;Integer&gt; newQueue){
    int count=0;
    while(newQueue.peek()&lt;k) {
      if(newQueue.size()&gt;=2) {
        count++;
        int tempFirst = newQueue.poll();
        int tempSecond = newQueue.poll();
        newQueue.offer(tempFirst+(tempSecond*2));
      }
      else {
        return -1;
      }
    }
    return count;
  }

  public static void main(String[] args) {
    Scanner scanObj = new Scanner(System.in);
    int numOfCookies = scanObj.nextInt();
    long minSweetness = scanObj.nextLong();
    PriorityQueue&lt;Integer&gt; newQueue = new PriorityQueue&lt;Integer&gt;();
    for(int i=0;i&lt;numOfCookies;i++) {
      newQueue.offer(scanObj.nextInt());
    }
    System.out.println(getMinStepsToGetK(minSweetness,newQueue));
  }

}


Note: There's no need to create a new Solution object in order to access the getMinStepsToGetK() member function. Since it isn't needed externally, I declared it as a private static function.