Day 58, #42, #43, #55, Trapping Rain Water, Multiply Strings, Jump Game II

Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

-----------------------------------------------------------------------------------
O(n) solution. for each bar, find the max height bar on the left and right. then for this bar it can hold min(max_left, max_right) - height

class Solution {
public:
    int trap(int A[], int n) {
        vector<int> leftMax(n,0);
        vector<int> rightMax(n,0);
        
        // get left max for each element
        for (int i = 1; i < n; i++) {
            leftMax[i] = max(leftMax[i - 1],A[i - 1]);
        }
        
        // get right max for each element
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = max(rightMax[i + 1], A[i + 1]);
        }
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int water = min(leftMax[i],rightMax[i]) - A[i]; 
            if (water > 0) {
                sum += water; 
            }
        }
        return sum;
    }
};

Update on Nov-6th-2014
come back
Solution #2, if leftMax < rightMax, leftIndex can contain (leftMax - A[leftIndex]) water, regardless what it looks like between leftIndex and rightIndex

class Solution {
public:
    int trap(int A[], int n) {
        int sum = 0;
        int leftMax = 0, rightMax = 0;
        int leftIndex = 0, rightIndex = n - 1;
        
        while (leftIndex <= rightIndex) {
            leftMax = max(leftMax,A[leftIndex]);
            rightMax = max(rightMax,A[rightIndex]);
            if (leftMax < rightMax) {
                sum += leftMax - A[leftIndex];
                leftIndex++;
            }else {
                sum += rightMax - A[rightIndex];
                rightIndex--;
            }
        }
        
        return sum;
    }
};

Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
--------------------------------------
Multiply numbers using straightforward math

class Solution {
public:
    string multiply(string num1, string num2) {
        int len1 = num1.length(), len2 = num2.length();
        string sum(len1 + len2,'0');
      
        for (int i = len1 - 1; i >= 0; i--) {
            int carry = 0;
            for (int j = len2 - 1; j >= 0; j--) {
                int cur = (sum[i + j + 1] - '0') + carry + (num1[i] - '0') * (num2[j] - '0');
                sum[i + j + 1] = cur % 10 + '0';
                carry = cur / 10;
            }
            sum[i] += carry;   
        }
        
        int start = 0;
        while (sum[start] == '0') {
            start++;
        }
        if (start == sum.length()) return "0";
        return sum.substr(start);
    }
};

Jump Game II
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.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
---------------------------------------------------------------------------
Greedy, the point of this question is to find the largest distance with minimum steps
Every time 'i' passes curMax, increment step

class Solution {
public:
    int jump(int A[], int n) {
        int curMax = 0, newMax = 0;
        int step = 0;
        for (int i = 0; i < n; i++) {
            if (i > curMax) {
                // set up new max from old steps
                curMax = newMax;
                step++;
            }
            newMax = max(newMax,i + A[i]); // this line should be placed after if condition, 'cause new step has been made
        }
        return step;
    }
};

Update on Nov-7th-2014
a slightly different version, handles the case where the goal cannot be reached

class Solution {
public:
    int jump(int A[], int n) {
        if (n == 1) return 0;
        int step = 1;
        int currentReach = A[0];
        int maxCanReach = A[0];
        
        for (int i = 1; i < n; i++) {
            if (i > currentReach) {
                // to handle cases where the end cannot be reached
                if (currentReach == maxCanReach) {
                    return -1;
                }
                step++;
                currentReach = maxCanReach;
            }
            maxCanReach = max(maxCanReach,i + A[i]);
        }
        
        return step;
    }
};