LeetCode [336] Palindrome Pairs

LeetCode [334] Increasing Triplet Subsequence

 334. Increasing Triplet Subsequence

Medium

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.

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

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

1 2 3 4 5 6 7 8 9 10 11 12 13

bool increasingTriplet(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); for(int i=1; i<n; ++i){ for(int j=0; j<i; ++j){ if(nums[i]>nums[j]){ dp[i] = max(dp[i], dp[j]+1); if(dp[i]>=3) return true; } } } return false; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

bool increasingTriplet1(vector<int>& nums) { vector<int> dp; for(auto n:nums){ if(dp.empty()||n>dp.back()){ dp.push_back(n); if(dp.size()>=3) return true; }else{ int l = 0, r = dp.size()-1; while(l<=r){ int m = (l+r)/2; if((m==0||n>dp[m-1])&&n<=dp[m]){ dp[m]=n; break; }else if(n>dp[m]){ l = m+1; }else{ r = m-1; } } } } return false; }

1 2 3 4 5 6 7 8 9

bool increasingTriplet2(vector<int>& nums) { int c1 = INT_MAX, c2 = INT_MAX; for(auto n:nums){ if(n<=c1) c1 = n; else if(n<=c2) c2 = n; else return true; } return false; }

LeetCode [333] Largest BST Subtree

Ref

[1] https://leetcode.com/problems/largest-bst-subtree/

LeetCode [332] Reconstruct Itinerary

332. Reconstruct Itinerary

Medium

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:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { Map<String, PriorityQueue<String>> targets = new HashMap<>(); List<String> route = new LinkedList(); public List<String> findItinerary(List<List<String>> tickets) { for (List<String> ticket : tickets) targets.computeIfAbsent(ticket.get(0), k -> new PriorityQueue()).add(ticket.get(1)); visit("JFK"); return route; } void visit(String airport) { while(targets.containsKey(airport) && !targets.get(airport).isEmpty()) visit(targets.get(airport).poll()); route.add(0, airport); } }

LeetCode [331] Verify Preorder Serialization of a Binary Tree

Ref
[1] https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
[2] https://leetcode.com/discuss/83824/7-lines-easy-java-solution
[3] https://leetcode.com/discuss/83825/simple-python-solution-using-stack-with-explanation

LeetCode [330] Patching Array

Ref
[1] https://leetcode.com/problems/patching-array/
[2] https://leetcode.com/discuss/82822/solution-explanation

LeetCode [329] Longest Increasing Path in a Matrix

329. 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:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { vector<vector<int>> dir{{1,0},{-1,0},{0,-1},{0,1}}; public: int longestIncreasingPath(vector<vector<int>>& matrix) { int m = matrix.size(); if(m==0) return 0; int n = matrix[0].size(); if(n==0) return 0; vector<vector<int>> dp(m, vector<int>(n, -1)); int ret = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(dp[i][j]<0){ dfs(matrix, dp, i, j, m, n); } ret = max(ret, dp[i][j]); } } return ret; } void dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int i, int j, int m, int n){ dp[i][j] = 1; for(auto d:dir){ int ii = i+d[0], jj = j+d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n && matrix[i][j]<matrix[ii][jj]){ if(dp[ii][jj]<0){ dfs(matrix, dp, ii, jj, m, n); } dp[i][j] = max(dp[i][j], 1+dp[ii][jj]); } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

//Java class Solution { int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; int ret = 0; int m, n; int[][] dp; public int longestIncreasingPath(int[][] matrix) { m = matrix.length; if(m==0) return 0; n = matrix[0].length; if(n==0) return 0; dp = new int[m][n]; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ dp[i][j] = -1; } } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(dp[i][j]<0) helper(matrix, i, j); ret = Math.max(ret, dp[i][j]); } } return ret; } void helper(int[][] matrix, int i, int j){ dp[i][j] = 1; for(int[] d : dir){ int ii = i + d[0]; int jj = j + d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n && matrix[i][j]<matrix[ii][jj]){ if(dp[ii][jj]<0){ helper(matrix, ii, jj); } dp[i][j] = Math.max(dp[i][j], dp[ii][jj]+1); } } } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

//O((mn)^2) class Solution { int m, n; int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; public int longestIncreasingPath(int[][] matrix) { m = matrix.length; if(m == 0) return 0; n = matrix[0].length; if(n == 0) return 0; int[][] dp = new int[m][n]; for(int i=0; i<m; ++i){ Arrays.fill(dp[i], 1); } boolean cont = true; while(cont){ cont = false; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ for(int[] d : dirs){ int ii = i+d[0], jj = j+d[1]; if(ii>=0 && ii<m && jj>=0 && jj<n){ if(matrix[ii][jj]>matrix[i][j]){ if(dp[ii][jj]<dp[i][j]+1){ cont = true; dp[ii][jj] = dp[i][j]+1; } } } } } } } int ret = 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ ret = Math.max(ret, dp[i][j]); } } return ret; } }

LeetCode [328] Odd Even Linked List

 328. Odd Even Linked List

Medium

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 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

 

Constraints:

• 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 ...
• The length of the linked list is between [0, 10^4].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/** * 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) return NULL; ListNode* p = head->next; ListNode* t = head; while(p && p->next){ ListNode* next = p->next->next; ListNode* c = p->next; c->next = t->next; t->next = c; t = c; p->next = next; p = next; } return head; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode oddEvenList(ListNode head) { ListNode HO = new ListNode(); ListNode HE = new ListNode(); ListNode pO = HO; ListNode pE = HE; ListNode p = head; int i=1; while(p!=null){ ListNode next = p.next; p.next = null; if(i%2==1){ pO.next = p; pO = p; }else{ pE.next = p; pE = p; } p = next; i++; } pO.next = HE.next; return HO.next; } }

LeetCode [327] Count of Range Sum

327. 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:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.

 

Constraints:

• 0 <= nums.length <= 10^4

//C++
//C++: TLE Divide and Conquer
class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        if(nums.empty() || lower>upper) return 0;
        int n = nums.size();
        if(n==1) return nums[0]>=lower&&nums[0]<=upper?1:0;
        vector<int> left(nums.begin(), nums.begin()+n/2);
        vector<int> right(nums.begin()+n/2, nums.end());
        int nl = countRangeSum(left, lower, upper);
        int nr = countRangeSum(right, lower, upper);

        for(int i=left.size()-2; i>=0; --i){
            left[i] += left[i+1];
        }
        for(int i=1; i<right.size(); ++i){
            right[i] += right[i-1];
        }
        sort(right.begin(), right.end());

        int c = 0;
        for(auto e:left){
            int a = lower-e, b = upper-e;
            int l = 0, r = right.size()-1;
            while(l<=r){
                if(right[l]<a){
                    l++;
                }else if(right[r]>b){
                    r--;
                }else{
                    break;
                }
            }
            c += r-l+1;
        }
        return c+nl+nr;
    }
};
]]></script>

<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: 72ms
typedef long long ll;

class Solution {
public:
    vector<ll> dm(vector<ll> nums, int lower, int upper, int &ret){
        int n = nums.size();
        if(n<2) return nums;
        vector<ll> left = dm(vector<ll>(nums.begin(), nums.begin()+n/2), lower, upper, ret);
        vector<ll> right = dm(vector<ll>(nums.begin()+n/2, nums.end()), lower, upper, ret);
        int nl = left.size(), nr = right.size(), t = 0, i = 0, j = 0, k = 0, index=-1;
        vector<ll> merge(n);
        for(; i<nl; ++i){
            while(j<nr && right[j]-left[i]<lower) j++;
            while(k<nr && right[k]-left[i]<=upper) k++;
            ret += k-j;
            while(t<nr && right[t]<=left[i]){
                merge[++index] = right[t++];
            }
            merge[++index] = left[i];
        }
        while(index<n-1){
            merge[++index] = right[t++];
        }
        return merge;
    }


    int countRangeSum(vector<int>& nums, int lower, int upper) {
        int ret = 0, n =  nums.size()+1;
        vector<ll> sums(n, 0);
        for(int i=1; i<n; ++i) sums[i] = sums[i-1] + nums[i-1];
        dm(sums, lower, upper, ret);
        return ret;
    }
};

//Java
class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        long[] array = new long[n+1];
        for(int i=1; i<=n; ++i){
            array[i] = array[i-1] + nums[i-1];
        }
        return helper(array, 0, n, lower, upper);
    }

    int helper(long[] array, int start, int end, int lower, int upper){
        if(end-start+1<2) return 0;
        int mid = (start+end)/2, count = 0;
        count += helper(array, start, mid, lower, upper);
        count += helper(array, mid+1, end, lower, upper);

        int j = mid+1, k = mid+1, l = mid+1, m = 0;
        long[] cache = new long[end-start+1];
        for(int i=start; i<=mid; ++i){
            while(j<=end && array[j]-array[i]<lower) j++;
            while(k<=end && array[k]-array[i]<=upper) k++;
            count += k-j;
            while(l<=end && array[l]<=array[i]) cache[m++] = array[l++];
            cache[m++] = array[i];
        }

        System.arraycopy(cache, 0, array, start, m);
        return count;
    }
}