Jump Game

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 true.

A = [3,2,1,0,4], return false.

[Analysis]

At first it seems like a straightforward DP problem and I did just that and failed at the last test cases which contains 25k elements… Lessons learned, there must be some observations to be made in order to optimize the solution. Let’s optimize it!

Note my DP array canJump. In fact, we know there are maximum n steps that we can make on each given position i, therefore the n steps following the positions i are all possible destinations. That is, note how our DP array is set block by block, this means that if we have canJump[i] = true, not only position i is a possible destination, but every elements before it must also be possible destinations. There is thus no need to set them to true again.

Therefore, at each position, we retain previously farthest position such that canJump[farthest] = true, we check if i+A[i] would bring us even farther, if yes, we start at farthest and update our farthest position. The complexity is thus brought to O(n) instead of , because we only set each elements to true once, so in total we are still in O(n).

    bool canJump(int A[], int n) {
        if (n == 0)
            return false;
            
        bool canJump[n];
        
        for (int i=0; i<n; ++i){
            canJump[i] = false;
        }
        
        canJump[0] = true;
        int farthest = 0;
        
        
        for (int i=0; i<n; ++i) {
            if (canJump[i]) {
                if (i+A[i] > farthest) {
                    for (int j=farthest; j<n-1 && j<=i+A[i]; ++j) {
                        canJump[j] = true;
                    }
                    farthest = min(n-1, i+A[i]);
                    if (farthest == n-1)
                        return true;
                } 
            }
        }
        
        return canJump[n-1];
    }

Update:
Turns out there is even no need for the DP part, since we know everything before farthest is attainable, why not just check if i<=farthest? This runs in 20ms instead of 70ms. Not so bad 😛

    bool canJump(int A[], int n) {
        if (n == 0)
            return false;
        if (n == 1)
            return true;

        int farthest = 0;

        for (int i=0; i<n; ++i) {
            if (i <= farthest) {
                if (i+A[i] > farthest) {
                    farthest = min(n-1, i+A[i]);
                    if (farthest == n-1)
                        return true;
                }
            }
        }

        return false;
    }

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]

]

[Analysis]

Know your DFS!

Don’t forget to pop!

If you do pop, make sure we are always pushing one element on each recursion!

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<vector > res;
    vector r;

    void pathSumHelper(TreeNode *node, int target) {
        if (!node->left && !node->right && target == node->val) {
            // node is a leaf and it's a solution
            r.push_back(node->val);
            res.push_back(r);
            return;
        }

        // internal node, also makes sure that we always push a node
        r.push_back(node->val);
        int current = target - node->val;

        if (node->right) {
            pathSumHelper(node->right, current);
            r.pop_back();
        }
        if (node->left) {
            pathSumHelper(node->left, current);
            r.pop_back();
        }
    }

public:
    vector<vector > pathSum(TreeNode *root, int sum) {
        res.clear();
        r.clear();

        if (!root)
            return res;

        pathSumHelper(root, sum);

        return res;
    }
};


		
	
			

			
								

Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

[Analysis]

To solve this problem in O(n) there are several observations to be made.

1. when we scan through the ratings, there is constraint on the number of candies of i and i-1 when we are in a ascending position (ratings[i-1] < ratings[i]) but there is no constraints if we are not in such a position.
2. starting with 1 candy for each child, we should only increase the number of candies to be distributed, but never reduce it, otherwise, we would break some constraints previously calculated

The following solution is inspired by this post, with more detailed comments.

class Solution {
public:
    int candy(vector<int> &ratings) {
        vector<int> candies(ratings.size(), 1);
        
        // scanning through the ratings from left to right while 
        // maintaining the rules for all rising positions
        for (int i=1; i<ratings.size(); ++i) {
            if (ratings[i] > ratings[i-1])
                candies[i] = candies[i-1]+1;
        }
        
        int sum = 0;
        // scanning through the ratings from right to left while 
        // maintaining the rules for all rising positions 
        // (descending positions in the first loop)
        for (int i=ratings.size()-2; i>=0; --i) {
            // we only want to increase numbers, not reduce them. 
            // !(candies[i] >= candies[i+1]+1) gurantees that we will only increase it
            // if we increase a number from right to left, we will never break the right policy
            // previously assured left policy will be maintained if we only increase a number
            if (ratings[i] > ratings[i+1] && !(candies[i] >= candies[i+1]+1))
                candies[i] = candies[i+1]+1;
            sum += candies[i+1];
        }
        sum += candies[0];
        
        return sum;
    }
};