[LeetCode] 334. Increasing Triplet Subsequence

Problem : https://leetcode.com/problems/increasing-triplet-subsequence/

Use 2 caches to save the minimal number from left and the maximal number from right of each position.

Return true when minimal_from_left < nums[i] < maximal_from_right.

Time Complexity = O ( N )

Space Complexity = O ( 2 * N )

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        mi = [0] * len(nums)
        mx = [0] * len(nums)
        
        mi_so_far = nums[0]
        for i in range(len(nums)):
            mi_so_far = min(mi_so_far, nums[i])
            mi[i] = mi_so_far
        
        mx_so_far = nums[-1]
        for i in reversed(range(len(nums))):
            mx_so_far = max(mx_so_far, nums[i])
            mx[i] = mx_so_far
        
        for i in range(len(nums)):
            if mi[i] < nums[i] < mx[i]:
                return True
        
        return False

Space Complexity O(1) Solution:

Use 2 pointers m1, m2 to save number with smaller value.

It finds the increasing triplet when find a number larger than both m1 and m2.

 
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        m1 = m2 = 2 ** 31 - 1 #MAX_INT
        
        for n in nums:
            if m1 >= n : 
                m1 = n
            elif m2 >= n :
                # find m2 > m1
                m2 = n
            else:
                # find m3 > m2 > m1
                return True
        
        return False

[LeetCode] 332. Reconstruct Itinerary

 Problem : https://leetcode.com/problems/reconstruct-itinerary/

Consider each city is a vertex in a directed graph, then every ticket is an edge between 2 vertices.

Use one hash table to track all available tickets. ( Notice : There could be duplicated tickets between 2 cities )

Then use DFS to find the possible path between city "JFK" to the ending city.

DFS ends when number of city = total number of tickets  + 1

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = defaultdict(list)
        allTickets = defaultdict(int)
        
        for src, dst in tickets:
            graph[src].append(dst)
            allTickets[(src,dst)] += 1
        
        for src in graph.keys():
            graph[src].sort()
        
        
        def dfs(src, path):
            if len(path) == len(tickets) + 1:
                return path
            
            for dst in graph[src]:
                if allTickets[(src,dst)] > 0:
                    allTickets[(src,dst)] -= 1
                    
                    tmp = dfs(dst, path + [dst])
                    if tmp:
                        return tmp
                    
                    allTickets[(src,dst)] += 1
                    
            return None
        
    
        return dfs("JFK", ["JFK"])

[LeetCode] 331. Verify Preorder Serialization of a Binary Tree

 Problem : https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

Re-create node list by splitting the input string with comma.

Then iterate the node list with pre-order traversal process.

Validate the tree node during traversal.

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        
        if not nodes : return True
        
        def helper(i):
            if i >= len(nodes):
                return (i, False)
            
            if nodes[i] == '#':
                return (i, True)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            i, result = helper(i+1)
            if not result:
                return (i, False)
            
            return (i, True)
        
        i, result = helper(0)
        
        return i == len(nodes) - 1 and result

[LeetCode] 329. Longest Increasing Path in a Matrix

 Problem : https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COLUMN = len(matrix[0])
        
        diff = ((0,1), (0,-1), (1,0), (-1,0))
        
        @cache
        def helper(y, x):
            """
            Longest increasing path starts from matrix[y][x]
            """
            result = 1
            for dx, dy in diff:
                nx = x + dx
                ny = y + dy
                if 0 <= nx < COLUMN and 0 <= ny < ROW and matrix[y][x] < matrix[ny][nx]:
                    # increasing sequence can only be built with one direction
                    # no need to mark the visited positions
                    result = max(result, 1 + helper(ny, nx))
            
            return result
        
        result = 1
        for y in range(ROW):
            for x in range(COLUMN):
                result = max(result, helper(y,x))
        return result

Edited on 04/10/2021. Use @cache annotation.

[LeetCode] 328. Odd Even Linked List

 Problem : https://leetcode.com/problems/odd-even-linked-list/

Use dummy list to save odd and even node separately:

/**
 * 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 odd = new ListNode();
        ListNode even = new ListNode();
        
        ListNode p = head;
        ListNode po = odd;
        ListNode pe = even;
        
        int count = 1;
        
        while (p != null) {
            if (count++ % 2 == 1) {
                po.next = p;
                po = po.next;
            } else {
                pe.next = p;
                pe = pe.next;
            }
            
            p = p.next;
        }
        
        po.next = even.next;
        pe.next = null;
        
        return odd.next;
    }
}

Edited on 12/01/2021. Replaced with iterative solution.

[LeetCode] 327. Count of Range Sum

 Problem : https://leetcode.com/problems/count-of-range-sum/

Time Complexity = O ( N ** 2 ). Time Limit Exceeded.

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        N = len(nums)
        
        sums = [0] * (N+1)
        
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
        result = 0
        for i in range(N+1):
            for j in range(i+1, N+1):
                if lower <= sums[j] - sums[i] <= upper:
                    result += 1
        
        return result

Count and merge sort solution:

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        
        def countAndMergeSort(sums, start, end):
            if end - start <= 1: return 0
            mid = start + (end - start) // 2
            
            count = countAndMergeSort(sums, start, mid) + countAndMergeSort(sums, mid, end)
            
            j = k = t = mid
            cache = [0] * (end - start)
            r = 0
            
            for i in range(start, mid):
                while k < end and sums[k] - sums[i] < lower: 
                    k += 1
                while j < end and sums[j] - sums[i] <= upper: 
                    j += 1
                while t < end and sums[t] < sums[i]:
                    cache[r] = sums[t]
                    r += 1
                    t += 1
    
                cache[r] = sums[i]
                r += 1
            
                count += j - k
            
            r = 0
            for i in range(start, t):
                sums[i] = cache[r]
                r += 1
            
            return count
            
        
        
        
        N = len(nums)
        
        sums = [0] * (N+1)    
        for i in range(N):
            sums[i+1] = sums[i] + nums[i]
        
    
        return countAndMergeSort(sums, 0, len(sums))
                
       

[LeetCode] 326. Power of Three

 Problem : https://leetcode.com/problems/power-of-three/

A naive solution:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 3 == 0 and self.isPowerOfThree(n // 3)

A math solution:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 3 ** (math.log2(n) // math.log2(3)) == n

Edited on 05/04/2021. Update the math solution.

[LeetCode] 324. Wiggle Sort II

 Problem : https://leetcode.com/problems/wiggle-sort-ii/

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        tmp = sorted(nums)
        N = len(tmp)
        
        i, j = ((N + 1) // 2) - 1, len(tmp) - 1
        k = 0
        
        while k < N:
            nums[k] = tmp[i]
            k += 1
            i -= 1
            
            if k == len(tmp):
                break
                
            nums[k] = tmp[j]
            k += 1
            j -= 1

[LeetCode] 322. Coin Change

Problem : https://leetcode.com/problems/coin-change/

Time Complexity = O ( M * N ),   M = amount,  N = len(coins).

Top-down Solution :

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        MAX_INT = 2 ** 31 - 1
        N = len(coins)
        coins.sort()
        
        @lru_cache(maxsize = None)
        def helper(amount):
            """
            Fewest number of coins needed
            to make up this amount.
            """
            if amount == 0:
                return 0
            
            result = MAX_INT
            
            for i in range(N):
                if coins[i] > amount:
                    break
                
                tmp = helper(amount - coins[i])
                if tmp != -1:
                    result = min(result, tmp + 1)
            
            return result if result != MAX_INT else -1
        
        
        return helper(amount)

Bottom-up Solution:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[n] = Fewest number of coins needed to make up amount n
        dp = [amount+1] * (amount + 1)
        dp[0] = 0
        
        coins.sort()
        
        for n in range(1, amount+1):
            for coin in coins:
                if coin > n:
                    break
                
                dp[n] = min(dp[n], dp[n-coin] + 1)
        
        return dp[-1] if dp[-1] != amount + 1 else -1

[LeetCode] 321. Create Maximum Number

 Problem : https://leetcode.com/problems/create-maximum-number/

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        
        def monotoneDecreasingSequence(nums, size):
            if size <= 0: return []
            
            dropCount = len(nums) - size
            
            result = []
            
            for n in nums:
                while result and result[-1] < n and dropCount > 0:
                    result.pop()
                    dropCount -= 1
                    
                result.append(n)
            
            return result[:size]
    
    
        def merge(n1, n2):
            i = j = 0
            result = []
            while i < len(n1) or j < len(n2):
                if i < len(n1) and j < len(n2):
                    # important! compare the rest numbers in lexical 
                    if n1[i:] > n2[j:]:
                        result.append(n1[i])
                        i += 1
                    else:
                        result.append(n2[j])
                        j += 1
                elif i < len(n1):
                    result.append(n1[i])
                    i += 1
                else:
                    result.append(n2[j])
                    j += 1
            
            return result
        
        result = []
        for i in range(max(0, k - len(nums2)), min(k, len(nums1)) +1):
            mds1 = monotoneDecreasingSequence(nums1, i)
            mds2 = monotoneDecreasingSequence(nums2, k - i)
            merged = merge(mds1, mds2)
            
            result = max(result, merged)
        
        return result