Finding the third largest string from an array of strings in Java

Question

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);
    }
}

You could also use the quick-select algoritm; I have a suspicion that that would be even faster in practice because it doesn't copy, and doesn't need to sort the whole list. — Neil
– Neil, Commented May 15, 2022 at 5:40

Sync it · Accepted Answer · 2022-05-15 04:10:55Z

2

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];

answered May 15, 2022 at 4:10

Sync it

1,1982 gold badges16 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Stephen C · Accepted Answer · 2022-05-15 04:52:21Z

1

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.

edited May 15, 2022 at 4:52

answered May 15, 2022 at 4:18

Stephen C

723k95 gold badges849 silver badges1.3k bronze badges

4 Comments

Leonlit Over a year ago

Yes, this would also work if there is a constraint on how many resources we could use in the challenge. I still can't upvote, but thanks for the help.

Stephen C Over a year ago

What constraint? What resources? (Why can't you upvote? Anyone can upvote answers to their questions.)

SeanH Over a year ago

I think this is a good idea when meeting very large amount of input data.

Stephen C Over a year ago

Yea ... and for small sized input arrays, the extra code complexity is not worth the improved algorithmic complexity. (Complexity is not performance ...)

Collectives™ on Stack Overflow

Finding the third largest string from an array of strings in Java

2 Answers 2

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related