886.possible-bipartition.md

886. Possible Bipartition

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

The idea is to color the graph and see if there is conflict, we can run either DFS or BFS.

enum class Color { NONE, RED, BLUE }

class Solution {
    fun possibleBipartition(n: Int, dislikes: Array<IntArray>): Boolean {
        val graph = buildGraph(dislikes)
        val colors = Array<Color>(n + 1) { Color.NONE }
        for (i in 1..n) {
            if (colors[i] == Color.NONE)
                // if (!dfs(graph, i, Color.RED, colors)) return false
                if (!bfs(graph, i, colors)) return false
        }
        return true
    }

    private fun bfs(graph: HashMap<Int, HashSet<Int>>, source: Int, colors: Array<Color>): Boolean {
        val queue = ArrayDeque<Int>()
        var toColor = Color.RED
        queue.addLast(source)
        while (queue.isNotEmpty()) {
            val size = queue.size
            for (j in 0 until size) {
                val i = queue.removeFirst()
                if (colors[i] != Color.NONE) {
                    if (colors[i] != toColor) return false
                    else continue
                }
                colors[i] = toColor
                graph[i]?.forEach { adj ->
                    queue.addLast(adj)
                }
            }
            toColor = if (toColor == Color.RED) Color.BLUE else Color.RED
        }
        return true
    }

    private fun dfs(graph: HashMap<Int, HashSet<Int>>, i: Int, toColor: Color, colors: Array<Color>): Boolean {
        if (colors[i] != Color.NONE) {
            return colors[i] == toColor
        } 
        colors[i] = toColor

        val nextColor = if (toColor == Color.RED) Color.BLUE else Color.RED
        graph[i]?.forEach { adj ->
            if (!dfs(graph, adj, nextColor, colors)) return false
        }
        return true
    }

    private fun buildGraph(dislikes: Array<IntArray>): HashMap<Int, HashSet<Int>> {
        val graph = hashMapOf<Int, HashSet<Int>>()
        for (pair in dislikes) {
            val p1 = pair[0]
            val p2 = pair[1]
            if (!graph.containsKey(p1)) graph[p1] = hashSetOf<Int>()
            if (!graph.containsKey(p2)) graph[p2] = hashSetOf<Int>()
            graph[p1]!!.add(p2)
            graph[p2]!!.add(p1)
        }
        return graph
    }
}

• Time Complexity: O(N + E) where N represents the number of people and E represents the size of dislikes array.
• Space Complexity: O(N + E).