Approach #1: Insert Into Sorted Structure [Accepted] Intuition Let's add flowers in the order they bloom. When each flower blooms, we check it's neighbors to see if they can satisfy the condition with the current flower. Algorithm We'll maintain active , a sorted data structure containing every flower that has currently bloomed. When we add a flower to active , we should check it's lower and higher neighbors. If some neighbor satisfies the condition, we know the condition occurred first on this day. Complexity Analysis Time Complexity (Java): O(N \log N) O ( N lo g N ) , where N N is the length of flowers . Every insertion and search is O(\log N) O ( lo g N ) . Time Complexity (Python): O(N^2) O ( N 2 ) . As above, except list.insert is O(N) O ( N ) . Space Complexity: O(N) O ( N ) , the size of active . Approach #2: Min Queue [Accepted] Intuition For each contiguous block ("window") of k po...
Solution This article assumes you already have some confidence with graph algorithms , such as breadth-first search and depth-first searching . If you're familiar with those, but not with topological sort (the topic tag for this problem), don't panic, as you should still be able to make sense of it. It is one of the many more advanced algorithms that keen programmers tend to "invent" themselves before realizing it's already a widely known and used algorithm. There are a couple of approaches to topological sort; Kahn's Algorithm and DFS. A few things to keep in mind: The letters within a word don't tell us anything about the relative order. For example, the presence of the word kitten in the list does not tell us that the letter k is before the letter i . The input can contain words followed by their prefix, for example, abcd and then ab . These cases will never ...