Posts

Depth-First Search (DFS)

-
Image
Although it is an easy problem and likely there is a clever way to solve it using just mathematical tricks, I decided to do a full implementation of Depth-First Search (DFS). Notice that the "visited" requires you to also use the cardinality of the number of steps taken. Code is down below, cheers, ACC. Even Number of Knight Moves - LeetCode You are given two integer arrays start and target , where each array is of the form [x, y] representing a cell on a standard 8 x 8 chessboard. Return true if a knight can move from start to target in an even number of moves. Otherwise, return false . Note: A valid knight move consists of moving two squares in one direction and one square perpendicular to it. The figure below illustrates all eight possible moves from a cell.   Example 1: Input: start = [1,1], target = [2,2] Output: true Explanation: One possible sequence of moves is (1, 1) -> (3, 2) -> (2, 4) -> (4, 3) -> (2, 2) . The knight reaches the target in 4 mov...
Post a Comment
Read more

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