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

__ATA.cmd.push(function() {
__ATA.initDynamicSlot({
id: 'atatags-26942-61ae011c86a91',
location: 120,
formFactor: '001',
label: {
},
creative: {
},
privacySettings: {
text: 'Privacy',

}
}
});
});


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

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-61ae011c88683', {
sectionId: '370373',
});
});



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



## (Longest Palindromic Substring)

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Thoughts:
Two parts of this question: determine if a string is palindrome and find out the longest palindrome. First part can be done in recursive or iterative way. We just need to check if the 1st letter == last letter, 2nd letter == 2nd last letter, so on and so forth. Second part we can do it using a sliding window approach. We examine if the entire string is palindrome or not, then the substrings of length n – 1 (there are two of them), then the substrings of length n – 2 (3 of them), etc.

Code (Java):

public class Solution {
public String longestPalindrome(String s) {
for(int len = s.length(); len > 0; --len) {
for(int j = 0; j <= s.length() - len; ++j) {
String sub = s.substring(j, j + len);
if(isPalindrome(sub))
return sub;
}
}
return new String();
}

private boolean isPalindrome(String s) {
if(s.length() <= 1)
return true;
else
return s.charAt(0) == s.charAt(s.length()-1) &&
isPalindrome(s.substring(1,s.length()-1));
}
}

Code (C++):
class Solution {
public:
string longestPalindrome(string s) {
for(int len = s.size(); len > 0; --len) {
for(int i = 0; i <= s.size() - len; ++i) {
string sub = s.substr(i, len);
if(isPalindrome(sub))
return sub;
}
}
return "";
}

private:
bool isPalindrome(string s) {
if(s.size() <= 1)
return true;
else
return s[0] == s[s.size() - 1] &&
isPalindrome(s.substr(1,s.size()-2));
}
};



## Find the longest common prefix in an array of strings (Longest Common Prefix)

Write a function to find the longest common prefix string amongst an array of strings.

Thoughts:
Apparently this can be done in $O(n)$. We start with the first string as the longest common prefix. We then go through every string in the array and compare the prefix with them. Update (shorten) the prefix if needed.

Code (Java):

public class Solution {
public String longestCommonPrefix(String[] strs) {
String prefix = new String();
if(strs.length > 0)
prefix = strs[0];
for(int i = 1; i < strs.length; ++i) {
String s = strs[i];
int j = 0;
for(; j < Math.min(prefix.length(), s.length()); ++j) {
if(prefix.charAt(j) != s.charAt(j)) {
break;
}
}
prefix = prefix.substring(0, j);
}
return prefix;
}
}

Code (C++):
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
string prefix;
if(strs.size() > 0)
prefix = strs[0];
for(int i = 1; i < strs.size(); ++i) {
string s = strs[i];
int j = 0;
for(; j < min(prefix.size(), s.size()); ++j) {
if(prefix[j] != s[j])
break;
}
prefix = prefix.substr(0, j);
}
return prefix;
}
};



## (Letter Combinations of a Phone Number)

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Thoughts:
Another classic recursion problem. We try to generate solution each time by iterating through every digit and every character that digit maps to. If we overflow, we cut that solution and stop. If we get the correct solution (where solution.length() == digits.length()), we add to the solution set.

Code (Java):

public class Solution {
private HashMap<Character, String> map;

public ArrayList<String> letterCombinations(String digits) {
setup();
ArrayList<String> solutions
= new ArrayList<String>();
recursion(digits, 0, new String(), solutions);
return solutions;
}

private void recursion(String digits, int start,
String sol, ArrayList<String> solutions) {
if(sol.length() > digits.length()) {
return;
} else if(sol.length() == digits.length()) {
return;
} else {
for(int i = start; i < digits.length(); ++i) {
String letters = map.get(digits.charAt(i));
for(int j = 0; j < letters.length(); ++j) {
recursion(digits, i + 1, sol + letters.charAt(j), solutions);
}
}
}
}

private void setup() {
map = new HashMap<Character, String>();
map.put('1', "");
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
map.put('0', " ");
}
}

Code (C++):
class Solution {
public:
vector<string> letterCombinations(string digits) {
setup();
vector<string> solutions;
string s;
recursion(digits, 0, s, solutions);
return solutions;
}

private:
map<char, string> mapping;
void recursion(string digits, int start,
string sol, vector<string>& solutions) {
if(sol.size() > digits.size()) {
return;
} else if(sol.size() == digits.size()) {
solutions.push_back(sol);
return;
} else {
for(int i = start; i < digits.size(); ++i) {
string letters = mapping[digits[i]];
for(int j = 0; j < letters.size(); ++j) {
recursion(digits, i + 1, sol + letters[j], solutions);
}
}
}
}

void setup() {
mapping.clear();
mapping['1'] = "";
mapping['2'] = "abc";
mapping['3'] = "def";
mapping['4'] = "ghi";
mapping['5'] = "jkl";
mapping['6'] = "mno";
mapping['7'] = "pqrs";
mapping['8'] = "tuv";
mapping['9'] = "wxyz";
mapping['0'] = " ";
}
};



## (Length of Last Word)

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = “Hello World”,
return 5.

Thoughts:
We just need to iterate from the last position of the string, find the first index that is not space, and count from there backwards.

Code (Java):

public class Solution {
public int lengthOfLastWord(String s) {
int length = 0;
int i = s.length() - 1;
while(i >= 0 && s.charAt(i) == ' ') {
i--;
}
while(i >= 0 && s.charAt(i) != ' ') {
length++;
i--;
}
return length;
}
}

Code (C++):
class Solution {
public:
int lengthOfLastWord(const char *s) {
int length = 0;
int i = strlen(s) - 1;
while(i >= 0 && s[i] == ' ') {
i--;
}
while(i >= 0 && s[i] != ' ') {
length++;
i--;
}
return length;
}
};



## (Largest Rectangle in Histogram)

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

Thoughts:
The point of this algorithm is to maintain a stack where higher element is always greater or equal to the lower element. Why do we need to maintain that kind of stack? Because if we have a non-decreasing list, we can easily calculate the maximum area in one scan. We just need to compare: height[i] * (n – i) for every i. So how do we maintain this stack? If we keep seeing larger element, we just need to push them onto the stack. If we see a smaller (compared to the top element on the stack) element, we need to do two things:

1. Pop the stack until we can maintain the non-decreasing order. Pushing the smaller element for m times, where m = number of poped elements.
2. Keep track of the maximum area that cause by those pop.

For example, we have height = {1,3,5,7,4}.
We push onto the stack for {1,3,5,7} then we see 4. 4 is less than 7, so we need to pop. We stop popping until we see 3. However many times we pop, we push 4 onto the stack. Therefore the resulted stack would be {1,3,4,4,4}. Because of popping 7, we need to remember that the maximum area that contains 7 is 7. The largest area that contains 5, the other element which get popped, is 10. So we take that down. We then finish processing all the elements in the original array and end up with a non-decreasing stack {1,3,4,4,4}. We can compute the largest area of this stack, which is 4*3 = 12. Since 12 is larger than the previous largest, 10, we output 12.

Code (Java):

public class Solution {
public 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 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;
}
};



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

Thoughts:
We use the similar approach as in Jump Game with the exception that table[i] now stores the minimum step it takes from position i to the last index. We update the table from end to start. At each position i, we look at every possible position j that one can reach from i, and then pick the least step it takes from j to the last index (i.e., table[j]). We then store table[j] + 1 in table[i]. When A[i] == 0, i.e., we cannot go anywhere from position i, we make table[i] = INT_MAX. Also when we cannot get to any intermediate position that will lead us to the last index, we make table[i] = INT_MAX.

Code (Java):

public class Solution {
public int jump(int[] A) {
int n = A.length;
int[] table = new int[n];
table[n-1] = 0;
for(int start = n - 2; start >= 0; --start) {
if(A[start] == 0) {
table[start] = Integer.MAX_VALUE;
} else if(n - 1 - start <= A[start]) {
table[start] = 1;
} else {
int min = Integer.MAX_VALUE;
for(int j = start + 1; j < n &&
j - start <= A[start]; ++j) {
if(table[j] < min) {
min = table[j];
}
}
table[start] = min == Integer.MAX_VALUE ?
min : min + 1;
}
}
return table[0];
}
}

Code (C++):
class Solution {
public:
int jump(int A[], int n) {
int *table = new int[n];
table[n-1] = 0;

for (int i = n-2; i >=0; i--) {
if (A[i] == 0)
table[i] = INT_MAX;
else if (A[i] >= n - i - 1)
table[i] = 1;
else {
int min = INT_MAX;
for (int j = i+1; j < n &&
j <= A[i] + i; j++) {
if (min > table[j])
min = table[j];
}
if (min != INT_MAX)
table[i] = min + 1;
else
table[i] = min;
}
}
return table[0];
}
};