Search This Blog

Sunday, October 16, 2016

Jump Game Array Interviewbit

Problem:
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return 1 ( true ).
A = [3,2,1,0,4], return 0 ( false ).




Solution:

int canJump(int* A, int n1) {
    int i, j;
    /* Create a hash map equal to size of array */
    int visited[n1];
    /* Mark all positions as non-visited */
    for (i = 0; i < n1; i++) {
        visited[i] = 0;
    }
    /* Mark first position as visited */
    visited[0] = 1;
    /* Idea here is to visit all the indexes which can be jumped from
        an index */
    for (i = 0; i < n1; i++) {
        /* If we reach at any non-visited index then all other indexes to its right 
           will be non-visited */
        if (visited[i] == 0) {
            break;
        }
        /* Mark all the indexes which can be reached as visited */
        for (j = 1; j <= A[i]; j++) {
            /* No need to visit index beyond the last index */
            if (i+j >= n1) {
                break;
            }
            visited[i+j] = 1;
        }
        /* If we have already visited the last index then no need to move further */
        if (visited[n1-1] == 1) {
            break;
        }
    }
    return visited[n1-1];
}

int main()
{
    int A[] = { 2, 3, 1, 1, 4 };
    int n1 = sizeof(A)/sizeof(A[0]);
    printf("%s jump to last index\n", canJump(A, n1) ? "Can" : "Can't");
    return 0;
}

Let me know your feedbacks in comments.