[LeetCode] Jump Game I && II

Jump Game I

Problem Statement (link):

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:
Starting from the first entry, for each of the reachable next entries, we find the maximum reachable position. If the max reachable position is at end of array, return true; otherwise, return false.

Code:

class Solution {
public:
    bool canJump(int A[], int n) {
        int maxReach=0;

        for (int i=0; i<=maxReach && maxReach<=n-1; i++)
            maxReach=max(maxReach, A[i]+i);

        return maxReach>=n-1;
    }
};

Jump Game II

Problem Statement (link):

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

Analysis:
We use the same methodology as that in the previous problem to find the farthest reachable position - maxReach - from index i. The idea is that we record the number of steps while we reach the farthest possible position from current index i. As long as we reach at or farther than the end of array, we found the solution.

E.g., A = [2, 3, 1, 1, 4, 1]
run 1: i = 0, found maxReach = 2 starting at index 0, number of steps = 1
run 2: i = 1, found maxReach = 4 starting at index 1, number of steps = 2
run 3: i = 4, found maxReach = 8 starting at index 4, number of steps = 3
--> found.

Again, the core of this algorithm is finding the farthest reachable position starting within the reachable range from previous index.

Code:

class Solution {
public:
    int jump(int A[], int n) {
        int maxReach=0, currFar=0, minStep=0;

        for (int i=0; i<n; ) {
            if (currFar>=n-1) break;

            while(i<=currFar) { // same as the for loop in previous problem
                maxReach=max(maxReach,A[i]+i);
                i++;
            }
            minStep++;
            currFar=maxReach;
        }
        return minStep;
    }
};

[LeetCode] Permutations I & II

Permutations I

Problem Statement (link):

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Analysis:
A picture worth a thousand words:

Fig. Algorithm demonstration (courtesy of Yu)

The algorithm is sort of like DFS. We start at the original vector, for each int at index i, we swap it with each int from index i to n, and we move to the next index i+1 recursively. If we reach the end, we push the result vector to our solution vector. Remember we need to swap back the two entries when getting back to the previous layer.

Code:

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > out;
        if (num.empty()) return out;

        perm(num, out, 0, num.size());
        return out;
    }
   
    void perm(vector<int> & num, vector<vector<int> >& out, int idx, int n) {
        if (idx==n)
            out.push_back(num);
        else {
            for (int i=idx; i<n; i++) {
                swap(num, idx, i);
                perm(num, out, idx+1, n);
                swap(num, idx, i);
            }
        }
    }

    void swap(vector<int> &num, int i, int j) {
        int tmp=num[i];
        num[i]=num[j];
        num[j]=tmp;
    }
};

Permutations II

Problem Statement (link):

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Analysis:
If contains duplicates, the problem is trickier. My initial try was identifying if two swapping ints is same, if not, we swap. But it turns out this yields duplicated result. E.g., we have input 0111, if we swap ints at index 0 and 1, we have 1011; if we swap ints at index 0 and 2, we have 1011.

The condition should be more strict. If we want to swap two ints at index i and j, the idea is to check if any int between i and j are duplicates, if yes, we shouldn't swap as we must have already swapped a same int before. Back to our 0111 example, we could swap ints at index 0 and 1, then we go to swap ints at index 0 and 2, we found two ints at index 1 and 2 are same, then we do not execute the swapping. As a matter of fact, we've already swapped int 0 with int 1 before.

Code:

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > out;
        if (num.empty()) return out;
        sort(num.begin(), num.end()); // sorting for easier identifying duplicates
        perm(num, out, 0, num.size());
        return out;
    }

    void perm(vector<int> &num, vector<vector<int> >& out, int idx, int n) {
        if (idx==n)
            out.push_back(num);
        else {
            for (int i=idx; i<n; i++) {
                if (!containDup(num, idx, i)) { // only swap if no duplicates
                    swap(num, idx, i);
                    perm(num, out, idx+1, n);
                    swap(num, idx, i);
                }
            }
        }
    }

    bool containDup(vector<int> num, int st, int ed) {
        for (int i=st; i<ed; i++)
            if (num[i]==num[ed])
                return true;
        return false;
    }

    void swap(vector<int> &num, int i, int j) {
        int tmp=num[i];
        num[i]=num[j];
        num[j]=tmp;
    }
};

[LeetCode] Gas Station

Problem Statement (link):

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Analysis:
Brute force solution is trying out every possible start index, if the cumulative gas is negative at some point, it implies the start index we chose is not a valid solution, we will then move to next index to check. This algorithm could be implemented with two for loops and yield a O(N^2) time complexity.

To figure out a more efficient solution, we need to think about the characteristics of this problem. We notice that:
- If starts at index i, the car has to stop at station j if the left gas in the tank plus gas[j] is smaller than cost[j]. The left gas is calculated by summing up gas[i : j] minus cost[i : j];
- Further, if a car stops at station j, then any station between i and j could not be a starting station. This is crucial to lower time complexity. Consider station k, where i<k<j, as the car doesn't stop until station j, then the gas-cost sum from i to k must be positive; also, as the car stop at station j, then the gas-cost sum from i to j must be negative, this implies that the gas-cost sum from k to j must be negative, thus, k could not be a starting point.

With this understood, we start at any station i, and accumulate gas-cost. Once we find the accumulation is negative at station j, we change the starting station to the next station j+1, rather than i+1 in the brute force algorithm. The new algorithm has O(N) complexity. If the accumulative sum of all gas-cost is negative, we return -1 as there is no possible solution; otherwise, we return the start station index.

Code:

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int st=0, left=0, sum=0; // left-gas left in the tank
        for (int i=0; i<gas.size(); i++) {
            left+=gas[i]-cost[i];
            sum+=gas[i]-cost[i];
            if (sum<0) {
                sum=0;
                st=i+1;
            }
        }
        return left<0 ? -1:st;
    }
};

[LeetCode] Search for a Range

Problem Statement (link):

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Analysis:
The search algorithm is same as that in the Search Insert Position problem.

- First we search if the target value exists in the array. If not, we return the [-1, -1] as required.
- Next we search for the lower and upper index bound of the given value in the array. A trick is to search for a value that is a bit smaller and a bit larger than the target value, as we are sure then the searching value doesn't exist in the array and will return us the exact index boundary of the given target value. Note that we need to -1 for the upper bound as we are not looking for the inserting position of the larger value.

The time complexity is O(log n). Precisely, we execute the binary search three times on the array.

Code:

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> index(2,-1);
        int found = recur(A, 0, n-1, n, (double)target);
        if (A[found]!=target) // if target doesn't exist in the array
            return index;

        index[0]=recur(A, 0, n-1, n, target-0.5);
        index[1]=recur(A, 0, n-1, n, target+0.5)-1; 
        return index;
    }

    int recur(int A[], int st, int ed, int n, double target) {
        if (st>ed) return st;

        int mid=(st+ed)/2;
        if (A[mid]<target)
            recur(A, mid+1, ed, n, target);
        else
            recur(A, st, mid-1, n, target);
    }
};

[LeetCode] Search Insert Position

Problem Statement (link):

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Analysis:
It's obvious we can use binary search to find the correct position. A little bit tweaking can make code much cleaner, see below.

The time complexity of this binary search is O(log n).

Code:

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        if (n==0) return 0;
        return recur(A, n, 0, n-1, target);
    }

    int recur(int A[], int n, int st, int ed, int target) {
        if (st>ed) return st; // when not found the same value in array

        int mid=(st+ed)/2;
        if (A[mid]==target) return mid;
        else if (A[mid]>target)
            recur(A, n, st, mid-1, target);
        else
            recur(A, n, mid+1, ed, target);
    }
};

[LeetCode] Clone Graph

Problem Statement (link):

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Analysis:
It's a standard graph traversal problem. Herein we use DFS to solve this problem.

We keep an unordered_map<int, Node*> visited to maintain the visited nodes - the label and the pointer to it. Note that the pointer is the pointer to nodes in the new graph.

A big difference between graph and tree is that cycles may exist. So whenever we visit a node, we add the node into the visited map. For each of its neighbors, we then check the visited map if the neighbor's label exists. Here we assume the label is unique for each node.

- If the label exists, it means we have visited this neighbor somewhere else - even if it is not currently in the neighbor's vector, we need to add the neighbor's pointer to the vector - by looking up in the visited map (Again, remember the visited map stores the label and new node's pointer).

- If the label doesn't exist, it implies that we haven't traversed the node, we then need to do a DFS recursion on that node.

Additionally, if the label/value of each node is different, we only need to change the visited map to unordered_map<Node*, Node> visited, where the two pointers are the pointer to node in the old graph and that to the corresponding node in the new graph.

Code:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
    typedef UndirectedGraphNode Node;

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node==NULL) return NULL;
        unordered_map<int, Node*> visited;
        return recur(node, visited);
    }

    Node *recur(Node *node, unordered_map<int, Node*>& visited) {
        Node *newNode=new Node(node->label);
        visited.emplace(node->label, newNode);

        for (int i=0; i<node->neighbors.size(); i++) {
            if (visited.find(node->neighbors[i]->label)==visited.end())
                newNode->neighbors.push_back(recur(node->neighbors[i], visited));
            else
                newNode->neighbors.push_back(visited[node->neighbors[i]->label]);
        }
        return newNode;
    }
};

[LeetCode] Add Binary

Problem Statement (link):

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

Analysis:
Starting from end of strings, we add corresponding two digits together. Need to consider the followings:

1) a variable to record if there's carry in each addition;
2) if there's carry when we reach the MSB of two binaries, need to append another digit 1 in front;
3) (option) we could add dummy '0's in front of the shorter string, such that the code is cleaner and easier to understand.

Code:

class Solution {
public:
    string addBinary(string a, string b) {
        string c="";
        int carry=0;
        int al=a.size(), bl=b.size();
        int cl=max(al, bl);

        for (int i=0; i<cl; i++){
            // add dummy 0s in front of shorter string
            int k1=i<al ? a[al-i-1]-'0':0;
            int k2=i<bl ? b[bl-i-1]-'0':0;
            c=to_string((k1+k2+carry)%2)+c;
            carry=(k1+k2+carry)/2;
        }

        // need to check the last carry
        return carry==1 ? "1"+c:c;
    }
};