Number of Connected Components in an Undirected Graph (Python)

66. Number of Connected Components in an Undirected Graph

Question Link : check here

Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

0 3

| |

1 --- 2 4

Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2.

Example 2:

0 4

| |

1 --- 2 --- 3

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1.

Note:

You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.

Solution :

class Solution:
    def counComponents(self, n: int, edges : List[List[int]]) -> int:
        p = [ i for i in range(n)]
        r = [1] * n
        
        def find(n1) :
            ans = n1
            
            while ans != p[ans] :
                p[ans] = p[p[ans]]
                ans = p[ans]
            
            return ans
        
        def union(n1, n2):
            p1, p2 = find(n1), find(n2)
            
            if p1==p2:
                return 0
            
            if r[p2] > r[p1]:
                p[p1] = p2
                r[p2] += r[p1]
                
            else:
                p[p2] = p1
                r[p1] += r[p2]
                
            return 1
        
        ans = n #5 - 1 - 1 - 1 = 2
        
        for n1, n2 in edges:
            ans -= union(n1,n2)
        return ans

Explaination :

Comments

Leetcode 424. Longest Repeating Character Replacement. Python (Sliding Window)

424 . Longest Repeating Character Replacement You are given a string s and an integer k . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations . Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. Constraints: 1 <= s.length <= 10 5 s consists of only uppercase English letters. 0 <= k <= s.length Solution : class Solution: def characterReplacement(self, s: str, k: int) -> int: hm = {} ans = 0 ...

Leetcode 371. Sum of Two Integers. C++ / Java

371 . Sum of Two Integers Given two integers a and b , return the sum of the two integers without using the operators + and - . Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5 Constraints: -1000 <= a, b <= 1000 Solution : C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java : class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Two Sum - Leetcode 1 - HashMap - Python

1. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashmap = {} # val : index for i,n in enumerate(nums): diff = target - n if diff in hashmap: return [hashmap[diff],i] hashmap[n]=i return Explained :

LEETCODE SOLUTIONS

Search This Blog