ysinjab

import (
    "fmt"
    "strings"
    "sort"
    "os"
    "io"
)
type DisjointSet struct {
	Nodes       []int
}

ysinjab

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */


func dfs(n *Node, visited map[*Node]*Node) *Node {

ysinjab

class Solution(object):
    def minCostConnectPoints(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        edges = []
        for i in range(len(points)):
            for j in range(i, len(points)):
                heapq.heappush(edges, (abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j))

ysinjab

class Solution(object):
    def maxProbability(self, n, edges, succProb, start, end):

        # it looks like dijsktra but with different relaxation
        g = collections.defaultdict(dict)
        for i in range(len(edges)):
            s = edges[i][0]
            d = edges[i][1]
            p = succProb[i]
            g[s][d] = g[d][s] = p

ysinjab

class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, k):
        # bellman-ford 
        p = [float('inf') for _ in range(n)]
        c = [float('inf') for _ in range(n)]
        p[src] = 0
        
        for i in range(k+1):
            for u, v, w in flights:
                c[v] = min(p[u]+w, c[v])

ysinjab

class Solution(object):
    def findOrder(self, num_courses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        # basically this is Kahn algorithm for topological sorting
        # I like it because it depends on the indegree centrality of the node
        degrees = collections.defaultdict(int)

ysinjab

class Solution(object):
    def myAtoi(self, s):
        """
        :type s: str
        :rtype: int
        """
        splitted = s.split(' ')
        for i in splitted:
            if not i:
                continue

ysinjab

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        # top down approach: function dp
        # state variables are (i, j) where i is index of text1 and j is index of text2
        # if both carachters are equal retrun 1 
        # else choose the max between the two remaining
        
        from functools import lru_cache
        @lru_cache(maxsize=None)

ysinjab

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        # top-down solution
#         holding_a_stock = 'HOLDING'
#         not_holding_any_stock = 'NOT_HOLDING'
        
#         @lru_cache(None)
#         def dp(i, holding_status):
#             if i == len(prices):
#                 return 0

ysinjab

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        
        # recursion
        # state is the current house we are painting with color c that has a cost + min of prev min
        # state variables are i, c
        # recurrence relation : dp(i, c) = cost[c] + min(dp(i + 1, c-1), dp(i + 1, c+1))
        # base case: i == len(costs) return 0
#         @lru_cache(None)
#         def dp(i, c):