Skip to main content

656 Coin Path

 

Solution


Approach #1 Brute Force[Time Limit Exceeded]

In this approach, we make use of a next array of size n. Here, n refers to the size of the given A array. The array nums is used such that nums[i] is used to store the minimum number of coins needed to jump till the end of the array A, starting from the index i.

We start by filling the next array with all -1's. Then, in order to fill this next array, we make use of a recursive function jump(A, B, i, next) which fills the next array starting from the index i onwards, given A as the coins array and B as the largest jump value.

With i as the current index, we can consider every possible index from i+1 to i+B as the next place to be jumped to. For every such next index, j, if this place can be jumped to, we determine the cost of reaching the end of the array starting from the index i, and with j as the next index jumped from i, as A[i] + jump(A, B, j, next). If this cost is lesser than the minimum cost required till now, for the same starting index, we can update the minimum cost and the value of next[i] as well.

For every such function call, we also need to return this minimum cost.

At the end, we traverse over the next array starting from the index 1. At every step, we add the current index to the res list to be returned and also jump/move to the index pointed by next[i], since this refers to the next index for the minimum cost. We continue in the same manner till we reach the end of the array A.

Complexity Analysis

  • Time complexity : O(B^n). The size of the recursive tree can grow upto O(b^n) in the worst case. This is because, we have B possible branches at every step. Here, B refers to the limit of the largest jump and n refers to the size of the given A array.

  • Space complexity : O(n). The depth of the recursive tree can grow upto n. next array of size n is used.


Approach #2 Using Memoization [Accepted]

Algorithm

In the recursive solution just discussed, a lot of duplicate function calls are made, since we are considering the same index through multiple paths. To remove this redundancy, we can make use of memoization.

We keep a memo array, such that memo[i] is used to store the minimum cost of jumps to reach the end of the array A. Whenever the value for any index is calculated once, it is stored in its appropriate location. Thus, next time whenever the same function call is made, we can return the result directly from this memo array, pruning the search space to a great extent.

Complexity Analysis

  • Time complexity : O(nB). memo array of size n is filled only once. We also do a traversal over the next array, which will go upto B steps. Here, n refers to the number of nodes in the given tree.

  • Space complexity : O(n). The depth of the recursive tree can grow upto n. next array of size n is used.


Approach #3 Using Dynamic Programming [Accepted]

Algorithm

From the solutions discussed above, we can observe that the cost of jumping till the end of the array A starting from the index i is only dependent on the elements following the index i and not the ones before it. This inspires us to make use of Dynamic Programming to solve the current problem.

We again make use of a next array to store the next jump locations. We also make use of a dp with the same size as that of the given A array. dp[i] is used to store the minimum cost of jumping till the end of the array A, starting from the index i. We start with the last index as the current index and proceed backwards for filling the next and dp array.

With i as the current index, we consider all the next possible positions from i+1, i+2,..., i+B, and determine the position, j, which leads to a minimum cost of reaching the end of A, which is given by A[i]+dp[j]. We update next[i] with this corresponding index. We also update dp[i] with the minimum cost, to be used by the previous indices' cost calculations.

At the end, we again jump over the indices as per the next array and put these indices in the res array to be returned.

Complexity Analysis

  • Time complexity : O(nB). We need to consider all the possible B positions for every current index considered in the A array. Here, A refers to the number of elements in A.

  • Space complexity : O(n). dp and next array of size n are used.

Comments

Popular posts from this blog

Python - Mathematical Functions - Hexadecimal, Binary, Exponential, Absolute, Round

🐍 Some mathematical functions are in-built in python. Here are some of them. Convert Decimal to Hexadecimal hex(246) Output: '0xf6' hex(512) Output: '0x200' 0x is prefix to all hexadecimal numbers in output. The number after 0x is the hexadecimal value. Convert Decimal to Binary bin(1234) Output: '0b10011010010' bin(246) Output: '0b11110110' bin(512) Output: '0b1000000000' Exponential Function pow() function is similar to num1**num2, but it comes useful when you want to execute (num1**num2)%num3. Passing three arguments to pow(), does this. pow(3,4) Output: 81 This works just like 3**4 pow(3,4,5) Output: 1 But this, works equivalent to (3**4)%5. Either of the two ways can be used. At this point I feel (3**4)%5 is better, as anybody reading the code will understand what is being done immediately. While with pow(2,3,4), the person may have to refer to documentation to understand how this function works. Absolute Value The function abs() is used ...

Two Ways of rendering in React Examples

Two Ways of rendering in React Examples 1 - Render twice HTML < div id = "p1" ></ div > < div id = "p2" ></ div > CSS . person { display : inline - block ; margin : 10px ; border : 1px solid # eee ; box - shadow : 0 2px 2px # ccc ; } JAVASCRIPT (Babel) function Person ( props ) { return ( < div className = ' person "> < h1 >{ props . name }</ h1 > < p > Age :{ props . age }</ p > </ div > ); } ReactDOM . render (< Person name = "VK" age = "29" />, document . querySselector ( '#p1' )); ReactDOM . render (< Person name = "HK" age = "28" />, document . querySselector ( '#p2' )); 2 Render all at once HTML < div id = "app" ></ div > CSS . person { display : inline - block ; margin : 1...

Binary Tree Traversal in Python - In Order, Pre Order, Post Order

Binary Tree Traversal in Python - In Order, Pre Order, Post Order Run the code here to see output:  https://repl.it/@VinitKhandelwal/iterative-traversal-of-binary-tree # Node Class to Create Object of Nodes class Node (): def __init__ ( self , value , left= None , right= None ): self .value = value self .left = left self .right = right # Creation of a Binary Tree class BinaryTree (): def __init__ ( self , mylist ): self .mylist = mylist self .root=Node ( None ) for value in self .mylist : self .curr= self .root self ._add ( value ) def _add ( self , value ): if self .curr.value == None : self .curr.value = value else : if self .curr.value > value : if self .curr.left == None : self .curr.left = Node ( value ) else : self .curr = self .curr.left self ._add ( value ) else : if self...