Jump Game

                                            
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int reachable = 0;
        for (int i = 0; i < n; i++) {
            if (i > reachable) {
                return false;
            }
            reachable = max(reachable, i + nums[i]);
            if (reachable >= n - 1) {
                return true;
            }
        }
        return false;
    }
};

                                            
class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }
}

                                            
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        max_reachable = 0
        n = len(nums)
        for i in range(n):
            if i > max_reachable:
                return False
            max_reachable = max(max_reachable, i + nums[i])
            if max_reachable >= n - 1:
                return True
        return False

                                            
bool canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = fmax(maxReach, i + nums[i]);
        if (maxReach >= numsSize - 1) {
            return true;
        }
    }
    return false;
}

                                            
public class Solution {
    public bool CanJump(int[] nums) {
        int maxReach = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (i > maxReach) {
                return false;
            }
            maxReach = Math.Max(maxReach, i + nums[i]);
            if (maxReach >= nums.Length - 1) {
                return true;
            }
        }
        
        return false;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
};

                                            
function canJump(nums: number[]): boolean {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) {
            return true;
        }
    }
    return false;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canJump($nums) {
        $maxReach = 0;
        for ($i = 0; $i < count($nums); $i++) {
            if ($i > $maxReach) {
                return false;
            }
            $maxReach = max($maxReach, $i + $nums[$i]);
            if ($maxReach >= count($nums)-1) {
                return true;
            }
        }
        return false;
    }
}

                                            
class Solution {
    func canJump(_ nums: [Int]) -> Bool {
        var maxReach = 0
        for i in 0..<nums.count {
            if i > maxReach {
                return false
            }
            maxReach = max(maxReach, i + nums[i])
            if maxReach >= nums.count - 1 {
                return true
            }
        }
        return false
    }
}

                                            
class Solution {
    fun canJump(nums: IntArray): Boolean {
        var maxReach = 0
        for (i in nums.indices) {
            if (i > maxReach) return false
            maxReach = maxOf(maxReach, i + nums[i])
            if (maxReach >= nums.size - 1) return true
        }
        return false
    }
}

                                            
class Solution {
  bool canJump(List<int> nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
      if (i > maxReach) {
        return false;
      }
      maxReach = max(maxReach, i + nums[i]);
      if (maxReach >= nums.length - 1) {
        return true;
      }
    }
    return false;
  }
}

                                            
func canJump(nums []int) bool {
    maxJump := 0
    for i := 0; i < len(nums); i++ {
        if i > maxJump {
            return false
        }
        maxJump = max(maxJump, i+nums[i])
        if maxJump >= len(nums)-1 {
            return true
        }
    }
    return false
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Integer[]} nums
# @return {Boolean}
def can_jump(nums)
    max_reach = 0
    (0...nums.length).each do |i|
        return false if i > max_reach
        max_reach = [max_reach, i + nums[i]].max
    end
    return true
end

                                            
impl Solution {
    pub fn can_jump(nums: Vec<i32>) -> bool {
        let mut max_jump = 0;
        for i in 0..nums.len() {
            if i > max_jump {
                return false;
            }
            max_jump = max_jump.max(i + nums[i] as usize);
            if max_jump >= nums.len() - 1 {
                return true;
            }
        }
        false
    }
}

To solve this coding challenge, you need to determine whether it's possible to jump from the first index to the last index in an array, where each element in the array represents the maximum jump length from that position. The solution involves checking whether each position can be reached based on the maximum distance that can be jumped from previous positions.

Explanation

The main idea is to keep track of the farthest position that can be reached while iterating through the array. If, at any index, the farthest position is less than the current index, it means you cannot proceed further to reach the last index, and the answer is false. On the other hand, if you can reach or surpass the last index, the answer is true. Here's a step-by-step explanation:

Initialize a variable
max_reachable

to track the farthest index that can be reached. Set it initially to 0.
Iterate through the array using a loop. The loop variable
i

represents the current index.
For each index
i

, check if the current index is greater than
max_reachable

. If it is, return
false

immediately because this means you cannot reach this index.
Update the
max_reachable

value to the maximum of its current value and
i + nums[i]

(the current index plus the jump length at this index).
If at any point,
max_reachable

is greater than or equal to the last index, return
true

as you can successfully jump to or past the last index.
If the loop completes, return
false

as none of the previous jumps were sufficient to reach the last index.

Detailed Steps in Pseudocode

                                            
# Define a function that takes in an array of integers named nums
function canReachLastIndex(nums):

# Initialize the maximum reachable index at the beginning as 0
max_reachable = 0

# Get the length of the nums array
length = length of nums

# Loop through each index in the nums array
for i from 0 to length - 1:

# If current index is greater than the maximum reachable index
if i > max_reachable:
# You can't reach this index, return false
return false

# Update max_reachable to be the farthest point you can reach from here
max_reachable = maximum of (max_reachable, i + nums[i])

# If max_reachable is beyond or at the last index
if max_reachable >= length - 1:
# You can reach the last index, return true
return true

# If you complete the loop and haven't reached the end, return false
return false

To help reinforce the logic applied:

Initialization :

max_reachable

is set to 0, which means initially only the first index is reachable.
The length of the array (
length

) is stored for easier access.

Loop Through Elements :

The loop runs from the start of the array to the second-to-last index because we're considering jumps from each position.

Check Unreachable Index :

If at any position
i

,
i

is greater than
max_reachable

, it indicates that the position
i

is not reachable from any of the previous indices, hence return
false

.

Update Maximum Reachable Index :

At each index,
max_reachable

is updated to the maximum of its current value and the distance you can reach from the current index (
i + nums[i]

).

Check for Last Index Reachability :

If
max_reachable

reaches or exceeds the last index (
length - 1

), return
true

, indicating that it's possible to reach the last index.

Return Final Verdict :

If the loop completes and no early return was triggered, it means you were unable to reach the last index from any of the jumps, hence return
false

.

This pseudocode should guide you to understanding the logic necessary to solve the Jump Game coding challenge effectively. The key takeaway is keeping track of the farthest point you can reach and using that to determine whether you can reach the end.