Calculate the rates at which users get stuck at each stage I completed an algorithm problem just as a personal study, and I can't help but feel like my solution is a bit needlessly complicated, although I can't figure out a better way to do it. Here's the problem : 


  Given a number N, and a list of users currently on a stage, find out the failure rate of each stage up to N, and list the stages in descending order of failure rate. The failure rate is the percentage of users currently stuck on a stage, out of all the users who are currently playing the current stage or higher.


Example :
        stages = [2, 1, 2, 6, 2, 4, 3, 3], N = 5


There is 1 user currently playing stage 1, therefore out of the list of 8 users playing stage 1 or higher the failure rate of stage 1 is 1/8.
There are 3 users currently playing stage 2, therefore out of 7 users playing stage 2 or higher the failure rate is 3/7.
There are 2 users currently playing stage 3, therefore out of 4 users playing stage 3 or higher the failure rate is 2/4.
There is 1 user currently playing stage 4, therefore out of 2 users playing stage 4 or higher the failure rate is 1/2.
There are 0 users currently playing stage 5, therefore out of 1 users playing stage 5 or higher the failure rate is 0/1.


Therefore the result is : [3, 4, 2, 1, 5]

My solution : 

public class StageFailureRate {
    private ArrayList&lt;Integer&gt; result;

    public StageFailureRate(int N, Integer[] stages) {
        result = new ArrayList&lt;&gt;();
        Map&lt;Integer, Integer&gt; usersOnStage = new HashMap&lt;&gt;();

        //count how many users are on each stage
        for (int stage : stages) {
            if (!usersOnStage.containsKey(stage)) {
                usersOnStage.put(stage, 1);
            } else {
                usersOnStage.put(stage, usersOnStage.get(stage) + 1);
            }
        }

        //compute the failure rate for each stage, up to N stages
        int total = stages.length;
        Map&lt;Integer, Float&gt; failureRates = new HashMap&lt;Integer, Float&gt;();
        float failureRate = 0;
        for (int i = 1; i &lt;= N; ++i) {
            if (usersOnStage.containsKey(i)) {
                failureRate = (float) usersOnStage.get(i) / (float) total;
                total = total - usersOnStage.get(i);
            } else {
                failureRate = 0 / total;
            }
            failureRates.put(i, failureRate);
        }

        //Sort into descending order and get the result.
        Map&lt;Integer, Float&gt; sortedMap = sortByValue(failureRates);

        for (Map.Entry&lt;Integer, Float&gt; entry : sortedMap.entrySet()) {
            result.add(entry.getKey());
        }
    }

    public ArrayList&lt;Integer&gt; getResult() {
        return result;
    }

    private static Map&lt;Integer, Float&gt; sortByValue(Map&lt;Integer, Float&gt; unsortedMap) {
        List&lt;Map.Entry&lt;Integer, Float&gt;&gt; list =
                new LinkedList&lt;Map.Entry&lt;Integer, Float&gt;&gt;(unsortedMap.entrySet());

        Collections.sort(list, new Comparator&lt;Map.Entry&lt;Integer, Float&gt;&gt;() {
            public int compare(Map.Entry&lt;Integer, Float&gt; o1,
                               Map.Entry&lt;Integer, Float&gt; o2) {
                return (o2.getValue()).compareTo(o1.getValue());
            }
        });

        Map&lt;Integer, Float&gt; sortedMap = new LinkedHashMap&lt;Integer, Float&gt;();
        for (Map.Entry&lt;Integer, Float&gt; entry : list) {
            sortedMap.put(entry.getKey(), entry.getValue());
       }
        return sortedMap;
    }
}


This solution is correct. Do you think it's the most optimal solution or could this be optimized to be much faster?
you should define float failureRate = 0; inside the for (int i = 1; i &lt;= N; ++i) loop, because you are not using it outside the loop. See this for more info.
When you calculate failureRate, just cast one of usersOnStage.get(i) or total to float. You don't need to cast both.
else {failureRate = 0 / total;} is redundant because you'll always set failureRate to 0, which is its default value.


As for optimization to make it faster, since this piece of code is likely to be used in a video game, stages should be a small list, where efficiency of the algorithm doesn't matter much. You'd probably want to use simpler data structures, for a smaller overhead.