Skip to main content

< Back to Data Structures and Algorithms

LeetCode 1791 · Graphs

Find Center of Star Graph

The node a star graph's edges all share: whichever of the first edge's ends is also in the second, then checked against the rest.

Step through it

edges (as a graph)
1234

Step 0 of 9

Output

Running… play or step to the end.

The code

/**
 * Determines the center node within a star graph.
 * @param {number[][]} edges
 * @return {number}
 */
 const findCenter = edges => {
    // Edge case: There can't be a center node.
    if (!edges || edges.length < 2) return 0
    
    // Saves the node that re-occurs on every edge.
    let consistentNode = 0
    
    // Find the node that exists on the both the first and second edge.
    if (edges[0][0] === edges[1][0] ||
        edges[0][0] === edges[1][1]
    ) {
        consistentNode = edges[0][0]
    } else if (edges[0][1] === edges[1][0] ||
               edges[0][1] === edges[1][1]
    ) {
        consistentNode = edges[0][1]
    }
    
    // Found a consisent node
    if (consistentNode) {
        // O(n) loop to iterate over every edge.
        for (let edge of edges) {
            // If the consistent node doesn't exist on the edge.
            if (edge[0] !== consistentNode &&
                edge[1] !== consistentNode
            ) {
                // No consistent node exists, exit the loop
                consistentNode = 0
                break
            }
        }
    }
    
    // Return the consistent node if it exists, otherwise return 0.
    return consistentNode
}

View it on GitHub (opens in a new tab)