Counting Sort 1 HackerRank solution in Java with code explanation

Find occurrence of all elements from Java list and store into another List 

Problem description :

Given a list of integers, count and return the number of times each value appears as an array of integers.

Input = [1, 1, 3, 2, 1]
Output = [0, 3, 1, 1]

In input, we have three occurrence of 1, one occurrence of 2 and one occurrence of 3. So in output put 3 at first index, 1 at second index and 1 at third index.

Input = [2, 2, 1, 6, 5]
Output = [0, 1, 2, 0, 0, 1, 1]

In this problem, we does not have to write entire code of counting sort. we need only first step of counting sort algorithm.

So lets jump on code.

import java.io.*;
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    public static List<Integer> countingSort(List<Integer> arr) {

    // Creating 100 list size and initialize with 0
    List<Integer> output = new ArrayList<>(Collections.nCopies(100, 0));
        for (Integer value : arr) {
            if (output.get(value) != 0) {
                output.set(value, output.get(value)+1);
            } else {
                output.set(value, 1);
            }
        }
    return output;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        List<Integer> result = Result.countingSort(arr);

        bufferedWriter.write(
            result.stream()
                .map(Object::toString)
                .collect(joining(" "))
            + "\n"
        );

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Code explanation :

• Create ArrayList with 100 size with initialization 0. We can use nCopies() method of Collections class.
  
• Traverse through given List :
• Check if current element index value is 0 or not in Output List.
• If it is not 0, then get current index value from output list and increment its value by one.
• Otherwise simply add 1 at current index element. 

Output explanation :

Input : [1 1 3 2 1]

• Output List : [0, 0, 0, 0, 0]
• Current value = 1
• If condition : 
• output.get(1) = 0 | 0 != 0 becomes false
• Else condition :
• output.set(1, 1) | set 1 at index 1
  
  
• Output List : [0, 1, 0, 0, 0] 
• Current value = 1
• If condition : 
• output.get(1) = 1 | 1 != 0 becomes true
• output.set(1, output.get(1)+1); | set 2 at index 1
  
  
• Output List : [0, 2, 0, 0, 0]
• Current value = 3
• If condition : 
• output.get(3) = 0 | 0 != 0 becomes false
• Else condition :
• output.set(3, 1) | set 1 at index 3
  
  
• Output List : [0, 2, 0, 1, 0]
• Current value = 2
• If condition : 
• output.get(2) = 0 | 0 != 0 becomes false
• Else condition :
• output.set(2, 1) | set 1 at index 2
  
  
• Output List : [0, 2, 1, 1, 0]
• Current value = 1
• If condition : 
• output.get(1) = 2 | 2 != 0 becomes true
• output.set(1, output.get(1)+2); | set 3 at index 1
  
  
• Output List : [0, 3, 1, 1, 0] 

 

Other articles :

• Lonely Integer Hackerrank solution in Java | Find unique element in Java Array 
• Java program to check given alphabet is an uppercase or lowercase vowel or not