Jump Game in c#

Programming C#
1

The Jump Game problem is a classic algorithmic challenge where you determine if you can reach the last index of an array starting from the first index. Each element in the array represents the maximum jump length you can take from that position.

Problem Statement

Given an array of non-negative integers, where each integer represents the maximum jump length at that position, return true if you can reach the last index, and false otherwise.

C# Implementation

Here’s a C# implementation using a greedy approach:

public class Solution {
    public bool CanJump(int[] nums) {
        int maxReach = 0;
        int n = nums.Length;

        for (int i = 0; i < n; i++) {
            // If the current index is greater than the maximum reachable index,
            // we cannot move further, hence return false.
            if (i > maxReach) {
                return false;
            }
            // Update the maximum reachable index
            maxReach = Math.Max(maxReach, i + nums[i]);

            // If we can reach the last index, return true
            if (maxReach >= n - 1) {
                return true;
            }
        }

        return false;
    }
}

Explanation

  1. Initialization:

    • We start by initializing a variable maxReach, which keeps track of the farthest index we can reach at any point in the array.

  2. Iterating Through the Array:

    • We loop through each index i in the array:
      • If i exceeds maxReach, it means we cannot reach this index from any previous index, so we return false.
      • We update maxReach by comparing its current value with i + nums[i], which represents how far we can reach from the current index.
      • If at any point maxReach is greater than or equal to the last index (n - 1), we return true, indicating we can reach the end.

  3. Return Value:

    • If we finish the loop without returning, it means we cannot reach the last index, and we return false.

Example Walkthrough

Consider the array [2, 3, 1, 1, 4].

  • Initialization:

    • maxReach = 0, n = 5.

  • Iteration:

    • For i = 0: maxReach = max(0, 0 + 2) = 2.
    • For i = 1: maxReach = max(2, 1 + 3) = 4.
    • For i = 2: maxReach = max(4, 2 + 1) = 4.
    • For i = 3: maxReach = max(4, 3 + 1) = 4.
    • For i = 4: Since maxReach is already 4, which is greater than 4, we don’t check further.

Since maxReach reaches the last index, the function returns true.

Complexity

  • Time Complexity: O(n), where n is the number of elements in the array, as we traverse the array once.
  • Space Complexity: O(1), as we only use a constant amount of space for variables.

This greedy approach is efficient and straightforward for solving the Jump Game problem!