Is Graph Bipartite?

 There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node uis adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).
• There are no parallel edges (graph[u] does not contain duplicate values).
• If v is in graph[u], then u is in graph[v] (the graph is undirected).
• The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and Bsuch that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

 

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

 

Constraints:

• graph.length == n
• 1 <= n <= 100
• 0 <= graph[u].length < n
• 0 <= graph[u][i] <= n - 1
• graph[u] does not contain u.
• All the values of graph[u] are unique.
• If graph[u] contains v, then graph[v] contains u.

class Solution {

public:

    bool isBipartite(vector<vector<int>>& graph) {

        set<int> set_a;

        set<int> set_b;

        bool ans = true;

        vector<bool> visited(graph.size(), false);

       for (int i = 0; i < graph.size(); i++) {

           if (!visited[i]) {

                dfs(graph, i, visited, set_a, set_b, ans);

                if (!ans) {

                    return false;

                }

           }

       }

        return ans;

    }

    

    void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited,

            set<int>& set_a, set<int>& set_b, bool& ans) {

        if (visited[node] == true || !ans) {

            return;

        }

        visited[node] = true;

        for (auto neighbor : graph[node]) {

            if (set_a.count(node) != 0) {

                if (set_a.count(neighbor) != 0) {

                    ans = false;

                    return;

                }

                set_b.insert(neighbor);

            } else if (set_b.count(node) != 0) {

                if (set_b.count(neighbor) != 0) {

                    ans = false;

                    return;

                }

                set_a.insert(neighbor);

            } else {

                set_a.insert(node);

                if (set_a.count(neighbor) != 0) {

                    ans = false;

                    return;

                }

                set_b.insert(neighbor);

            }

            dfs(graph, neighbor, visited, set_a, set_b, ans);

        }

    }

};

================ Space optimized =========

https://zxi.mytechroad.com/blog/graph/leetcode-785-is-graph-bipartite/

Solution: Graph Coloring

For each node

• If has not been colored, color it to RED(1).
• Color its neighbors with a different color RED(1) to BLUE(-1) or BLUE(-1) to RED(-1).

If we can finish the coloring then the graph is bipartite. All red nodes on the left no connections between them and all blues nodes on the right, again no connections between them. red and blue nodes are neighbors.

Time complexity: O(V+E)

Space complexity: O(V)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

  bool isBipartite(vector<vector<int>>& graph) {

    const int n = graph.size();

    vector<int> colors(n);

    for (int i = 0; i < n; ++i)

      if (!colors[i] && !coloring(graph, colors, 1, i))

        return false;

    return true;

  }

private:

  bool coloring(const vector<vector<int>>& graph, vector<int>& colors, int color, int node) {    

    if (colors[node]) return colors[node] == color;

    colors[node] = color;

    for (int nxt : graph[node])

      if (!coloring(graph, colors, -color, nxt)) return false;

    return true;

  }

};

============= 2nd time ========

    bool isBipartite(vector<vector<int>>& graph) {

        int size = graph.size();

        if (size == 0) {

            return false;

        }

        vector<int> colors(size, -1);

        vector<bool> visited(size, false);

        bool ans = true;

        for (int i = 0; i < visited.size(); i++) {

            bool node = visited[i];

            if (!node) {

                ans = helper(i, graph, colors, 1, visited);

                if (!ans) {

                    return false;

                }

            }

        }

        return true;

    }

    

    bool helper(int start, vector<vector<int>>& graph, vector<int>& colors, int color, vector<bool>& visited) {

        if (colors[start] == color) {

            return false;

        }

        int new_color = (color + 1) % 2;

        colors[start] = new_color;

        if (visited[start]) {

            return true;

        }

        visited[start] = true;

        for (auto neighbor : graph[start]) {

            if (!helper(neighbor, graph, colors, new_color, visited)) {

                return false;

            }

        }

        return true;

    }

    ============================ Iterative one ==========

class Solution {

public:

    bool isBipartite(vector<vector<int>>& graph) {

        int n = graph.size();

        vector<int> color(n, -1);

        for (int start = 0; start < n; ++start) {

            if (color[start] == -1) {

                stack<int> stk;

                stk.push(start);

                color[start] = 0;

                while (!stk.empty()) {

                    int node = stk.top();

                    stk.pop();

                    for (int neigh : graph[node]) {

                        if (color[neigh] == -1) {

                            stk.push(neigh);

                            color[neigh] = color[node] ^ 1;

                        } else if (color[neigh] == color[node]) {

                            return false;

                        }

                    }

                }

            }

        }

        return true;

    }

};

Range sum BST

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].

 

Example 1:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

class Solution {

public:

    int rangeSumBST(TreeNode* root, int low, int high) {

        int ans = 0;

        helper(root, low, high, ans);

        return ans;

    }

    

    void helper(TreeNode* root, int low, int high, int& ans) {

        if (root == NULL) {

            return;

        }

        helper(root -> left, low, high, ans);

        if (root -> val >= low && root -> val <= high) {

            ans += root -> val;

        } else if (root -> val > high) {

            return;

        }

        helper(root -> right, low, high, ans);

    }

};

 

487 Max Consecutive Ones II

Problem:

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

Example 1:

Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
    After flipping, the maximum number of consecutive 1s is 4.

Note:

1. The input array will only contain 0 and 1.
2. The length of input array is a positive integer and will not exceed 10,000

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, zero = 0, left = 0, k = 1;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) ++zero;
            while (zero > k) {
                if (nums[left++] == 0) --zero;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

========= (can only be used for a at most 1 flip. Generic solution is above. Above can be used

for multiple flips)

 class Solution {

public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, cur = 0, cnt = 0;
        for (int num : nums) {
            ++cnt;
            if (num == 0) {
                cur = cnt;
                cnt = 0;
            } 
            res = max(res, cnt + cur);
        }
        return res;
    }
};

=========

The above method cannot be used in the case of follow up, because nums[left] needs to access the previous number. We can save all the positions of 0 we encountered, so that we know where to move when we need to move left:
 
Solution three:
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int res = 0, left = 0, k = 1;
        queue<int> q;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) q.push(right);
            if (q.size() > k) {
                left = q.front() + 1; q.pop();
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};