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.

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)

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.

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:

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.

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.

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.

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.

LeetCode Q327: Count of Range Sum (hard)

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Solution 1:

My solution is to pre-processing the array and compute range sum, than build BST for searching. In C++, to allow duplicated nodes in a BST, you should use multimap.

Revised version of solution 1

Solution 2:
Analysis of the solution is given in this post.

LeetCode Q325: Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Solution:

This question remind me of using range sum which require you preprocessing the array and you can get sum of any range in constant time.

Once we preprocess the array, for each location given its range sum starting from 0, to quickly find the part with remaining sum, we should use hash table with range sum as key and array index as content.

LeetCode Q324: Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

Solution:

Please refer to this post

常数空间的解法：

Dutch National Flag Algorithm

Sort an array of 0s, 1s and 2s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

We strongly recommend that you click here and practice it, before moving on to the solution.

The problem is similar to our old post Segregate 0s and 1s in an array, and both of these problems are variation of famous Dutch national flag problem.

The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi–

— Dutch National Flag Algorithm, or 3-way Partitioning —

Part way through the process, some red, white and blue elements are known and are in the “right” place. The section of unknown elements, a[Mid..Hi], is shrunk by examining a[Mid]:

Examine a[Mid]. There are three possibilities: 
a[Mid] is (0) red, (1) white or (2) blue.
Case (0) a[Mid] is red, swap a[Lo] and a[Mid]; Lo++; Mid++




Case (1) a[Mid] is white, Mid++




Case (2) a[Mid] is blue, swap a[Mid] and a[Hi]; Hi--



Continue until Mid>Hi. 

Below is C implementation of above algorithm.

• C
• Java

// C program to sort an array with 0,1 and 2 // in a single pass #include   /* Function to swap *a and *b */ void swap(int *a, int *b);   // Sort the input array, the array is assumed to // have values in {0, 1, 2} void sort012(int a[], int arr_size) {     int lo = 0;     int hi = arr_size - 1;     int mid = 0;       while (mid <= hi)     {         switch (a[mid])         {         case 0:             swap(&a[lo++], &a[mid++]);             break;         case 1:             mid++;             break;         case 2:             swap(&a[mid], &a[hi--]);             break;         }     } }   /* UTILITY FUNCTIONS */ void swap(int *a, int *b) {     int temp = *a;     *a = *b;     *b = temp; }   /* Utility function to print array arr[] */ void printArray(int arr[], int arr_size) {     int i;     for (i = 0; i < arr_size; i++)         printf("%d ", arr[i]);     printf("\n"); }   /* driver program to test */ int main() {     int arr[] = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};     int arr_size = sizeof(arr)/sizeof(arr[0]);     int i;       sort012(arr, arr_size);       printf("array after segregation ");     printArray(arr, arr_size);       getchar();     return 0; }