Posts

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