Folks, any ideas on how to approach the following questions:
Q1. Given coins and minCoins both of size n < 10^5 and k < 10^5. coins[i] represents the cost of crossing the i-th toll and is subtracted from the number of coins you have after crossing the toll. If after crossing the i-th toll, you have atleast minCoins[i] remaining you get a star. Return an array of size n where arr[i] represents the number of stars which can be collected if you start to cross tolls from the i-th toll with k initial coins. Note that it is possible to have enough coins to continue even with remaining coins < minCoins[i] at a particular toll i. Ex: coins = [5, 7, 2, 1], minCoins = [4, 3, 2, 2], k = 10, ans = [1, 1, 2, 1]
I think a sliding window/two pointers on the coins array might work here but not 100% sure.
Q2. Given n < 10^5 numbers and k < 10^9, can the numbers be sorted just by swapping two number a[i], a[j] such that abs(a[i]-a[j]) <= k any number of times? Return boolean true/false. Ex: arr = [6, 5, 1, 2], k = 2, ans = false, arr = [2, 1, 6, 5], k = 2, ans = true For this problem, I think a set needs to be created starting from index i till the rightmost j possible. Then the set needs to be sorted in place. This process can be repeated till the end of the array and then it can be checked if the array is sorted. The set can be created by binary searching arr[i]-k or arr[i]+k in the existing set to see if arr[i] can be inserted into the set. If not, then this is the end of the current set.
Is there a better way to do this?
Q3. Given a graph with n < 10^5 nodes and m < 2*10^5 edges. Both nodes and edges have values. The pleasant value of a path in graph is the sum of node values minus the sum of edge values on that path. Return the maximum pleasant value of a path of length 4 starting from any node. All nodes and edges visited in a path must be unique. Ex: G = [[1, 2], [2, 3], [3, 4], [4, 5]], has paths 1-2-3-4 and 2-3-4-5
Any ideas for this?
For the first question, a hint:
Let's say you want to obtain a star from index $$$i$$$. Where can you start from in order to obtain that star?
For the second question (full solution):
Think about sorting the values. Now think about making a graph on these values in the following way: there is an edge between $$$i$$$ and $$$i+1$$$ if the condition you mentioned is satisfied. Now let's look at each of the original array. The array can be sorted iff $$$\forall i, arr_i$$$ is connected with $$$sorted_i$$$.
Third question (hint):
Think about a solution from the middle edge's perspective.