-2
\$\begingroup\$

The task is to find the top two elements from the array without sorting. how can we achieve it? Can we use any DS to achieve this? Say tree? Please pour in your suggestions.

Between, iterative way of solving the problem is also one way. I have done that. Below is the code. I will also welcome if the below can be customized reasonably. Please help.

public static void main(String[] args) {

    System.out.println("Top Two elements from an array without sorting");

    int[] arr = {2,9,3,16,10,14};
    int n = arr.length;
    while(n!=0){
        int high = arr[0];
        for(int i=0;i<n;i++){
            if(high<arr[i])
                high = arr[i];
        }
        int j = 0;
        for(int i=0;i<n;i++){
            if(high!=arr[i]){
                arr[j] = arr[i];
                j++;
            }
        }
        n--;
        System.out.println("The renewed array is "+Arrays.toString(arr));
        System.out.println("The top element is "+high);
    }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Does this work? It doesn't seem to be getting the top two elements. In fact, most of this doesn't make sense. you're asking to enter the array size in, but never taking in data. \$\endgroup\$ – Blue Eyed Behemoth Apr 7 '16 at 17:12
  • \$\begingroup\$ Welcome to Code Review. Please clarify what you are asking. See How do I ask a good question? \$\endgroup\$ – Phrancis Apr 7 '16 at 17:18
  • \$\begingroup\$ @BlueEyedBehemoth: Now see my code. Edited. Have initialized values to my array \$\endgroup\$ – user3624000 Apr 7 '16 at 17:26
  • \$\begingroup\$ @user3624000 What is the second loop suppose to be doing? Looks like it's sorting. \$\endgroup\$ – Blue Eyed Behemoth Apr 7 '16 at 17:40
  • \$\begingroup\$ The code (in this version) is broken – it can't produce any results because your first loop will never end (n is initially non-zero and it's not modified inside the loop, so the loop condition (n!=0) will stay true forever). \$\endgroup\$ – CiaPan Apr 8 '16 at 6:30
1
\$\begingroup\$

Your code currently doesn't to what you say it does. That being said, this is my revision.

Note that I removed your while loop and one of your for loops. Your program must have printed many lines.

For the logic, I did <= when checking the values in the array so that if the array has 2 numbers that are the same, it still counts them. For instance, an array of {10, 9, 13, 2, 13, 6} will return 13 and 13, not 13 and 10

public static void main(String[] args) {
    System.out.println("Top Two elements from an array without sorting");
    int[] arr = {2,9,3,16,10,14};
    // Let the user know what the original array is
    System.out.println("The array is " + Arrays.toString(arr));
    // Renamed the array length variable to something a bit more meaningful
    int arrayLength = arr.length;

    // Need a variable for the highest and the second highest
    int high = 0;
    int secondHigh = 0;

    for(int i=0; i < arrayLength; i++)
    {
        // If the current index has a larger or equal value
        if(high <= arr[i])
        {
            // Check to see if high has a higher or equal value than the secondHigh,
            // if so assign the once high to the secondHigh.
            if(secondHigh <= high)
                secondHigh = high;
            // Assign high with new highest
            high = arr[i];

        // EDIT: Make sure it's also not less than the second highest.
        } else if(secondHigh <= arr[i]){ 
                secondHigh = arr[i];
        }
    }

    System.out.println("The two top elements are "+ high + " and " + secondHigh);
}
\$\endgroup\$
  • \$\begingroup\$ This doesn't give me top two elements. This says high = 16 and secondHigh = 9. The correct output is high = 16 and secondHigh = 14. \$\endgroup\$ – user3624000 Apr 8 '16 at 6:16
  • \$\begingroup\$ @user3624000 Try that \$\endgroup\$ – Blue Eyed Behemoth Apr 8 '16 at 15:21
  • \$\begingroup\$ It works. Thanks. You can even cut statement if(secondHigh <= high) secondHigh = high; and replace it with secondHigh = high; high = arr[i]; Also, this works at a O(n) time complexity. I am looking for a solution that reduces the time complexity. Thanks Anyway. \$\endgroup\$ – user3624000 Apr 9 '16 at 13:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.