55. Jump Game - Medium

 You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index or false otherwise.

Example:
Input: nums = [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]

Output: false

Explanation: You will always arrive at index 3 no matter wht. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

1 <= nums.length <= 10**4

0 <= nums[i] <= 10**5

Solution:

var canJump = function(nums) {

    let goal = nums.length - 1;

    for (let i = nums.length - 2; i >= 0; i--) {

        if (i + nums[i] >= goal) {

            goal = i;

        }

    return goal === 0;

}


Thoughts:
Too difficult this problem. I would have never thought to start at the end and move the goal and see if it could reach the first index. If it can then return true else false. It's one of those difficult problems where you need to know the technique in order to solve it. I tried to think of a solution and didn't have a clue within 15 minutes, I looked for the solution. I kind of understand what's going on but would never have come up with it on my own. Wish the problem had hints. I'd give my confidence rating a 2/10. I'm not sure if I should skip these mediums and go back to easy ones.

Comments

Post a Comment

Popular posts from this blog

28. Find the Index of the First Occurence in a String - Easy

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if the needle is not part of haystack. Example: Input: haystack = 'sadbutsad', needle = 'sad' Output: 0 Explanation: 'sad' occurs at index 0 and 6. The first occurrence is at index 0, so we return 0. Constraints: 1 <= haystack.length, needle.length <= 10**4 haystack and needle consist of only lowercase English characters. Solution: var strStr = function(haystack, needle) {          return haystack.indexOf(needle); } Thoughts: 10/10 easy.
Read more

121. Best Time to Buy and Sell Stock - Easy

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximise your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0 Example: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Constraints: 1 <= prices.length <= 10**5 0 <= prices[i] <= 10**4 Solution: var maxProfit = function(prices) {     let buyPrice = prices[0];     let profit = 0;     for (let i = 1; i < prices.length; i++) {          if (buyPrice > prices[i]) {               buyPrice = prices[i];         ...
Read more

58. Length of Last Word - Easy

Given a string s consisting of words and spaces, return the length of the last word in the string. A word is. a maximal substring consisting of non-space characters only. Example: Input: s = "Hello World" Output: 5 Explanation: The last word is "World" with length 5. Constraints: 1 <= s.length <= 10**4 s consists of only English letters and spaces ' '. There will be at least one word in s. Solution: var lenghtOfLastWord = function(s) {       return s.trim().split(' ').pop().length; } Thoughts: Super simple. 10/10 for confidence and understanding.
Read more