Posts

Post-Order

-
Image
Post-Order traversals were, to me, the most unintuitive types of traversals because you are performing the induction before the base case, but once you grasp the idea it is very powerful, this problem exemplifies it clearly. Code is down below, cheers, ACC. Count Dominant Nodes in a Binary Tree - LeetCode You are given the root of a complete binary tree . A node x is called dominant if its value is equal to the maximum value among all nodes in the subtree rooted at x . Return the number of dominant nodes in the tree.   Example 1: Input: root = [5,3,8,2,4,7,1] Output: 5 Explanation: The leaf nodes with values 2, 4, 7, and 1 are dominant. The node with value 8 is dominant because its value is the maximum value in its subtree [8, 7, 1] . Thus, the answer is 5. Example 2: Input: root = [1,2,3,1,2] Output: 4 Explanation: The leaf nodes with values 1, 2, and 3 are dominant. The node with value 2 whose subtree is [2, 1, 2] is dominant because its value is the maximum value in its...
Post a Comment
Read more

Cache for a linear solution

-
We don't want to do an N^2 solution here since N=10^5. Since the numbers are all positive, cache the max number from nums.Length-1..j, and use this cached value for a linear computation of the solution. Code is down below, cheers, ACC. Maximum Valid Pair Sum - LeetCode You are given an integer array nums of length n and an integer k . A pair of indices (i, j) is called valid if: 0 <= i < j < n j - i >= k Return the maximum value of nums[i] + nums[j] among all valid pairs.   Example 1: Input: nums = [1,3,5,2,8], k = 2 Output: 13 Explanation: The valid pairs are: (0, 2) : nums[0] + nums[2] = 6 (0, 3) : nums[0] + nums[3] = 3 (0, 4) : nums[0] + nums[4] = 9 (1, 3) : nums[1] + nums[3] = 5 (1, 4) : nums[1] + nums[4] = 11 (2, 4) : nums[2] + nums[4] = 13 Thus, the answer is 13.​​​​​​​ Example 2: Input: nums = [5,1,9], k = 1 Output: 14 Explanation: Since k = 1 , every pair is valid. The maximum value is obtained from a pair (0, 2) ​​​​​​​, which is nums[0] + nums[2] = 5...
Post a Comment
Read more

Connected Components in a Graph II

-
Image
In reality this question is just looking for the following: find the connected components to vertex 1, and select the minimum edge. That's it. The problem statement guarantees that there will be at least one connection between 1 and N. That way, just traverse the graph looking for the smallest edge, starting from 1. Code is down below, cheers, ACC. Minimum Score of a Path Between Two Cities - LeetCode You are given a positive integer n representing n cities numbered from 1 to n . You are also given a 2D array roads where roads[i] = [a i , b i , distance i ] indicates that there is a bidirectional road between cities a i and b i with a distance equal to distance i . The cities graph is not necessarily connected. The score of a path between two cities is defined as the minimum distance of a road in this path. Return the minimum possible score of a path between cities 1 and n . Note : A path is a sequence of roads between two cities. It is allowed for a path to contain the s...
Post a Comment
Read more