Exit

Leetcode Notes

posted on July 09, 2024, last updated on Saturday, November 23, 2024 at 10:51 AM

1701. Average waiting time

A restaurant with single chef,

customers[i] = [arrival_i, time_i]

Chef prepares food for customers in the order they were given in the input.

return the average waitiing time of all customers

this question can be modelled as a non-preemptive single process at a time scheduling model.

Intuitative solution (in Python3):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        # FCFS scheduling
        customers[0].append(customers[0][0] + customers[0][1])
        total_wait_time = customers[0][1]

        for i in range(1, len(customers)):
            prev_customer = customers[i-1]
            customer = customers[i]

            if customer[0] < prev_customer[-1]:
                customer.append(prev_customer[-1] + customer[1])
            else:
                customer.append(customer[0]+customer[1])
            
            total_wait_time += customer[2] - customer[0]
            

        
        return total_wait_time/len(customers)

Java Tips:

1
2

// to initialize an array with the length of an existing array arr
int newArr[] = new int[arr.length];

Optimized:

  • it is not necessary to save all the finish times of each customer
  • in the line total_wait_time += customer[2] - customer[0] , we just need to save the finish time of the previous customer, use a variable to iterate
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public double averageWaitingTime(int[][] customers) {
        // finish time of the prev customer
        int ft = 0;
        double allWaitingTime = 0;

        for(int i=0; i<customers.length; i++) {
            // current customer arrived later than the prev customer ends
            if (customers[i][0] > ft) {
                ft = customers[i][0] + customers[i][1];
            } 
            // current customer arrived no later than the prev customer ends
            else {
                ft = ft + customers[i][1];
            }
            allWaitingTime += ft-customers[i][0];
        }
        return allWaitingTime/customers.length;       
    }
}

1598. Crawler log folder

A very easy question…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int minOperations(String[] logs) {
        int layer = 0;
        
        for(int i=0; i<logs.length; i++) {
            if(logs[i].equals("../")) {
                layer = Math.max(0, layer-1);
            }
            else if (logs[i].equals("./")) {
                // no action - current dir
            } else {
                layer++;
            }
        }

        return layer;
    }
}

1717. Maximum score from removing substrings

Preservation of Opportunities:

  • Removing higher-scoring pairs first does not diminish the opportunity to remove lower-scoring pairs later. For instance, after all “ba” pairs are removed from the string, it still contains “ab” pairs if they existed initially.
  • If we reverse this order, i.e., remove lower-scoring pairs first, we might miss out on higher-scoring pairs that could have been formed by the initial configuration of the string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        # intuitive - recursion and search

        ab = "ab"
        ba = "ba"

        first = ""
        second = ""
        maxxy = max(x,y)
        minxy = min(x,y)

        if x>y:
            first = ab
            second = ba
        else:
            first = ba
            second = ab

        st = []

        it = 0
        score = 0

        while it < len(s):
            curr = s[it]
            it += 1
            if len(st) == 0:
                st.append(curr)
                continue
                
            prev = st[-1]

            
            if prev+curr == first:
                score += maxxy
                st.pop()

            else:
                st.append(curr)
            
           
        
        s = "".join(st)
        st = []

        it = 0

        while it < len(s):
            curr = s[it]
            it += 1
            if len(st) == 0:
                st.append(curr)
                continue
                
            prev = st[-1]

            
            if prev+curr == second:
                score += minxy
                st.pop()

            else:
                st.append(curr)
            
            
        

        return score

1530. Number of good leaf node pairs

  • use BFS - “distance” indicates that we need to search for pairs layer by layer
  • construct a graph is necessary since we need to search bidirectionally – than tree having one-way references
  • when searching in each layer, use the length of the queue as the number of nodes of this layer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    
    def _traverse_tree(self, curr_node: TreeNode, prev_node: TreeNode, graph: dict, leaf_nodes: set):
        if curr_node is None:
            return
        if curr_node.left is None and curr_node.right is None:
            leaf_nodes.add(curr_node)
        
        if prev_node is not None:
            if prev_node not in graph:
                graph[prev_node] = []
            graph[prev_node].append(curr_node)

            if curr_node not in graph:
                graph[curr_node] = []
            graph[curr_node].append(prev_node)
        
        self._traverse_tree(curr_node.left, curr_node, graph, leaf_nodes)
        self._traverse_tree(curr_node.right, curr_node, graph, leaf_nodes)
 
    def countPairs(self, root: TreeNode, distance: int) -> int:
        graph = {}
        leaf_nodes = set()

        self._traverse_tree(root, None, graph, leaf_nodes)

        count = 0

        # begin of DFS

        for leaf in leaf_nodes:
            queue = []
            seen = set()
            queue.append(leaf)
            seen.add(leaf)

            # visiting all nodes, start from the leaf node (distance is 0 at this time)
            for i in range(distance+1):
                size = len(queue)
                #print(f"leaf:{leaf.val}, distance:{i}, size:{size}")
                # nodes of this distance
                # visit all nodes of i distance
                # add all nodes of i+1 distance
                for j in range(size):
                    curr_node = queue.pop(0) # bfs -- queue -> popleft
                    if curr_node in leaf_nodes and curr_node != leaf:
                        count += 1 # a satisfied leaf node has been visited
                    if curr_node in graph:
                        for _ in graph[curr_node]:
                            if _ not in seen:
                                queue.append(_)
                                seen.add(_)
        
        return count//2

1380. Lucky numbers in a matrix

  • Since matrix contains distinct numbers – we just need to get two sets, one is max values in cols and another is min values in rows.

  • The intersection of this two sets is the answer.

    Proof that there is only one lucky numbers in a matrix – proof by contradicary

    • suppose that in a matrix, if two lucky numbers, X and Y exist

      1
2

      a b X c
d Y e f

    • since X is a lucky number - min of the row and max of the col: X < b and X > e

      • in an axis: —-e—-X—-b—-

    • Y is also a lucky number: Y < e and Y > b

      • in the above axis: –Y?—e—X—b—Y?—

    • a contradiction arise - hence, only one lucky number can exist.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        col_maxs = set()
        row_mins = set()

        for i in range(len(matrix)):
            row_mins.add(min(matrix[i]))
        
        m_T = list(zip(*matrix))
        for i in range(len(m_T)):
            col_maxs.add(max(m_T[i]))

        """
        for i in range(len(matrix[0])):
            col_max = -1
            for j in range(len(matrix)):
                elem = matrix[j][i]
                if elem > col_max:
                    col_max = elem
        
            col_maxs.add(col_max)
        """

        """
        class Solution:
            def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
                return set(map(min,matrix)) & set(map(max,zip(*matrix)))
        """

        return list(col_maxs.intersection(row_mins))

912. Sort an array - o(nlogn) complexity

  • although quicksort is an optimized sorting algorithm, however in worst case, it takes o(n^2) times.

    • quicksort

      • quicksort() and partiton()
      • use index i to label the position that all elem before index i is less than the pivot.
      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

      class Solution {
    public int[] sortArray(int[] nums) {
        quicksort(nums, 0, nums.length-1);
    
        return nums;
    }
    
    private static void quicksort(int[] nums, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(nums, low, high);
    
            quicksort(nums, low, partitionIndex-1);
            quicksort(nums, partitionIndex+1, high);
        }
    }
    
    private static int partition(int[] nums, int low, int high) {
        int pivot = nums[high];
    
        int i = (low-1);
    
    
        for(int j=low; j<= high; j++) {
            if (nums[j] <= pivot) {
                i++;
    
                // all elements before index at i is less than the pivot
                // therefore, if elem at j is less than the pivot
                // swap elem at j with elem at i
                // in special circumstance - low...j is all less than the pivot, the swapping swaps the element by itself
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    
        return i;
    }
}

2418. Sort the people

  • easy solution - “distinct value in heights” - create a map mapping height to name, then sort the keys (heights), output the names in the sorted order.
  • Or, sorting manually with quicksort.
1
2
3
4
5
6
7

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        height_dict = {h:n for h, n in zip(heights, names)}

        sorted_keys = sorted(list(k for k in height_dict.keys()), reverse=True)
        
        return [height_dict[height] for height in sorted_keys]

1636. Sort array by increasing frequency

  • Count the frequency for each number into pairs

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

    # initial attempt
class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        reversedlookup = {}
  
        n_min = -100
        n_max = 100
  
        frequency = [0 for _ in range(n_min, n_max+1)]
          
        for num in nums:
            frequency[num-n_min] += 1
          
        for i in range(len(frequency)):
            num = i+n_min
            freq = frequency[i]
            if freq > 0:
                if freq in reversedlookup:
                    reversedlookup[freq].append(num)
                else:
                    reversedlookup[freq] = [num]
          
        result = []
        sorted_keys = sorted(reversedlookup.keys())
          
        for k in sorted_keys:
            for elem in sorted(reversedlookup[k], reverse=True):
                for i in range(k):
                    result.append(elem)
          
  
        return result

  • Sort the frequency by key

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        freq = {}
  
        for n in nums:
            if n in freq:
                freq[n] += 1
            else:
                freq[n] = 1
          
        result = sorted(nums, key = lambda x: (freq[x], -x)) # by the frequency first, if they have the same frequency, sort the numbers in decreasing order
  
        return result

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

2191. Sort the jumbled numbers

  • design a key that jumbles numbers.
  • use sorted to sort nums using that key
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def convert(self, mapping, num):
        if num == 0:
            return mapping[0]

        val = 0
        i = 0

        while num != 0:
            digit = num % 10
            num = num//10
            val += mapping[digit] * 10**i
            i+=1

        return val

    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        
        return sorted(nums, key=lambda x: self.convert(mapping, x))

164. Maximum gap

  • Vanilla approach - sort then count

    • however this violates the restriction that you must write an algorithm that runs in linear time and uses linear extra space.

      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

      class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
    
        max_gap = -1
        sorted_nums = sorted(nums)
    
        for i in range(len(sorted_nums)-1):
            curr_n = sorted_nums[i]
            next_n = sorted_nums[i+1]
    
            max_gap = max(next_n-curr_n, max_gap)
            
        return max_gap

  • Hence we can consider bucket sort - where we compare the gap between adjacent buckets

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        low, high, n = min(nums), max(nums), len(nums)
  
        if n <= 2 or high == low: return high - low
  
        buckets = defaultdict(list)
  
        for num in nums:
            bucket_index = n-2 if num == high else ((num - low)*(n-1))//(high-low) # the index of the bucket
            buckets[bucket_index].append(num)
  
          
        candidates = [[min(buckets[i]), max(buckets[i])] for i in range(n-1) if buckets[i]]
  
        max_gap = -1
        #for k in buckets.keys():
            #print(k, buckets[k])
        for i in range(len(candidates)-1):
            # min: next bucket #max: curr bucket
            max_gap = max(max_gap, candidates[i+1][0] - candidates[i][1])
          
        return max_gap

1334. Find the city with the smallest number of neighbors at a threshold distance

  • BFS won’t suffice for this question! – it can only visit a node once but there will be circumstance that two paths using the same node.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

    class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # solution - BFS with threshold cut
          
      
        graph = {}
        candidates = []
        # notes: init the graph map first, in case there may have city with no neighbour -- wont be added to keys when building the graph
        for city_no in range(n):
            graph[city_no] = []
            candidates.append([city_no, 0])
  
        for edge in edges:
            node_0 = edge[0]
            node_1 = edge[1]
            distance = edge[2]
              
            if node_0 in graph:
                graph[node_0].append([node_1, distance])
            else:
                graph[node_0] = [[node_1, distance]]
  
            if node_1 in graph:
                graph[node_1].append([node_0, distance])
            else:
                graph[node_1] = [[node_0, distance]]
              
        print(graph)
  
        for node in graph:
            queue = []
            visited = set()
              
            queue.append([node, 0, 0])
                        # node, accumulated distance, city_visited
  
            most_city_visited = -1
              
            while (len(queue) > 0):
                curr = queue.pop(0)
                city = curr[0]
                if city in visited:
                    continue
                  
                acc_dist = curr[1]
                  
                if acc_dist > distanceThreshold:
                    continue
  
                visited.add(city)
                most_city_visited += 1
                city_visited = curr[2]
  
                print("startcity", node, "visiting", city, "city_visited", most_city_visited, 'acc_dist', acc_dist)
                  
                for edge in graph[city]:
                    neighbour = edge[0]
                    distance = edge[1]+acc_dist
                    if neighbour not in visited:
                        queue.append([neighbour, distance, city_visited+1])
              
            candidates[node] = [node, most_city_visited]
          
          
                                                                  #dsc city_visited #asc city_no
        sorted_by_name = list(sorted(candidates, key=lambda pair: [pair[1], -pair[0]]))
        print(sorted_by_name)
  
        return sorted_by_name[0][0]

  • The best solution should be using the Floyd-Warshall algorithm

    • with $O(n^3)$ time complexity and $O(n^2)$ space complexity.
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

    class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        # large value to represent inf
        INF = int(1e9+7)
          
        distance_matrix = [[INF] * n for _ in range(n)]
  
        for i in range(n):
            distance_matrix[i][i] = 0
  
        for start, end, weight in edges:
            distance_matrix[start][end] = weight
            distance_matrix[end][start] = weight
  
        self.floyd(n, distance_matrix)
  
        return self.get_city_with_fewest_reachable(n, distance_matrix, distanceThreshold)
  
		# a n^3 algorithm
    def floyd(self, n, distance_matrix):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    # compare the distance of previous path and the path passing by node k
                    distance_matrix[i][j] = min(
                        distance_matrix[i][j],
                        distance_matrix[i][k] + distance_matrix[k][j]
                    )
          
      
    def get_city_with_fewest_reachable(self, n, distance_matrix, distanceThreshold):
        fewest_city_id = -1
        fewest_reachable_cities = n+1
        for start_city in range(n):
            count = 0
            for dest_city in range(n):
                if start_city != dest_city and distance_matrix[start_city][dest_city] <= distanceThreshold:
                    count += 1
              
            if count <= fewest_reachable_cities:
                fewest_reachable_cities = count
                fewest_city_id = start_city
          
  
        return fewest_city_id

2976. Minimum cost to convert string I

  • actually it is a application of searching the shortest path between each two nodes in a graph
  • the tuple (original, changed, cost) describes the edges in the graph
    • need to notice that: there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].
  • it is possibly that one letter cannot reach another letter through exchanges, so If it is impossible to convert source to target, return -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class Solution:
    # consider using floyd-warshall
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        self.INF = 10**9
        alphabet_lookup, alphabet_matrix = self.floyd(source ,target, original, changed, cost)
        print(alphabet_lookup, alphabet_matrix)
        cost = 0

        for i in range(len(source)):
            source_a = source[i]
            target_a = target[i]

            source_index = alphabet_lookup[source_a]
            target_index = alphabet_lookup[target_a]
            
            change_cost = alphabet_matrix[source_index][target_index]
            
            if change_cost == self.INF:
                cost = -1
                break

            cost += change_cost
        
        return cost
        
    def floyd(self, source, target, original, changed, cost):
        alphabet_original = set(original)
        alphabet_change = set(changed)
        alphabet_source = set(source)
        alphabet_target = set(target)

        alphabet = list(alphabet_original.union(alphabet_change, alphabet_source, alphabet_target))
        
        lookup = {}

        for i in range(len(alphabet)):
            lookup[alphabet[i]] = i
        


        alphabet_matrix = [[self.INF for j in range(len(alphabet))] for i in range(len(alphabet)) ]
        
        for i in range(len(alphabet)):
            alphabet_matrix[i][i] = 0

        for i in range(len(cost)):
            from_index = lookup[original[i]]
            to_index = lookup[changed[i]]
            
            alphabet_matrix[from_index][to_index] = min(cost[i], alphabet_matrix[from_index][to_index])
            # to avoid cases as: Note that there may exist indices i, j such that original[j] == original[i] and changed[j] == changed[i].
        
        for k in range(len(alphabet)):
            for i in range(len(alphabet)):
                for j in range(len(alphabet)):
                    alphabet_matrix[i][j] = min(
                        alphabet_matrix[i][j],
                        alphabet_matrix[i][k] + alphabet_matrix[k][j]
                    )


        return lookup, alphabet_matrix

  • alternatively, using dijkstra’s algorithm (since all the edges are all non-negative)

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

    class Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        def _ord(ch):
            return ord(ch)-ord('a')
          
        graph = [[] for i in range(26)]
  
        for i in range(len(original)):
            from_ch = _ord(original[i])
            to_ch = _ord(changed[i])
              
            graph[from_ch].append((to_ch, cost[i]))
  
        def dijkstra(start_ch, graph):
            distances = [-1 for i in range(26)]
            pq = [(0, start_ch)]
  
  
            # correctness -- in the first iteration, the algorithms will find the first shortest path -- the path between the start node to its nearest adjacent node
            while len(pq) > 0:
                curr_dist, curr_ch = heapq.heappop(pq)
  
                if distances[curr_ch] != -1:
                    continue # already found shortest path
                  
                distances[curr_ch] = curr_dist
                  
                for edge in graph[curr_ch]:
                    node, dist = edge
                    if distances[node] == -1: # the shortest path is not found
                        new_dist = curr_dist + dist
                        heapq.heappush(pq, (new_dist, node))
  
            return distances
  
        min_dists = [ dijkstra(ch, graph) for ch in range(26) ]
  
        total_cost = 0
  
        for i in range(len(source)):
            from_ch = _ord(source[i])
            to_ch = _ord(target[i])
              
            cost = min_dists[from_ch][to_ch]
  
            if cost == -1:
                return -1
              
            total_cost += cost
          
        return total_cost

2134. Minimum swaps to group all 1’s together II

  • use suffix sum

3243. Shortest distance after road addition queries I

  • Floyd-warshall will exceed the time limit

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

    class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
          
        INF = 10000
        distances = [[INF for i in range(n)] for j in range(n)]
          
        for i in range(n):
            distances[i][i] = 0
              
        for i in range(n-1):
            distances[i][i+1] = 1
              
        # build the initial graph
        for i in range(n):
            for j in range(i+1, n):
                distances[i][j] = j-i
          
        ans = []
  
          
        # adding routes
        for query in queries:
            u, v = query
            distances[u][v] = 1
              
            for k in [u,v]:
                for i in range(n):
                    for j in range(i+1, n):
                        dist_i_j = distances[i][j]
                        dist_i_k_j = distances[i][k] + distances[k][j]
                        distances[i][j] = min(dist_i_j, dist_i_k_j)
              
              
            #count current min distance
            ans.append(distances[0][n-1])
          
        return ans

  • Using Dijkstra with priority queue (heap queue):

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        graph = {i: [] for i in range(n)}
        for i in range(n-1):
            graph[i].append((i+1, 1))
          
        results = []
  
        def dijkstra(graph, start, end):
            distances = {node: float('infinity') for node in range(n)}
            distances[start] = 0
            priority_queue = [(0, start)]
              
            while priority_queue:
                current_distance, current_node = heapq.heappop(priority_queue)
                # the current_distance is greater than the known shortest distance between start and c_node
                if current_distance > distances[current_node]:
                    continue
                  
                for neighbor, weight in graph[current_node]:
                    distance = current_distance + weight
                    if distance < distances[neighbor]:
                        distances[neighbor] = distance
                        heapq.heappush(priority_queue, (distance, neighbor))
              
            return distances[end]
          
        for u, v in queries:
            graph[u].append((v, 1))
            shortest_path_length = dijkstra(graph, 0, n-1)
            results.append(shortest_path_length)
          
        return results

2053. Kth distinct string in an array

  • We can organize two sets, one is distinct string set and another is duplicated string set. (set is unordered)
  • To find the kth distinct string, we need to follow the order of the original array. We can iterate over the original array and check if each string is in the distinct string set, and use a counter to count the number of distinct string we’ve seen.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        dist_s = set()
        dup_s = set()

        for s in arr:
            if s in dup_s:
                continue

            if s in dist_s:
                dist_s.remove(s)
                dup_s.add(s)
            else:
                dist_s.add(s)
        
        n = 0
        for s in arr:
            if s in dist_s:
                n+=1
            
            if n==k:
                return s
        
        return ""

1460. Make two arrays equal by reversing subarrays

  • Think of swapping two adjacent elements – the same as reversing a subarray with length of 2.

  • Therefore, as long as two arrays have the amount of elements, they can be adjusted to be equal.

  • Hence, either we count the elements in two arrays, or we sort them to see if the two arrays are the same after sorting.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

    # count the elements
class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
          
        target_map = {}
        arr_map = {}
  
        for num in arr:
            if num in arr_map:
                arr_map[num] += 1
            else:
                arr_map[num] = 1
          
        for num in target:
            if num in target_map:
                target_map[num] += 1
            else:
                target_map[num] = 1
          
        for key in arr_map.keys():
            if key not in target_map.keys():
                return False
              
            if arr_map[key] != target_map[key]:
                return False
          
        return True

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

    class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
          
        if len(target) != len(arr):
            return False
  
        arr_sorted = sorted(arr)
        target_sorted = sorted(target)
  
        for i in range(len(arr_sorted)):
            if arr_sorted[i] != target_sorted[i]:
                return False
  
        return True

1508. Range sum of sorted subarray sums

  • Use two for-loops to iterate all the ranges, then, sort the array fo subarray sums, get the sum of the sorted array with given indexes.

    • this is a brute force solution with $O(n^2 \cdot \log n)$ time complexity – since the solution is sorting an array with $n^2$ elements, at best it need $O(n^2 \cdot \log n^2) = O(n^2 \cdot 2 \log n) = O(n^2 \cdot \log n)$ time.
    1
2
3
4
5
6
7
8
9
10
11
12
13

    class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        subsums = []
  
        for i in range(n):
            subsum = 0
            for j in range(i, n):
                subsum += nums[j]
                subsums.append(subsum)
          
        _sorted = sorted(subsums)
  
        return sum(_sorted[left-1: right]) % (10**9 + 7)

  • Alternatively, we can use a priority queue to maintain the order of subarray sums.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        pq = []
  
        for i in range(n):
            heapq.heappush(pq, (nums[i], i))
          
        ans = 0
        mod = 1e9+7
  
        print(pq)
  
        for i in range(1, right+1):
            p = heapq.heappop(pq)
            if i >= left:
                ans = (ans + p[0]) % mod
              
            if p[1] < n-1:
                p = (p[0] + nums[p[1]+1], p[1]+1)
                heapq.heappush(pq, p)
          
        return int(ans)

    • Java, using PriorityQueue

      1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

      class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0]-o2[0];
                }
            }
        );
    
        for (int i=0; i<n; i++) {
            pq.offer(new int[] {nums[i], i});
        } 
    
        int mod = 1000000007;
        int ans = 0;
        for(int i=1; i<right+1; i++) {
            int[] top = pq.poll();
                
            if (i >= left) {
                ans = (ans + top[0]) % mod;
            }
    
            if (top[1] < n-1) {
                pq.offer(new int[] {top[0]+ nums[top[1]+1], top[1]+1});
            }
        }
    
        return ans;
    
    }
}
      • pq.offer() – add a new element into the priority queue
      • pq.poll() – pop the top of the priority queue

3016. Minimum number to pushes to type word II

  • Count the frequency of each character in the word.
  • Sort the items in the frequency map in descending order, then get the key press times for each character by math.ceil(ch_freq/numpad_n) (prioritize high-frequency characters in the keypad, once reached the number of total available keys, characters are placed in the second, third, … place of a key – we don’t have to assign them just need to count them).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def minimumPushes(self, word: str) -> int:
        freq = {}

        for ch in word:
            if ch in freq:
                freq[ch] += 1
            else:
                freq[ch] = 1
        
        numpad_n = 8

        items = sorted(freq.items(), key=lambda item: -item[1])
        
        count = 0
        
        for i, item in enumerate(items):
            pressing = (math.ceil((i+1)/numpad_n))
            count += item[1] * pressing
            print(item, i, pressing, count)
        
        return count

2134. Minimum swaps to group all 1’s together II

  • using sliding window - window size is the total number of 1s in the array

840. Magic squares in grid

  • DON’T OVERTHINK! Here is the consequence of overthinking.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        
        count = 0

        H = len(grid)
        L = len(grid[0])
        X_MAX = L-3+1
        Y_MAX = H-3+1


        if H < 3 or L < 3:
            return count
        
        steps = X_MAX*Y_MAX
        

        x = 0
        y = 0
        occur = {}
        non_magic_count = 0
        row_sums = [0, 0, 0]
        col_sums = [0, 0, 0]
        
        left_diag = 0
        right_diag = 0
        
        for i in range(y+3):
            for j in range(x+3):
                val = grid[i][j]
                row_sums[i] += val
                col_sums[j] += val
                if val in occur:
                    occur[val] += 1
                else:
                    occur[val] = 1
                
                if i == j:
                    left_diag += val
                
                if i+j == 2:
                    right_diag += val

                if val > 9 or val < 1:
                    non_magic_count += 1

                
        if left_diag == right_diag and len(occur) == 9 and non_magic_count == 0 and len(set(row_sums)) == 1 and len(set(col_sums)) == 1:
            count += 1

        #print(left_diag, right_diag, occur)
        #print(grid[0],'\n',grid[1], '\n', grid[2])
        steps -= 1

        east=    [0, 1]     # east
        south=    [1, 0]     # south
        west=    [0, -1]    # west
        north=    [-1, 0]     # north -- not used
        
        direction = east
        x += direction[1]
        y += direction[0]

        while steps > 0:
            # remove vals out of square
            if direction == east:
                col_sums = col_sums[1:]
                col_sums.append(0)
                for i in range(3):
                    val = grid[y+i][x-1]
                    row_sums[i] -= val
                    if occur[val] == 1:
                        del occur[val]
                    else:
                        occur[val] -= 1
                    if val > 9 or val < 1:
                        non_magic_count -= 1

                    new_val = grid[y+i][x+2]
                    row_sums[i] += new_val
                    col_sums[2] += new_val
                    if new_val in occur:
                        occur[new_val] += 1
                    else:
                        occur[new_val] = 1
                    if new_val > 9 or new_val <1:
                        non_magic_count += 1
                    
            if direction == south:
                row_sums = row_sums[1:]
                row_sums.append(0)
                for i in range(3):
                    val = grid[y-1][x+i]
                    col_sums[i] -= val
                    if occur[val] == 1:
                        del occur[val]
                    else:
                        occur[val] -= 1
                    if val > 9 or val < 1:
                        non_magic_count -= 1
                    
                    new_val = grid[y+2][x+i]
                    row_sums[2] += new_val
                    col_sums[i] += new_val
                    if new_val in occur:
                        occur[new_val] += 1
                    else:
                        occur[new_val] = 1
                    if new_val > 9 or new_val <1:
                        non_magic_count += 1
            
            if direction == west:
                col_sums = col_sums[:2]
                col_sums.insert(0, 0)
                for i in range(3):
                    val = grid[y+i][x+1]
                    row_sums[i] -= val
                    if occur[val] == 1:
                        del occur[val]
                    else:
                        occur[val] -= 1
                    if val > 9 or val < 1:
                        non_magic_count -= 1

                    new_val = grid[y+i][x]
                    row_sums[i] += val
                    col_sums[0] += val
                    if new_val in occur:
                        occur[new_val] += 1
                    else:
                        occur[new_val] = 1
                    if new_val > 9 or new_val <1:
                        non_magic_count += 1
                    
            # get diags
            left_diag = 0
            right_diag = 0
            for i in range(3):
                left_diag += grid[y+i][x+i]
                right_diag += grid[y+i][2+x+y-(y+i)]
            
            if left_diag == right_diag and len(occur) == 9 and non_magic_count == 0 and len(set(row_sums)) == 1 and len(set(col_sums)) == 1 and left_diag == row_sums[0] and left_diag == col_sums[0]:
                count += 1
            
            #decide next direction
            if x == X_MAX and direction == east:
                direction = south
            if x == X_MAX and direction == south:
                direction = west
            if x == 0 and direction == west:
                direction = south
            if x == 0 and direction == south:
                direction = east

            steps -= 1
            x += direction[1]
            y += direction[0]
        
        return count

  • Simply scan each 3*3 block through the grids. Also, remember that x, y relationships in diagonal entries.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

    class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        count = 0
        X_MAX, Y_MAX = len(grid[0])-3+1, len(grid)-3+1
  
        for i in range(Y_MAX):
            for j in range(X_MAX):
                lookup = {}
                diag_left = 0
                diag_right = 0
                rowsums = [0, 0, 0]
                colsums = [0, 0, 0]
                non_magic = 0
                  
                for y in range(i, i+3):
                    for x in range(j, j+3):
                          
                        val = grid[y][x]
                        if val not in range(1, 10):
                            non_magic += 1
  
                        if val in lookup:
                            lookup[val] += 1
                        else:
                            lookup[val] = 1
  
                        if (x-j) == (y-i):
                            diag_left += val
                          
                        if (x-j)+(y-i) == 2:
                            diag_right += val
                          
                        rowsums[y-i] += val
                        colsums[x-j] += val
                          
                if len(lookup) == 9 and diag_left == diag_right and diag_left == rowsums[0] and diag_left == colsums[0] and len(set(rowsums)) == 1 and len(set(colsums)) == 1 and non_magic == 0:
                    count += 1
          
        return count

959. Regions cut by slashes

  • A novel question, need to use its geometrical properties to make the shapes.

  • An demo, it can animate the exploring steps in finding number of regions:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

    import copy
class Solution:
    def regionsBySlashes(self, grid):
        n = len(grid)
        expanded_grid = [[0 for j in range(n*3)] for i in range(n*3)]
  
        for i in range(n):
            for j in range(n):
                if grid[i][j] == '/':
                    expanded_grid[i*3][j*3+2] = 1
                    expanded_grid[i*3+1][j*3+1] = 1
                    expanded_grid[i*3+2][j*3] = 1
  
                if grid[i][j] == '\\':
                    expanded_grid[i*3][j*3] = 1
                    expanded_grid[i*3+1][j*3+1] = 1
                    expanded_grid[i*3+2][j*3+2] = 1
  
        N = len(expanded_grid)
  
  
  
        regions = 0
        steps = [{
            'grid': copy.deepcopy(expanded_grid),
            'regions': regions
        }]
  
        def explore(x, y):
            # check the boundaries
            if x in range(0, N) and y in range(0, N) and expanded_grid[x][y] == 0:
                expanded_grid[x][y] = 1
                steps.append({'grid': copy.deepcopy(expanded_grid), 'regions': regions})
  
                explore(x-1, y)
                explore(x+1, y)
                explore(x, y-1)
                explore(x, y+1)
  
  
  
        for i in range(N):
            for j in range(N):
                if expanded_grid[i][j] == 0:
                    # coloring this region until meets the boundary
                    explore(i, j)
  
                    regions += 1
  
        return regions, steps
  
import random
import math
import os
import time
  
fill = [
    '**',
    '░░',
    '▒▒',
    '▓▓',
    '██',
]
  
def print_grid(grid, regions=0):
    print('exploring region ', regions+1)
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == 0:
                print('  ', end='')
            else:
                print(fill[min(regions, len(fill)-1)], end='')
        print()
  
if __name__ == '__main__':
    candidates = [' ', '/', '\\']
    testcase = [random.sample(candidates, 2) for _ in range(2)]
    print(testcase)
    solver = Solution()
    region, steps = solver.regionsBySlashes(testcase)
    print(region)
  
    time.sleep(1)
    os.system('clear')
    print_grid(steps[0]['grid'])
  
    time.sleep(1)
    for step in steps:
        os.system('clear')
        print_grid(step['grid'], step['regions'])
        time.sleep(0.1)

40. Combination sum II

719. Find k-th smallest pair distance

1




860. Lemonade change



1140. Stone game II



    
  
  • 
    
    EACH PLAYER PLAYS OPTIMALLY – not greedy, alice would like to maximize her score, Bob will try to minimize Alice’s score
    

    
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
  
        # memo saves the states of (m, index)
        memo = [[0] * n for _ in range(n)]
  
        suffix_sums = piles[:]
  
        for i in range(n-2, -1, -1):
            suffix_sums[i] += suffix_sums[i+1]
  
        def minimax(m, index):
            if index + 2*m >= n: # player can take all remaining piles of stone, to maximize their gain
                return suffix_sums[index]
  
            if memo[m][index] > 0:
                return memo[m][index]
  
            opponent_results = float('inf')
  
            for i in range(1, 2*m+1):
                opponent_results = min(opponent_results, minimax(max(m, i), index+i))
              
            memo[m][index] = suffix_sums[index]-opponent_results
            return memo[m][index]
  
        minimax(1, 0)
          
        for row in memo:
            print(row)
  
        return memo[1][0]

        
    
  
    • 




Find the longest non-consecutive common substring



    
  
  • 
    
    using 2D DP for looking up sub problems
    

    
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    def nonconseqsubstr(s1, s2):
    m, n = len(s1), len(s2)
    dp = [["" for _ in range(n+1)] for __ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + s1[i-1]
            else:
                # choose the longer lcs for previous found
                if len(dp[i-1][j]) > len(dp[i][j-1]):
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-1]
  
    return dp[m][n], dp

        
    
  
    • 




264. Ugly number II



    
  
  • use a set to mark seen ugly numbers
    • 
  
  • use a heap queue to receive newly added ugly numbers
    • 




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        uglynumbers = [1]

        uglyset = set(uglynumbers)

        if n == 1:
            return 1
        
        counter = 0
        result = -1

        heapq.heapify(uglynumbers)

        while counter < n:
            result = heapq.heappop(uglynumbers)
            #print(result)
            counter += 1
            
            mul2 = result*2
            if mul2 not in uglyset:
                heapq.heappush(uglynumbers, mul2)
                uglyset.add(mul2)
            mul3 = result*3
            if mul3 not in uglyset:
                heapq.heappush(uglynumbers, mul3)
                uglyset.add(mul3)
            mul5 = result*5
            if mul5 not in uglyset:
                heapq.heappush(uglynumbers, mul5)
                uglyset.add(mul5)

        return result
            




f



1004. Max consecutive ones III



    
  
  • Use sliding window and effectively count number of 0s inside the window:
    • 




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left = 0
        right = 0

        penalty = 0

        # by default, not selecting any numbers in the array
        longest_ones = 0

        if nums[0] == 0:
            penalty += 1
        
        # consider the special case: nums[0] is 0 but k is also 0, therefore we won't count nums[0] into our result.
        if penalty <= k:
            longest_ones = 1

        # we dont need to count number of ones and zeroes in the window, we see all of them are 1s and count them by subtracting left and right indexes
        # if right = left+1 means we don't pick any number from the array
        while right != n-1:
            # first we need to move start index the if penalty is higher than the limit k.
            # the maximum total moves of the left point is less or equal n, so the time complexity is O(n) as we traverse the array.
            while penalty > k:
                if nums[left] == 0:
                    penalty -= 1
                left += 1
            
            right += 1

            if nums[right] == 0:   # rightend is 0
                penalty += 1
            
            if penalty <= k:
                longest_ones = max(longest_ones, right-left+1)


        return longest_ones




539. Minimum time difference



    
  
  • Add 24hr for earlier time if the time difference between two time point is larger than 720 mins (12hr)
    • 
  
  • After sorting the time points, don’t forget to compare the first and the last one (since time point is a circular data type: 23:59 -> 00:00)
    • 




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        
        times = []

        for time_point in timePoints:
            times.append( tuple(int(entry) for entry in time_point.split(":")))
        
        times.sort()

        def diff(time1, time2):
            hourdiff = time1[0] - time2[0]
            mindiff = time1[1]-time2[1]
            if abs(hourdiff*60 + mindiff) > 12*60 :
                if time1[0] < time2[0]:
                    time1 = (time1[0]+24, time1[1])
                else:
                    time2 = (time2[0]+24, time2[1])
            
            mindiff = abs((time1[0]-time2[0])*60 + (time1[1]-time2[1]))

            return mindiff
        
        min_mindiff = 24*60
        
        n = len(times)
        for i in range(1, n+1):
            min_mindiff = min(diff(times[i%n], times[i-1]), min_mindiff)

        return min_mindiff




884. Uncommon words from two sentences



    
  
  • Understand the question – uncommon word is acutally a word that only appear once from both sentences.
    • 




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        counter = defaultdict(int)

        words = s1.split(' ') + s2.split(' ')

        for word in words:
            counter[word] += 1

        uncommon_words = []

        for word in counter:
            if counter[word] == 1:
                uncommon_words.append(word)

        return uncommon_words




386. Lexicographical numbers



    
  
  • Imagine the result as a forest of trees
    
      
      
    • 1-10, 11, 12, 13, …, 19
        
        
          
      • 10-100, 101, …
        • 
        
      
      
      • 
      
    • 2, …
      • 
      
    • 3, …
      • 
      
    • …
      • 
    
    
  
    • 
  
  • Then, we can use DFS to traverse all nodes, by the limitation that numbers are in range [1, n].
    • 




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        numbers = []

        def generate_next_lexical_number(curr_number, limit, number_list):
            if curr_number > limit:
                return

            number_list.append(curr_number)
            for digit in range(10):
                next_number = curr_number*10 + digit
                
                generate_next_lexical_number(next_number, limit, number_list)
        
        for digit in range(1,10):
            generate_next_lexical_number(digit, n, numbers)

        
        return numbers




151. Reverse words in a string



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip()
        
        cur_word = []
        words = []

        for i in range(len(s)):
            ch = s[i]

            if ch == " " and len(cur_word) != 0:
                words.append(''.join(cur_word))
                cur_word = []

            if ch != " ":
                cur_word.append(ch)
        
        if len(cur_word) != 0:
            words.append(''.join(cur_word))
        

        return ' '.join(words[::-1])
# or use a stack to maintain a LIFO list




334. Increasing Triplet Subsequence



    
  
  • 
    
    Maintain two sequences, leftMins and rightMaxs, for every i - corresponding to nums[i] - we need to know the minimum value before nums[i], and maximum value after nums[i].
    

    
      
      
    • therefore, if we found that leftMins[i] < nums[i] < rightMaxs[i] when we iterate over i, an increasing triplet subsequence is found.
      • 
    
    

    
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

    class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        N = len(nums)
        if N <= 2:
            return False
  
        leftmins = [nums[0]] * N
        rightmaxs = [nums[-1]] * N
  
        for i in range(2, N):
            leftmins[i] = min(leftmins[i-1], nums[i-1])
          
        for i in range(N-1-2, -1, -1):
            rightmaxs[i] = max(rightmaxs[i+1], nums[i+1])
  
  
        for i in range(1, N-1):
            if leftmins[i] < nums[i] and nums[i] < rightmaxs[i]:
                return True
  
  
        return False

        
    
  
    • 
  
  • 
    
    The above solution is using O(N) time complexity and O(N) space complexity.
    

    
      
      
    • using its greedy nature of this question, we can reduce the space complexity to O(1), by maintaining a triplet.
      • 
    
    

    
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        N = len(nums)
  
        if N <= 2:
            return False
  
        first = nums[0]
        second = float('inf')
  
        for i in range(1, N):
            num = nums[i]
  
            if num > second:
                return True
              
            # num > first but < second, num as second
            if num > first:
                second = num
              
            # num <= first, place it as the lowest value
            else:
                first = num
  
        return False

        
    
  
    • 




1448. Count good nodes in binary tree



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        goodNodes = []
        def traverse(node, prevMax, goodNodes):
            if node is None:
                return
            
            if node.val >= prevMax:
                goodNodes.append(node.val)

            traverse(node.left, max(prevMax, node.val), goodNodes)
            traverse(node.right, max(prevMax, node.val), goodNodes)

        traverse(root, -float('inf'), goodNodes)

        return len(goodNodes)
      
 




use generator



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:

        def traverse(node, prevMax):
            if node is None:
                return
            
            if node.val >= prevMax:
                yield node.val

            yield from traverse(node.left, max(prevMax, node.val))
            yield from traverse(node.right, max(prevMax, node.val))

        

        return len(list(traverse(root, -float('inf'))))




use a counter



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def goodNodes(self, root: TreeNode) -> int:

        def traverse(node, prevMax):
            count = 0
            if node is None:
                return count
            
            if node.val >= prevMax:
                count += 1
            
            prevMax = max(prevMax, node.val)

            count += traverse(node.left, prevMax) + traverse(node.right, prevMax)
            
            return count
            
        return traverse(root, -float('inf'))




437. Path sum III



    
  
  • 
    
    brute force – O(N^2)
    

    
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

    # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def rootSum(root, targetSum):
            if root is None:
                return 0
  
            result = 0
  
            if root.val == targetSum:
                result += 1
  
            result += rootSum(root.left, targetSum-root.val)
            result += rootSum(root.right, targetSum-root.val)
  
            return result
          
        result = rootSum(root, targetSum)
  
        result += rootSum(root.left, targetSum)
        result += rootSum(root.right, targetSum)
  
        return result

        
    
  
    • 
  
  • 
    
    Hashset
    

    
    1

        
    
  
    • 




23. Merge k-sorted lists



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        N = len(lists)
        
        heap = []

        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))
        
        dummy = ListNode(0)

        current = dummy

        while heap:
            val, index, node = heapq.heappop(heap)
            current.next = ListNode(val)
            current = current.next

            if node.next:
                heapq.heappush(heap, (node.next.val, index, node.next))

        
        return dummy.next




        

        
        

            
            
Table of Content

            
            
            

  

    
Recent posts