Bipartite Algorithm Intro

Graph Requirements

Output

Video Animation

Bipartite: https://www.youtube.com/watch?v=Zg6UAnAzGGs

Pseudo Code

Time Complexity

Space Complexity

IRL Use Case

What is Bipartite Algorithm

2001. Alien Dictionary ::1:: - Hard

Topics: Breadth First Search, Graph, Topological Sort

Intro

There is a foreign language which uses the latin alphabet, but the order among letters is not "a", "b", "c" ... "z" as in English. You receive a list of non-empty strings words from the dictionary, where the words are sorted lexicographically based on the rules of this new language. Derive the order of letters in this language. If the order is invalid, return an empty string. If there are multiple valid order of letters, return any of them. A string a is lexicographically smaller than a string b if either of the following is true: The first letter where they differ is smaller in a than in b. a is a prefix of b and a.length < b.length.

Example Input	Output
["z","o"]	"zo"
["hrn","hrf","er","enn","rfnn"]	"hernf"

Constraints:

The input words will contain characters only from lowercase 'a' to 'z'.

1 ≤ nums.length ≤ 100

1 ≤ words[i].length ≤ 100

Abstraction

Given a foreign language, derive the order of letters.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: Topological Sort using BFS - Advanced Graphs/Advanced Graphs

    def foreignDictionary(self, words: List[str]) -> str:
        
        # Why Topological Sort?
        # Each character -> node in directed graph
        # Edge (c1 -> c2) means -> c1 comes before c2 in alien dictionary
        # Topological sort -> Finding a valid order of characters
        # Finding a valid order of characters is equivalent to performing
        # a topological sort on this graph.
        # If cycle exists, no valid order exists

        # Note:
        # 1. Build a graph of character dependencies from adjacent words
        # 2. Count in-degrees for each character
        # 3. Use BFS to perform topological sort
        # 4. Detect cycles: if result length != total unique chars, return ""

        # Initialize graph and in-degree counts
        graph = defaultdict(set)  # char -> set of chars that come after it
        in_degree = {c: 0 for word in words for c in word}

        # Build graph edges based on adjacent words
        for i in range(len(words) - 1):
            word1, word2 = words[i], words[i+1]
            min_len = min(len(word1), len(word2))
            found_diff = False

            for j in range(min_len):
                c1, c2 = word1[j], word2[j]
                if c1 != c2:
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        in_degree[c2] += 1
                    found_diff = True
                    break

            # Edge case: prefix situation invalid, e.g., "abc" before "ab"
            if not found_diff and len(word1) > len(word2):
                return ""

        # BFS topological sort
        queue = deque([c for c in in_degree if in_degree[c] == 0])
        result = []

        while queue:
            c = queue.popleft()
            result.append(c)
            for nei in graph[c]:
                in_degree[nei] -= 1
                if in_degree[nei] == 0:
                    queue.append(nei)

        # Check for cycle
        if len(result) != len(in_degree):
            return ""

        res = "".join(result)


        # overall: time complexity O(C + W*L)
        # C = number of unique characters, W = number of words, L = average word length
        # overall: space complexity O(C + W*L) for graph and in-degree
        return res

LeetCode: Graphs II Bipartite