LeetCode Q335: Self Crossing (hard)

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │

Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return true (self crossing)

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:

There are only three cases where the line will intersect itself.

where red point is the start point.

	class Solution {
	public:
	bool isSelfCrossing(vector<int>& x) {
	if(x.size()<=3)
	return false;
	for(int i = 3; i<x.size(); i++){
	if(x[i-1]<=x[i-3]&&x[i]>=x[i-2])
	return true;
	if(i>=4&&x[i-1]==x[i-3]&&x[i-2]<=x[i]+x[i-4])
	return true;
	if(i>=5&&x[i-2]>=x[i-4] && x[i-4]+x[i]>=x[i-2] && x[i-1]<=x[i-3] && x[i-5] + x[i-1]>=x[i-3])
	return true;
	}
	return false;
	}
	};

view raw Q335.cpp hosted with ❤ by GitHub

LeetCode Q334: Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Solution:

The solution of the question is same to Q300: Longest Increasing Subsequence.

Time complexity O(nlogn)

	class Solution {
	public:
	bool increasingTriplet(vector<int>& nums) {
	if(nums.empty())
	return 0;
	set<int> set;
	for(int i=0; i<nums.size(); i++){
	auto it = set.lower_bound(nums[i]);
	if(it==set.end()){
	set.insert(nums[i]);
	if(set.size()>=3)
	return true;
	}else{
	set.erase(it);
	set.insert(nums[i]);
	}
	}
	return false;
	}
	};

view raw Q334.cpp hosted with ❤ by GitHub

LeetCode Q333: Largest BST Subtree

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one. 
The return value is the subtree's size, which is 3.

Hint:

1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

Solution:

Use solution in Q98. Validate Binary Search Tree to solve this problem.

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int helper(TreeNode* root, int& upperBound, int& lowerBound, int& maxNum){
	int res=0;
	if(root==NULL){
	upperBound=INT_MIN;
	lowerBound=INT_MAX;
	return res;
	}
	int lub, llb, rub, rlb;
	int lnum=helper(root->left, lub, llb, maxNum);
	int rnum=helper(root->right, rub, rlb, maxNum);
	lowerBound=root->left==NULL? root->val:llb;
	upperBound=root->right==NULL? root->val:rub;
	if(root->val>=lub&&root->val<=rlb&&lnum!=-1&&rnum!=-1){
	res=lnum+rnum+1;
	maxNum=max(res, maxNum);
	}else
	res=-1;
	return res;
	}
	int largestBSTSubtree(TreeNode* root) {
	int maxNum=0;
	if(root==NULL)
	return maxNum;
	int upperBound, lowerBound;
	helper(root, upperBound, lowerBound, maxNum);
	return maxNum;
	}
	};

view raw Q333.cpp hosted with ❤ by GitHub

LeetCode Q332: Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].

Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.

Solution:

	class Solution {
	public:
	vector<string> findItinerary(vector<pair<string, string>> tickets) {
	// Each node (airport) contains a set of outgoing edges (destination).
	unordered_map<string, multiset<string>> graph;
	// We are always appending the deepest node to the itinerary,
	// so will need to reverse the itinerary in the end.
	vector<string> itinerary;
	if (tickets.size() == 0){
	return itinerary;
	}
	// Construct the node and assign outgoing edges
	for (pair<string, string> eachTicket : tickets){
	graph[eachTicket.first].insert(eachTicket.second);
	}
	stack<string> dfs;
	dfs.push("JFK");
	while (!dfs.empty()){
	string topAirport = dfs.top();
	if (graph[topAirport].empty()){
	// If there is no more outgoing edges, append to itinerary
	// Two cases:
	// 1. If it searchs the terminal end first, it will simply get
	// added to the itinerary first as it should, and the proper route
	// will still be traversed since its entry is still on the stack.
	// 2. If it search the proper route first, the dead end route will also
	// get added to the itinerary first.
	itinerary.push_back(topAirport);
	dfs.pop();
	}
	else {
	// Otherwise push the outgoing edge to the dfs stack and
	// remove it from the node.
	dfs.push(*(graph[topAirport].begin()));
	graph[topAirport].erase(graph[topAirport].begin());
	}
	}
	// Reverse the itinerary.
	reverse(itinerary.begin(), itinerary.end());
	return itinerary;
	}
	};

view raw Q332.cpp hosted with ❤ by GitHub

LeetCode Q331: Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_

    /   \

   3     2

  / \   / \

 4   1  #  6

/ \ / \   / \

# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:

"9,3,4,#,#,1,#,#,2,#,6,#,#"

Return true

Example 2:

"1,#"

Return false

Example 3:

"9,#,#,1"

Return false

Solution:

Idea is to simulate preorder traversal using a stack. Whenever meet a number, we push it to stack, which is to simulate go along the path down to the bottom left. When it is a #, we pop the stack. There are two situation during this process you should return a false. first, stack becomes empty but there are remaining string. Second, string is empty but stack is not.

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	if(preorder.length()==0)
	return false;
	vector<string> str;
	int i=0;
	string s;
	while(i<=preorder.length()){
	if(preorder[i]==','||i==preorder.length()){
	str.push_back(s);
	s=string("");
	}else{
	s=s+string(1, preorder[i]);
	}
	i++;
	}
	stack<string> myStack;
	i=0;
	while(i<str.size()){
	if(str[i]!="#"){
	myStack.push(str[i]);
	}else{
	if(myStack.empty()&&i!=str.size()-1)
	return false;
	if(!myStack.empty()&&i==str.size()-1)
	return false;
	if(i!=str.size()-1)
	myStack.pop();
	}
	i++;
	}
	return myStack.empty();
	}
	};

view raw Q331.cpp hosted with ❤ by GitHub

Round 2 solution:
When meet a '#', we keep removing '#' and one additional node from the stack. After all available removal, we push back one '#'. So at the end, the valid solution will have only one '#' in the stack.

	class Solution {
	public:
	bool isValidSerialization(string preorder) {
	bool res=true;
	stack<string> myStack;
	if(preorder.empty())
	return res;
	int p=0;
	string str;
	while(p<preorder.length()&&preorder[p]!=','){
	str+=string(1, preorder[p]);
	p++;
	}
	p++;
	myStack.push(str);
	str=string("");
	string pre = preorder;
	while(!myStack.empty()&&p<=preorder.length()){
	if(p==preorder.length()||pre[p]==','){
	if(str==string(1, '#')){
	while(!myStack.empty() && myStack.top()==string("#")){
	myStack.pop();
	if(myStack.empty())
	return false;
	myStack.pop();
	}
	myStack.push(string("#"));
	}else{
	myStack.push(str);
	}
	str=string("");
	}else{
	str=str+string(1, pre[p]);
	}
	p++;
	}
	if(myStack.size()==1&&myStack.top()==string("#"))
	return true;
	else
	return false;
	}
	};

view raw Q331Rnd2.cpp hosted with ❤ by GitHub

LeetCode Q329: Longest Increasing Path in a Matrix (hard)

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution 1:

It is not hard to think of DFS. But, its expensive to start a DFS for each entry. When thinking deeper, we notice that, we don't have to do DFS again at some entries if these entries have been accessed before with longest path already computed. To accelerate our computation, we can use memoization to save these information.

	class Solution {
	public:
	int DFS(int row, int col, vector<vector<int> >& matrix, vector<vector<int> >& steps){
	if(steps[row][col]!=0)
	return steps[row][col];
	int maxLen=INT_MIN;
	int dir[8] = {-1, 0, 1, 0, 0, -1, 0, 1};
	for(int i=0; i<4; i++){
	int r = row+dir[i*2];
	int c = col+dir[i*2+1];
	if(r<0||r>=matrix.size()||c<0||c>=matrix[0].size()||matrix[r][c]<=matrix[row][col])
	continue;
	maxLen = max(DFS(r, c, matrix, steps)+1, maxLen);
	}
	steps[row][col]=maxLen==INT_MIN? 1:maxLen;
	return steps[row][col];
	}
	int longestIncreasingPath(vector<vector<int>>& matrix) {
	if(matrix.empty())
	return 0;
	vector<vector<int> > steps(matrix.size(), vector<int>(matrix[0].size(), 0));
	int maxLen=INT_MIN;
	for(int i=0; i<matrix.size(); i++)
	for(int j=0; j<matrix[0].size(); j++)
	maxLen=max(maxLen, DFS(i, j, matrix, steps));
	return maxLen;
	}
	};

view raw Q329.cpp hosted with ❤ by GitHub

LeetCode Q328: Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...

Solution:

Set odd pointer and even pointer, link two pointers to next odd/even nodes alternatively.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* oddEvenList(ListNode* head) {
	if(head==NULL||head->next==NULL)
	return head;
	ListNode* oddHead=head;
	ListNode* evenHead=head->next;
	ListNode* oddp=head;
	ListNode* evenp=head->next;
	while(oddp->next!=NULL&&evenp->next!=NULL){
	oddp->next = evenp!=NULL? evenp->next:NULL;
	oddp=oddp->next;
	evenp->next = oddp!=NULL? oddp->next:NULL;
	evenp=evenp->next;
	}
	oddp->next = evenHead;
	return oddHead;
	}
	};

view raw Q328.cpp hosted with ❤ by GitHub