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

Thoughts:
This is not a hard question in the sense that there’s no “clever” algorithm to apply. We just do the intuitive way. Think about how we human being multiply two integers. We take each digit and multiply it with another digit, then the addition, taking care of the carry. So we just “mimic” that method in our code. The only catch is that we have to be busy travelling between integer and char. Another catch is how much space we should initialize our result string. Well, in my solution, I try to be conservative to find the upper bound – the number of digits of the products can be no more than the sum of the digits of the two multipliers. In the end, we might find we allocated more space than we need to, resulting some leading zeros. We can just clean it up.

Code (Java):

public class Solution {
    public String multiply(String num1, String num2) {
        char[] result = new char[num1.length() + num2.length()];
        for(int i = 0; i < result.length; ++i)
            result[i] = '0';
        for(int i = num1.length() - 1; i >= 0; --i) {
            int index = num1.length() + num2.length() - 1 - (num1.length() - 1 - i);
            int digit1 = Character.getNumericValue(num1.charAt(i));
            for(int j = num2.length() - 1; j >= 0; --j) {
                int digit2 = Character.getNumericValue(num2.charAt(j));
                int temp = digit1 * digit2;
                int previous = Character.getNumericValue(result[index]);
                result[index] = (char) ((previous + temp) % 10 + '0');
                int carry = (previous + temp) / 10;
                int m = index - 1;                
                while(carry != 0 && m >= 0) {
                    int rm = Character.getNumericValue(result[m]);
                    result[m] = (char)((rm + carry) % 10 + '0');
                    carry = (rm + carry) / 10;
                    m--;
                }
                
                index--;
            }
        }
        return new String(result).replaceFirst("^0+(?!$)", "");
    }
}

Code (C++):

class Solution {
public:
    string multiply(string num1, string num2) {
        char result[num1.size() + num2.size()];
        for(int i = 0; i < num1.size() + num2.size(); ++i)
            result[i] = '0';
        for(int i = num1.size() - 1; i >= 0; --i) {
            int index = num1.size() + num2.size() - 1 - (num1.size() - 1 - i);
            int digit1 = num1[i] - '0';
            for(int j = num2.size() - 1; j >= 0; --j) {
                int digit2 = num2[j] - '0';
                int temp = digit1 * digit2;
                int previous = result[index] - '0';
                result[index] = (char) ((previous + temp) % 10 + '0');
                int carry = (previous + temp) / 10;
                int m = index - 1;                
                while(carry != 0 && m >= 0) {
                    int rm = result[m] - '0';
                    result[m] = (char)((rm + carry) % 10 + '0');
                    carry = (rm + carry) / 10;
                    m--;
                }
                
                index--;
            }
        }
        string candidate = string(result, num1.size() + num2.size());
        size_t i = candidate.find_first_not_of('0');
        return i ==  string::npos ? "0" : candidate.substr(i);
    }
};

(Minimum Window Substring)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Thoughts:
The idea is from here. I try to rephrase it a little bit here. The general idea is that we find a window first, not necessarily the minimum, but it’s the first one we could find, traveling from the beginning of S. We could easily do this by keeping a count of the target characters we have found. After finding an candidate solution, we try to optimize it. We do this by going forward in S and trying to see if we could replace the first character of our candidate. If we find one, we then find a new candidate and we update our knowledge about the minimum. We keep doing this until we reach the end of S. For the giving example:

  1. We start with our very first window: “ADOBEC”, windowSize = 6. We now have “A”:1, “B”:1, “C”:1
  2. We skip the following character “ODE” since none of them is in our target T. We then see another “B” so we update “B”:2. Our candidate solution starts with an “A” so getting another “B” cannot make us a “trade”.
  3. We then see another “A” so we update “A”:2. Now we have two “A”s and we know we only need 1. If we keep the new position of this “A” and disregard the old one, we could move forward of our starting position of window. We move from A->D->O->B. Can we keep moving? Yes, since we know we have 2 “B”s so we can also disregard this one. So keep moving until we hit “C”: we only have 1 “C” so we have to stop. Therefore, we have a new candidate solution, “CODEBA”. Our new map is updated to “A”:1, “B”:1, “C”:1.
  4. We skip the next “N” and we arrive at “C”. Now we have two “C”s so we can move forward the starting position of last candidate: we move along this path C->O->D->E until we hit “B”. We only have one “B” so we have to stop. We have yet another new candidate, “BANC”.
  5. We have hit the end of S so we just output our best candidate, which is “BANC”.

Code (Java):

public class Solution {
    public String minWindow(String S, String T) {
        int[] needToFind = new int[256];
        int[] hasFound = new int[256];
        
        for(int i = 0; i < T.length(); ++i) {
            needToFind[T.charAt(i)]++;
        }
        
        int count = 0;
        int minWindowSize = Integer.MAX_VALUE;
        int start = 0, end = 0;
        String window = "";
        
        for(; end < S.length(); end++) {
            if(needToFind[S.charAt(end)] == 0) continue;
            char c = S.charAt(end);
            hasFound[c]++;
            
            if(hasFound[c] <= needToFind[c]) {
                count++;
            }
            
            if(count == T.length()) {
                while(needToFind[S.charAt(start)] == 0 ||
                    hasFound[S.charAt(start)] > needToFind[S.charAt(start)]) {
                    if(hasFound[S.charAt(start)] > needToFind[S.charAt(start)])
                        hasFound[S.charAt(start)]--;
                    start++;
                }
                
                if(end - start + 1 < minWindowSize) {
                    minWindowSize = end - start + 1;
                    window = S.substring(start, end + 1);
                }
            }
        }
        
        return window;
    }
}

Code (C++):

class Solution {
public:
    string minWindow(string S, string T) {
        int needToFind[256] = {0};
        int hasFound[256] = {0};
        
        for(int i = 0; i < T.size(); ++i) {
            needToFind[T[i]]++;
        }
        
        int count = 0;
        int minWindowSize = INT_MAX;
        int start = 0, end = 0;
        string window;
        
        for(; end < S.size(); end++) {
            if(needToFind[S[end]] == 0) continue;
            hasFound[S[end]]++;
            
            if(hasFound[S[end]] <= needToFind[S[end]]) {
                count++;
            }
            
            if(count == T.size()) {
                while(needToFind[S[start]] == 0 ||
                    hasFound[S[start]] > needToFind[S[start]]) {
                    if(hasFound[S[start]] > needToFind[S[start]])
                        hasFound[S[start]]--;
                    start++;
                }
                
                if(end - start + 1 < minWindowSize) {
                    minWindowSize = end - start + 1;
                    window = S.substr(start, minWindowSize);
                }
            }
        }
        
        return window;
    }
};

(Minimum Path Sum)

Given a m \times n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

Thoughts:
Because the grid is filled with non-negative numbers. Standing at any position (i, j), the minimum sum we can get is \text{grid}[i,j] + \min(minimum sum starting from[i+1,j], minimum sum starting from [i,j+1]). Hence we find the recursive structure of this problem. The base case would be one element only, one row only and one column only. Notice that we could end up with repeating computations a lot (e.g., right->down and down->right), hence we should employ dynamic programming, in which we introduce a hashmap to cache the partial result.

Code (Java):

public class Solution {
    
    private Map<List<Integer>, Integer> map = 
            new HashMap<List<Integer>, Integer>();
    
    public int minPathSum(int[][] grid) {
        map.clear();
        return minPathSumRec(grid, 0, 0);
    }
    
    private int minPathSumRec(int[][] grid, int i, int j) {
        List<Integer> pair = new ArrayList<Integer>();
        pair.add(i);
        pair.add(j);
        if(map.get(pair) != null)
           return map.get(pair);
        else {
            int r = grid[i][j];;
            if(i == grid.length-1 && j == grid[0].length - 1)
                r += 0; 
            else if(i == grid.length - 1)
                r += minPathSumRec(grid, i, j + 1);
            else if(j == grid[0].length - 1)
                r += minPathSumRec(grid, i + 1, j);
            else
                r += Math.min(minPathSumRec(grid, i + 1, j), 
                        minPathSumRec(grid, i, j + 1));
            map.put(pair, r);
            return r;
        }
    }
}

Code (C++):

class Solution {
public:
    int minPathSum(vector<vector<int> > &grid) {
        cache.clear();
        return minPathSumRec(grid, 0, 0);
    }
    
private:
    map<vector<int>, int> cache;

    int minPathSumRec(vector<vector<int> > &grid, int i, int j) {
        vector<int> pair(2);
        pair[0] = i;
        pair[1] = j;
        if(cache.find(pair) != cache.end())
            return cache[pair];
        else {
            int r = grid[i][j];
            if(i == grid.size() -1 && j == grid[0].size() - 1)
                r += 0;
            else if(i == grid.size() - 1)
                r += minPathSumRec(grid, i, j + 1);
            else if(j == grid[0].size() - 1)
                r += minPathSumRec(grid, i + 1, j);
            else
                r += min(minPathSumRec(grid, i, j + 1), 
                        minPathSumRec(grid, i + 1, j));
            cache[pair] = r;
            return r;
        }
    }
};

(Merge Intervals)

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Thoughts:
We first sort the list according to the start-time. Then for any interval i in the middle, it has overlap with the next interval j iff j.start <= i.end. If so, we know we are about to merge them into a new interval k. And k.start = i.start && k.end = \max(i.end, j.end).

Code (Java):

public class Solution {
    public class MyComparator implements Comparator{
        public int compare(Object o1, Object o2) {
            Interval i1 = (Interval)o1;
            Interval i2 = (Interval)o2;
            return i1.start - i2.start;
        }
    }
    
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals == null)
            return null;
        ArrayList<Interval> result = new ArrayList<Interval>();
        if(intervals.size() == 0)
            return result;
        if(intervals.size() == 1) {
            result.addAll(intervals);
            return result;
        }
        Collections.sort(intervals, new MyComparator());
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(int i = 1; i < intervals.size(); ++i) {
            Interval curr = intervals.get(i);
            if(curr.start <= end) {
                end = Math.max(end, curr.end);
            } else {
                result.add(new Interval(start, end));
                start = curr.start;
                end = curr.end;
            }
        }
        result.add(new Interval(start, end));
        return result;
    }
}

Code (C++):
Thanks to this post:

class Solution {
class Solution {
public:
    struct MyComparatorClass {
        bool operator() (Interval i, Interval j) { return (i.start < j.start);}
    } myComparator;

    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> result;
        if(intervals.size() == 0)
            return result;
        if(intervals.size() == 1) {
            result.push_back(intervals[0]);
            return result;
        }
        sort(intervals.begin(), intervals.end(), myComparator);
        vector<Interval>::iterator it = intervals.begin();
        Interval current = *(it)++;
        while (it != intervals.end()){
            if (current.end >= it -> start) {
                current.end = std::max(current.end, it -> end); 
            } else {
                result.push_back(current);
                current = *(it);
            }
            it++;
        }
        result.push_back(current);
        return result;
    }
};

(Search in Rotated Sorted Array)

Suppose a sorted array is rotated at some pivot unknown to you beforehand (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

Thoughts:
This is a modified version of binary search. Each time we half the array, and determine which part is sorted (there must be at least one of them). We then check if the target falls in the sorted part, we then apply the original version of binary search to it. Otherwise we recursively or iteratively go to the other half.

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        int low = 0;
        int high = A.length - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(target == A[mid])
                return mid;
            if(A[low] <= A[mid]) { // left part sorted
                if(A[low] <= target && target < A[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else { // right part sorted
                if(A[mid] < target && target <= A[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
}

Code (C++):

class Solution {
public:
    int search(int A[], int n, int target) {
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(A[mid] == target)
                return mid;
            if(A[low] <= A[mid]) { // left part sorted
                if(A[low] <= target && target < A[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                if(A[mid] < target && target <= A[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
};

(Remove Duplicates from Sorted Array)

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

Thoughts:
This question is actually simpler than what it looks. We just need one scan with two pointers. The first pointer points to the last index of subarray with distinct elements (hence it starts with 0). The second pointer goes through the array, starting from index 1.If the numbers referred by two pointers are different, we pad the number from back to head.

Code (Java):

public class Solution {
    public int removeDuplicates(int[] A) {
        int j = 0;
        if(A.length == 0)
            return 0;
        for(int i = 1; i < A.length; ++i) {
            if(A[i] != A[j]) {
                j++;
                A[j] = A[i];
            }
        }
        return j + 1;
    }
}

Code (C++):

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int j = 0;
        if(n == 0)
            return 0;
        for(int i = 1; i < n; ++i) {
            if(A[i] != A[j]) {
                j++;
                A[j] = A[i];
            }
        }
        return j + 1;
    }
};

contiguous subarray with largest sum in an array (Maximum Subarray)

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Thoughts:
For each element in the array, we want to track the subarray with the largest sum ending here. And the largest of those largest sums is the result we need. So how do we track the largest sum ending at a particular position? We can keep adding up positive numbers. We can also add negative numbers as long as the sum would be less than 0. If it’s smaller than 0, we need to reset from this position by starting the sum from 0. In the above example, the largest sums ending at each position are [-2,1,-3,4,3,5,6,1,5]. Hence the largest sum is 6.

code (Java):

public class Solution {
    public int maxSubArray(int[] A) {
        int maxSumSoFar = Integer.MIN_VALUE;
        int maxSumEndingHere = 0;
        
        for(int num : A) {
            maxSumEndingHere = Math.max(maxSumEndingHere + num, num);
            maxSumSoFar = Math.max(maxSumSoFar, maxSumEndingHere);
        }
        
        return maxSumSoFar;
    }
}

Code (C++):

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int maxSumSoFar = INT_MIN;
        int maxSumEndingHere = 0;
        for(int i = 0; i < n; ++i) {
            maxSumEndingHere = max(maxSumEndingHere+A[i], A[i]);
            maxSumSoFar = max(maxSumSoFar, maxSumEndingHere);
        }
        return maxSumSoFar;
    }
};

Previous Older Entries