Return certain element from Set based on ranking

Question

I'm working on a project where I have a number of unique strings in a Set (or it could be an array). I'm trying to write a function that returns the string in that Set with the highest "value".

The "value" is determined by a hierarchy that contains a number of other strings, each residing within their own level. For example:

Level 1 (Highest) A1, A2, A3, A4 ...

Level 2 B1, B2, B3, B4 ...

Level 3 (Lowest) C1, C2,C3 ...

So for example, if the strings in my initial Set are [C2, C3, A2, B1], then I'd expect A2 to be returned. In situations where there is a "value" tie, then the first string could be returned.

One potential solution might be to iterate through that hierarchy structure (which would maybe be an array of arrays) starting at the highest level, then checking to see if the currently iterated-on value is contained in the Set. If it is, then that value could be returned.

Can anyone think of a better way to structure / accomplish this though? Thank you!

Answer 1

Your general approach sounds reasonable, though a slightly better way would be to not have a hierarchy of arrays, but a hierarchy of sets. Checking whether an item exists in a Set is O(1), unlike an array, which is O(n). This way, the overall algorithm is O(n ^ 2), not O(n ^ 3).

for (const levelSet of hierarchy) {
  for (const str of inputStrings) {
    if (levelSet.has(str)) return str;
  }
}

Unless the level can be predicted from a string's structure without iterating through the hierarchy, I don't think there's a less complex solution.

If the level can be predicted without iterating - for example, if a string that starts with A is in the first hierarchy, and so on - it can probably be made less expensive by iterating over each string in the input instead, and not touching the hierarchy structure. (depending on the computation involved in determining the hierarchy level from a given string)