In this challenge, you are given a list of words written in an alien language, where the words are sorted lexicographically by the rules of this language. Surprisingly, the aliens also use English lowercase letters, but possibly in a different order. Given a list of words written in the alien language, you have to return a string of unique lette…

alien-order.js

export function alienOrder(words) {
  const adjList = {};
  const indegreeMap = {};

  // initialize adjacency list and indegree map
  for (let i = 0; i < words.length; ++i) {
    const word = words[i];
    for (let j = 0; j < word.length; ++j) {
      const letter = word[j];
      indegreeMap[letter] = 0;
      adjList[letter] = new Set();
    }
  }

  // flag if we met an invalid case
  let exit = false;

  for (let i = 0; i < words.length - 1; ++i) {
    // compare each word with the next word
    const wordA = words[i];
    const wordB = words[i + 1];

    // lfag that says if we found a character mismatch
    let found = false;

    // iterate from 0 to min length of two words
    for (let j = 0; j < Math.min(wordA.length, wordB.length); ++j) {
      const charA = wordA[j];
      const charB = wordB[j];
      // compare two characters
      if (charA !== charB) {
        // if characters arent equal,
        // it means charB comes after charA
        found = true;
        if (!adjList[charA].has(charB)) {
          // add charB to adjList of charA (because charB comes after charA)
          adjList[charA].add(charB);
          // increment indegree of charB (because it has an incoming edge from charA)
          indegreeMap[charB] += 1;
          break;
        }
      }
    }

    // we haven't found a mismatch, and second word is longer than the first
    // it means we have the case when prefix comes after
    // no result can be found
    if (!found && wordB.length < wordA.length) {
      exit = true;
      break;
    }
  }

  // handle invalid case
  if (exit) {
    return "";
  }

  // start building our result with BFS
  let result = "";
  const queue = [];

  // add all vertices with indegree === 0 to start our BFS from
  Object.keys(indegreeMap).forEach((char) => {
    if (indegreeMap[char] === 0) {
      queue.push(char);
    }
  });

  while (queue.length > 0) {
    // pop character from the queue and add it to result
    // any character in the queue has indegree 0,
    // it means it can be added to the result because
    // all characters that had to go before this one, they are already processed
    const char = queue.shift();
    result += char;
    // iterate children of the character and decrement their indegree
    // because we have just processed the character that forms an incoming edge to them
    const children = adjList[char];
    children.forEach(childChar => {
      indegreeMap[childChar] -= 1;
      if (indegreeMap[childChar] === 0) {
        // if the new indegree of the child char is 0,
        // we add it to the queue to be processed
        queue.push(childChar);
      }
    });
  }

  // if our result length does not equal to the amount of the unique characters
  // it means we have a cycle in our graph
  // so the result is invalid
  if (result.length !== Object.keys(indegreeMap).length) {
    return "";
  }

  return result;
}

// tc: O(c) where c is the total number of characters
// initialization and building the adj list takes O(c) because we need to check every letter
// BFS is O(V+E)
// the complexity of BFS in this case depends on the amount of words and the amount of unique letters
// the amount of total characters is the bigger value, so it's O(C)
// sc: in this case, it's O(1) because we know that the total number of letters is 26, however, in general case, it depends on the number of unique letters and words