title: Find the max value of the same length nails after hammered
body: <p>I'm trying to solve this problem:</p>
  
  <blockquote>
    <p>Given an array of positive integers, and an integer <em>Y</em>, you are allowed to replace at most <em>Y</em> array-elements with lesser values. Your goal is for the array to end up with as large a subset of identical values as possible. Return the size of this largest subset.</p>
    
    <p>The array is originally sorted in increasing order, but you do <em>not</em> need to preserve that property.</p>
    
    <p>So, for example, if the array is [10,20,20,30,30,30,40,40,40] and <em>Y</em>&nbsp;=&nbsp;3, the result should be 6, because you can get six 30s by replacing the three 40s with 30s. If the array is [20,20,20,40,50,50,50,50] and <em>Y</em>&nbsp;=&nbsp;2, the result should be 5, because you can get five 20s by replacing two of the 50s with 20s.</p>
  </blockquote>
  
  <p>Below is my solution with O(nlogn) time complexity. (is that right?) I wonder if I can further optimize this solution?</p>
  
  <p>Thanks in advance.</p>
  
  <pre class="lang-java prettyprint-override"><code>public class Nails {
  
      public static int Solutions(int[] A, int Y) {
          int N = A.length;
          TreeMap &lt; Integer, Integer &gt; nailMap = new TreeMap &lt; Integer, Integer &gt; (Collections.reverseOrder());
          for (int i = 0; i &lt; N; i++) {
              if (!nailMap.containsKey(A[i])) {
                  nailMap.put(A[i], 1);
              } else {
                  nailMap.put(A[i], nailMap.get(A[i]) + 1);
              }
          }
          List &lt; Integer &gt; nums = nailMap.values().stream().collect(Collectors.toList());
  
          if (nums.size() == 1) {
              return nums.get(0);
          }
  
          //else
          int max = nums.get(0);
          int longer = 0;
          for (int j = 0; j &lt; nums.size(); j++) {
              int count = 0;
              if (Y &lt; longer) {
                  count = Y + nums.get(j);
              } else {
                  count = longer + nums.get(j);
              }
              if (max &lt; count) {
                  max = count;
              }
              longer += nums.get(j);
          }
          return max;
      }
  
  
      public static void main(String[] args) {
          Scanner scanner = new Scanner(System.in);
          while (scanner.hasNext()) {
              String[] input = scanner.nextLine().replaceAll("\\[|\\]", "").split(",");
              System.out.println(Arrays.toString(input));
              int[] A = new int[input.length - 1];
              int Y = Integer.parseInt(input[input.length - 1]);
              for (int i = 0; i &lt; input.length; i++) {
                  if (i &lt; input.length - 1) {
                      A[i] = Integer.parseInt(input[i]);
                  } else {
                      break;
                  }
              }
              int result = Solutions(A, Y);
              System.out.println(result);
          }
      }
  }
  </code></pre>