Second Largest Non Repeating Number in an Array

Question

I am trying to solve this problem in which we have an array in which some elements are unique, and some are repetitive. For example, int[] array = { 4, 4, 6, 1, 2, 3, 5, 5 };.

So, the second largest non-repeating number would be 3. My output is coming as 2. The code isL

public class SecondLargestNonRepeatingNumber {

    public static void main(String[] args) {

        int[] array = { 4, 4, 6, 1, 2, 3, 5, 5 };
        System.out.println(process(array));
    }

    public static int process(int[] array) {
        int counter2 = 0;
        int result = 0;
        Arrays.sort(array);
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int count = array.length;
        int index = 0;
        while(count>0) {
            
            if(map.containsKey(array[index])) {
                map.put(array[index], map.get(array[index])+1);
            }else {
                map.put(array[index], 1);
            }
            index++;
            count--;
        }
        
        int maxNum = Integer.MIN_VALUE;

//      for (int i = 0; i < array.length; i++) {
//          for (int j = i + 1; j < array.length; j++) {
//              if (array[i] != array[j] && array[i] > maxNum) {
//                  maxNum = array[i];
//                  counter2++;
//              }
//              if (counter2 == 2)
//                  break;
//          }
//      }
        
    for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
        if(entry.getValue()==1) {
            if(entry.getKey() > maxNum) {
                maxNum = entry.getKey(); 
            }
            counter2++;
        }
        if(counter2==2) {
            result = entry.getKey();
        }
    }

        return result;
    }

}

Hint: asking other people to tell you what is wrong about your code ... sure works, but it shouldn't be your first solution. Instead: simply add print statements to your code, or learn how to use a debugger. You see, programming is actually ... mostly about "figuring why my code doesnt do what I expect it to do". — GhostCat, Apr 07 '22 at 11:32
And note that there are plenty of helpful operations in Map these days. See https://stackoverflow.com/questions/81346/most-efficient-way-to-increment-a-map-value-in-java for example. — GhostCat, Apr 07 '22 at 11:33

score 0 · Answer 1 · answered Apr 07 '22 at 11:35

Sorry, but now when I tried it again, I found this solution that is working -

public class SecondLargestNonRepeatingNumber {

    public static void main(String[] args) {

        int[] array = { 4, 4, 6, 1, 2, 3, 5, 5 };
        System.out.println(process(array));
    }

    public static int process(int[] array) {
        int counter2 = 0;
        int result = 0;
        Arrays.sort(array);
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int count = array.length;
        int index = 0;
        while(count>0) {
            
            if(map.containsKey(array[index])) {
                map.put(array[index], map.get(array[index])+1);
            }else {
                map.put(array[index], 1);
            }
            index++;
            count--;
        }
        
        int maxNum = Integer.MIN_VALUE;

//      for (int i = 0; i < array.length; i++) {
//          for (int j = i + 1; j < array.length; j++) {
//              if (array[i] != array[j] && array[i] > maxNum) {
//                  maxNum = array[i];
//                  counter2++;
//              }
//              if (counter2 == 2)
//                  break;
//          }
//      }
        List<Integer> list = new ArrayList<Integer>();
        
    for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
        if(entry.getValue()==1) {
            
                list.add(entry.getKey());
            
            counter2++;
        }
        Collections.sort(list);
    }

        return list.get(list.size()-2);
    }

}

you don't need maxNum, or that counter2. and you don't need to sort again. this should do: if ( map.entrySet().size() < 2 ) return -1; // can't find the element, because there aren't enough in the map final List> singles = map.entrySet().stream().filter(e -> e.getValue() == 1).collect(Collectors.toList()); return singles.get(singles.size() - 2).getKey(); — Stultuske, Apr 07 '22 at 11:40
Yes, I didnt try it as in Java 8 way. Thanks for the answer using Streams API. — user3454622, Apr 07 '22 at 11:45

Sash Sinha · Answer 2 · 2022-04-07T14:57:51.773

Instead of using a standard HashMap and then sorting you could instead use a TreeMap that maintains sorted order of the keys for you:

import java.util.Arrays;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import java.util.stream.Collectors;

public class SecondLargestNonRepeatingNumber {
    public static void main(String[] args) {
        int[] array = { 4, 4, 6, 1, 2, 3, 5, 5 };
        System.out.println(Arrays.toString(array));
        System.out.printf("Second largest non repeating number: %d%n",
            getSecondLargestNonRepeatingNumber(array));
    }

    public static int getSecondLargestNonRepeatingNumber(int[] array) {
        Map<Integer, Integer> counts = new TreeMap<>();
        for (int x : array) {
            counts.merge(x, 1, Integer::sum);
        }
        counts.entrySet().stream()
            .filter(e -> !e.getValue().equals(1))
            .map(Entry::getKey)
            .collect(Collectors.toList())
            .forEach(counts.keySet()::remove);
        return counts.keySet().stream().skip(counts.size() - 2).findFirst()
            .orElseThrow(); // When there is less than 2 unique numbers in array.
    }
}

Output:

[4, 4, 6, 1, 2, 3, 5, 5]
Second largest non repeating number: 3

Second Largest Non Repeating Number in an Array

2 Answers2