(String to Integer (atoi))

Implement atoi to convert a string to an integer.

Thoughts:
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Code (Java):

	public int atoi(String number) {
		if (number == null || number.trim().length() == 0) {
			return 0;
		}

		int result = 0;
		number = number.trim();

		boolean negate = false;
		char sign = number.charAt(0);

		if (sign == '+' || sign == '-') {
			if (sign == '-') {
				negate = true;
			}
			number = number.substring(1);
		}

		int length = number.length();
		int start = -1;
		int index = 0;
		for (; index < length; index++) {
			char a = number.charAt(index);
			if (a >= '0' && a <= '9') {
				if (start == -1)
					start = index;
			} else {
				break;
			}
		}
		int end = index - 1;

		if (start == -1)
			return 0;

		for (int i = start; i <= end; ++i) {
			char a = number.charAt(i);
			int digit = a - '0';
			if (!negate) {
				if (result + digit * (int) Math.pow(10, end - i) >= result)
					result += digit * (int) Math.pow(10, end - i);
				else
					result = Integer.MAX_VALUE;
			} else {
				if (result - digit * (int) Math.pow(10, end - i) <= result)
					result -= digit * (int) Math.pow(10, end - i);
				else
					result = Integer.MIN_VALUE;
			}
		}

		return result;
	}

Code (C++):

class Solution {
public:
    int atoi(const char *str) {
        if (str == NULL) {
            return 0;
        }
        string number(str);
        if(number.size() == 0)
            return 0;
        
        int i = 0;
        for(; i < number.size(); ++i) {
            if(!isspace(number[i])) {
                break;
            }
        }
        number = number.substr(i);
        int result = 0;
        
        bool negate = false;
        char sign = number[0];

        if (sign == '+' || sign == '-') {
            if (sign == '-') {
                negate = true;
            }
            number = number.substr(1);
        }

        int length = number.size();
        int start = -1;
        int index = 0;
        for (; index < length; index++) {
            char a = number[index];
            if (a >= '0' && a <= '9') {
                if(start == -1)
                    start = index;
            } else {
                break;
            }
        }
        int end = index - 1;

        if (start == -1)
            return 0;

        for (int i = start; i <= end; ++i) {
            char a = number[i];
            int digit = a - '0';
            if (!negate) {
                if (result + digit * (int) pow(10, end - i) >= result)
                    result += digit * (int) pow(10, end - i);
                else
                    result = INT_MAX;
            } else {
                if (result - digit * (int) pow(10, end - i) <= result)
                    result -= digit * (int) pow(10, end - i);
                else
                    result = INT_MIN;
            }
        }

        return result;
    }
};
Advertisements

(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 List)

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Thoughts:
This question is the same as ‘remove duplicates from sorted array’ except that we need to deal with linked list this time. The algorithm is the same.

Code (Java):

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return null;
        ListNode j = head;
        ListNode i = head.next;
        while(i != null) {
            if(j.val != i.val) {
                j = j.next;
                j.val = i.val;
            }
            i = i.next;
        }
        j.next = null;
        return head;
    }
}

Code (C++):

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL)
            return head;
        ListNode *j = head;
        ListNode *i = j -> next;
        while(i != NULL) {
            if(i -> val != j -> val) {
                j = j -> next;
                j -> val = i -> val;
            }
            i = i -> next;
        }
        j -> next = NULL;
        return head;
    }
};

(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;
    }
};

Maximal rectangle with 1’s in a binary matrix (Maximal Rectangle)

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Thoughts:
If we think the matrix as a number of rows and each row is a histogram then we can reduce the problem to the Largest Rectangle in Histogram problem. So how can we view each row as histogram? Consider the following binary matrix:

11000
11000
00111
00111
00111

The largest rectangle should be 3*3, apparently. What makes up a rectangle? There are 3 columns there, if you like, and each of them contains 3 consecutive ones. So if for each row, we count how many consecutive ones we have above us, we can construct 5 histograms:

11000
22000
00111
00222
00333

Then we can compute the largest rectangle for each row and we will find out that the last row contains a maximal rectangle with area of 5 in its histogram.

Code (Java):

import java.util.Stack;
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) 
            return 0;
        int[][] auxillary = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; ++i) {
            for(int j = 0; j < matrix[i].length; ++j) {
                auxillary[i][j] = Character.getNumericValue(matrix[i][j]);
            }
        }
        for(int i = 1; i < auxillary.length; ++i) {
            for(int j = 0; j < auxillary[i].length; ++j) {
                if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }
        
        int max = 0;
        for(int i = 0; i < auxillary.length; ++i) {
            max = Math.max(max, largestRectangleArea(auxillary[i]));
        }
        return max;
    }
    
    private int largestRectangleArea(int[] height) {
        Stack<Integer> stack = 
            new Stack<Integer>();
        int max = 0;
        int i = 0;
        while(i < height.length) {
            if(stack.isEmpty() || 
                height[i] >= stack.peek()) {
                stack.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack.isEmpty() && 
                    stack.peek() > height[i]) {
                    count++;
                    int top = stack.pop();
                    max = Math.max(max, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack.isEmpty()) {
            count++;
            max = Math.max(max, stack.pop() * count);
        }
        return max;
    }
}

Code (C++):

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.size() == 0) 
            return 0;
        vector<vector<int> > auxillary;
        for(int i = 0; i < matrix.size(); ++i) {
            vector<int> temp;
            for(int j = 0; j < matrix[i].size(); ++j) {
                temp.push_back(matrix[i][j] - '0');
            }
            auxillary.push_back(temp);
        }
        for(int i = 1; i < auxillary.size(); ++i) {
            for(int j = 0; j < auxillary[i].size(); ++j) {
                if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }
        
        int maxArea = 0;
        for(int i = 0; i < auxillary.size(); ++i) {
            maxArea = max(maxArea, largestRectangleArea(auxillary[i]));
        }
        return maxArea;
    }
    
private:
    int largestRectangleArea(vector<int> &height) {
        stack<int> stack_;
        int maxArea = 0;
        int i = 0;
        while(i < height.size()) {
            if(stack_.empty() || 
                height[i] >= stack_.top()) {
                stack_.push(height[i]);
                i++;
            }
            else {
                int count = 0;
                while(!stack_.empty() && 
                    stack_.top() > height[i]) {
                    count++;
                    int top = stack_.top();
                    stack_.pop();
                    maxArea = max(maxArea, top * count);
                }
                for(int j = 0; j < count + 1; ++j) {
                    stack_.push(height[i]);
                }
                i++;
            }
        }
        
        int count = 0;
        while(!stack_.empty()) {
            count++;
            maxArea = max(maxArea, stack_.top() * count);
            stack_.pop();
        }
        return maxArea;
    }
};