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

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

(Longest Palindromic Substring)

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Thoughts:
The idea is to use a stack to store all the index of ‘(‘ we encountered. We maintain a variable “startIndex” to store the earliest starting position of a ‘(‘, this is used to determine the start position (hence the length) of a possible solution. If we see a ‘)’, we can pop out a ‘(‘ to construct a parenthesis. Hence we have a candidate. After doing that, if the stack is empty, we can fetch the earliest starting position to calculate the length of this solution (this scenario occurs when we see the last index of “(()())”). If the stack is not empty yet, we can calculate the length by comparing the current index with the index of the top element in the stack (this scenario happens when we process the last index of “(()”).
Code (Java):

import java.util.Stack;
public class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int len = 0;
        int maxLen = 0;
        int startIndex = s.length();
        for(int i = 0; i < s.length(); ++i) {
            if(s.charAt(i) == '(') {
                stack.push(i);
                continue;
            }
            
            if(stack.isEmpty()) {
                startIndex = s.length();
            } else {
                startIndex = Math.min(stack.peek(), startIndex);
                stack.pop();
                
                if(stack.isEmpty()) {
                    len = i - startIndex + 1;
                } else {
                    len = i - stack.peek();
                }
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}

Code (C++):

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> Stack;
        int len = 0;
        int maxLen = 0;
        int startIndex = s.size();
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] == '(') {
                Stack.push(i);
                continue;
            }
            
            if(Stack.empty()) {
                startIndex = s.size();
            } else {
                startIndex = min(Stack.top(), startIndex);
                Stack.pop();
                
                if(Stack.empty()) {
                    len = i - startIndex + 1;
                } else {
                    len = i - Stack.top();
                }
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }
};

(Longest Substring Without Repeating Characters)

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Thoughts:
We want to finish this task in one scan. We can maintain a hashtable to detect if we have seen any character. We start from the beginning and walk through the array until we hit a repetition, let’s say, at position i. We then have two piece of valuable information right now:

  1. s[0..i-1] is a candidate of the longest substring without repetition. Therefore we can update the max length.
  2. There exists a position 0 \leq j \leq i-1, such that s[j] == s[i]. Substring starting from j is not a candidate because it has at least one repetition: s[j] and s[i]. Any substring ended at j will be shorter than the substring s[0..i-1] so we don’t need to look at them.

Then we can remove every elements in the hashtable from 0 to j, and make the start position of next candidate to j + 1. We keep walking and repeating this process until we hit the last element.

Code (Java):

import java.util.HashSet;
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        int candidateStartIndex = 0;
        for(int iter = 0; iter < s.length(); ++iter) {
            char c = s.charAt(iter);
            if(set.contains(c)) {
                max = Math.max(max, iter - candidateStartIndex);
                while(s.charAt(candidateStartIndex) 
                        != s.charAt(iter)) {
                    set.remove(s.charAt(candidateStartIndex));
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                set.add(c);
            }
        }
        max = Math.max(max, s.length() - candidateStartIndex);
        return max;
    }
}

Code (C++):

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unsigned int maxLen = 0;
        set<char> hashtable;
        int candidateStartIndex = 0;
        for(unsigned int iter = 0; iter < s.size(); ++iter) {
            char c = s[iter];
            if(hashtable.find(c) != hashtable.end()) {
                maxLen = max(maxLen, iter - candidateStartIndex);
                while(s[candidateStartIndex] != s[iter]) {
                    hashtable.erase(s[candidateStartIndex]);
                    candidateStartIndex++;
                }
                candidateStartIndex++;
            } else {
                hashtable.insert(c);
            }
        }
        maxLen = max(maxLen, s.size() - candidateStartIndex);
        return maxLen;
    }
};

Previous Older Entries Next Newer Entries