One of my friends asked me about a coding challenge that their lecturer gave them as an exercise. I got a solution working to solve it. But I think the solution is too lengthy for a categorised question as easy. So, I would like to ask if there's a more straightforward way to solve the challenge.

Have the function third_greatest() that takes an array of strings and returns the third-largest word. So, for example: if the array is ["hello", "world", "before", "noon"], the output should be "world" because "before" is six letters long, and "hello" and "world" are both 5, but the output should be "world" because it appeared as the last five-letter word in the array. If the array was ["hello", "world", "after", "noon"], the output should be "after" because the first three words are all five letters long, so return the last one. The array will have at least three strings, and each string will only contain letters.

The solution I've come up with used HashMap to store the strings in a dictionary manner. The Hashmap will store data in the form of Integer and ArrayList, the length and the words that have that length. Once the code finished iterating the String array and put the respective strings into their separate group, I then extracted all the keys (length) found in the array from the Hashmap, sorting them in ascending order. After that, all the values in the Hashmap's ArrayList will be transferred to another ArrayList. Finally, it returns the third String of the new ArrayList to the function caller.

Thanks.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;


class Main {
    public static void main (String args[]) {
        String test[] = {"hello", "world", "before", "noon"};
        System.out.println(third_greatest(test));
    }

    public static String third_greatest(String words[]) {
        HashMap<Integer, ArrayList<String>> words_length = new HashMap<Integer, ArrayList<String>>();
        for (String word : words) {
            int length = word.length();
            if (words_length.containsKey(length)) {
                words_length.get(length).add(word);
            } else {
                ArrayList<String> temp = new ArrayList<String>();
                temp.add(word);
                words_length.put(length, temp);
            }
        }
        Object keys[] = words_length.keySet().toArray();
        Integer sorted[] = new Integer[words_length.size()];
        for (int x = 0; x < keys.length; x  ) {
            sorted[x] = (Integer)keys[x];
        }
        Arrays.sort(sorted);
        ArrayList<String> results = new ArrayList<String>();
        for (int x = sorted.length - 1; x >= 0; x--) {
            ArrayList<String> temp = words_length.get(sorted[x]);
            for (String word : temp) {
                results.add(word);
            }
        }
        return results.get(2);
    }
}

CodePudding user response：

Sort the stream is descending order of their lengths and skip first 2 elements. Requires java 11

import java.util.*;

class ThirdLongest
{
    public static void main(String[] args) {
        String[] words={"Word","Longer Word","Longest Word Here"};
        
        String word=Arrays.stream(words)
            .sorted((s1,s2)->Integer.compare(s2.length(),s1.length()))
            .skip(2)
            .findFirst()
            .get();
                
       System.out.println(word);
    }
}

Or

Just sort the Array in descending order and return 3rd element

Arrays.sort(words,(s1,s2)->Integer.compare(s2.length(),s1.length()));

return words[2];

CodePudding user response：

As noted by others, the simple solution is to just sort the array into order based on the String size (or whatever the ordering criterion is). Then take the third from last element from the sorted list.

That is an O(NlogN) solution, since the sorting step is O(NlogN).

Here is an O(N) solution.

• Take the first 3 strings from the input array and sort them. This array of 3 will represent the third, second, and largest elements of the input array so far.
• Iterate over the rest of the array elements:
  • If the element is less that the current third largest element ignore it
  • Otherwise:
    • Add the current element to the array of 3.
    • Sort it
    • Remove the first (smallest) element.

At the end, you will have performed O(N) tests and at most O(N) sorts of 3 or 4 element arrays. For an overall complexity of O(N).

There is scope for micro-optimizing the sort steps to avoid loops and unnecessary array creation and copying.

Note: if the input lists are always going to be small, then this (more complex) solution is not worth the effort. Having a better algorithmic complexity does not guarantee better performance when the scaling variables have small values.