Network Delay Time - Python Solution

 There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2




Output: 2

class Solution(object):
    def networkDelayTime(self, times, N, K):
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))

        dist = {node: float('inf') for node in range(1, N+1)}
        seen = [False] * (N+1)
        dist[K] = 0

        while True:
            cand_node = -1
            cand_dist = float('inf')
            for i in range(1, N+1):
                if not seen[i] and dist[i] < cand_dist:
                    cand_dist = dist[i]
                    cand_node = i

            if cand_node < 0: break
            seen[cand_node] = True
            for nei, d in graph[cand_node]:
                dist[nei] = min(dist[nei], dist[cand_node] + d)

        ans = max(dist.values())
        return ans if ans < float('inf') else -1

 

String Transforms Into Another String - Python Solution

 Given two strings str1 and str2 of the same length, determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

 

Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.

Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        hashmap = {}
        hashset = set()
        
        for i in range(len(str1)):
            hashset.add(str2[i])
            if str1[i] in hashmap and hashmap[str1[i]] != str2[i]:
                return False
            hashmap[str1[i]] = str2[i]
        
        if str1 != str2 and len(hashset) == 26 and len(hashmap) == 26:
            return False
        return True
        
        

O(n) and O(n)

 

Maximal Square Python Solution

 Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if matrix is None or len(matrix) < 1:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        dp = [[0]*(cols+1) for _ in range(rows+1)]
        max_side = 0
        
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == '1':
                    dp[r+1][c+1] = min(dp[r][c], dp[r+1][c], dp[r][c+1]) + 1 # Be careful of the indexing since dp grid has additional row and column
                    max_side = max(max_side, dp[r+1][c+1])
                
        return max_side * max_side

            

Expressive Words - Python Solution

 Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii".  In these strings like "heeellooo", we have groups of adjacent letters that are all the same:  "h", "eee", "ll", "ooo".

For some given string S, a query word is stretchy if it can be made to be equal to S by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is 3 or more.

For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has size less than 3.  Also, we could do another extension like "ll" -> "lllll" to get "helllllooo".  If S = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = S.

Given a list of query words, return the number of words that are stretchy. 

 

Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

 

Constraints:

• 0 <= len(S) <= 100.
• 0 <= len(words) <= 100.
• 0 <= len(words[i]) <= 100.
• S and all words in words consist only of lowercase letters

class Solution(object):
    def expressiveWords(self, S, words):
        return sum(self.check(S,W) for W in words)
    def check(self,S,W):
        i,j,n,m = 0,0,len(S),len(W)
        for i in range(len(S)):
            if j<m and S[i] == W[j]: j+=1
            elif S[i-1:i+2] != S[i]*3 != S[i-2:i+1]: return False
        return j == m
    

O(noOfwords * len(largest word) SC: O(1)

Evaluate Division - Python Solution

 You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

 

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

 

Constraints:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj consist of lower case English letters and digits.

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = collections.defaultdict(dict)
        for (x,y),val in zip(equations,values):
            graph[x][y] = val
            graph[y][x] = 1.0/val
        
        def dfs(x,y,visited):
            if x not in graph or y not in graph:
                return -1.0
            if y in graph[x]:
                return graph[x][y]
            for i in graph[x]:
                if i not in visited:
                    visited.add(i)
                    temp = dfs(i,y,visited)
                    if temp == -1:
                        continue
                    else:
                        return graph[x][i] * temp
            return -1.0
      
        res = []
        for query in queries:
            res.append(dfs(query[0],query[1],set()))
        return res
       

TC: O(M*N) SC: O(N)

Number of Connected Components in an Undirected Graph - Python Solution

 Given n nodes labeled from 0 to n - 1 and 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:

Input: n = 5 and edges = [[0, 1], [1, 2], [3, 4]]

     0          3
     |          |
     1 --- 2    4 

Output: 2

Example 2:

Input: n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

     0           4
     |           |
     1 --- 2 --- 3

Output:  1

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

BFS:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = {x:[] for x in range(n)}
        for v1,v2 in edges:
            graph[v1].append(v2)
            graph[v2].append(v1)
        totalComponents = 0
        for i in range(n):
            queue = [i]
            totalComponents+= 1 if i in graph else 0
            for node in  queue:
                if node in graph:
                    queue+= graph[node]
                    del graph[node]
        return totalComponents

DFS:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = {x:[] for x in range(n)}
        for v1,v2 in edges:
            graph[v1].append(v2)
            graph[v2].append(v1)
        
        visited = set()
        def dfs(node,graph,visited):
            if node in visited:
                return
            visited.add(node)
            for nei in graph[node]:
                dfs(nei,graph,visited)
        totalComponents = 0
        for i in range(n):
            if i not in visited:
                dfs(i,graph,visited)
                totalComponents+=1
        return totalComponents

Union and Find:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(x,y):
            rx,ry = find(x),find(y)
            if rx != ry:
                parent[rx] = ry
        for x,y in edges:
            union(x,y)
        return len({find(x) for x in range(n)})

Decode Ways - Python Leetcode Solution

 A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

 

Example 1:

Input: s = "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with '0'. We cannot ignore a zero when we face it while decoding. So, each '0' should be part of "10" --> 'J' or "20" --> 'T'.

Example 4:

Input: s = "1"
Output: 1

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0,0]
        prev2 = 1
        prev1 = 0 if s[0] == '0' else 1
        final = 0
        for i in range(2,len(s)+1):
            cur = 0
            if s[i-1] != '0':
                cur += prev1
            two_digit = int(s[i-2:i])
            if two_digit >=10 and two_digit <=26:
                cur += prev2
            prev2,prev1 = prev1,cur
        return prev1
        

TC: O(n) SC: O(1)