[LeetCode] 25. Reverse Nodes in k-Group

Problem : https://leetcode.com/problems/reverse-nodes-in-k-group/

This problem needs to be solved by 2 nested recursion. The outer recursion locates the groups of k nodes. The inner recursion reverse the located group.

Time Complexity :  O ( N )

Space Complexity : O ( 1 ) 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        
        # find the first k nodes
        i = 0
        p = head
        
        while i < k and p:
            p = p.next
            i += 1
        
        # return the original list if it has less nodes than k
        if i < k:
            return head
        
        # reverse the first k nodes
        pre = None
        cur = head
               
        while cur != p:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        
        # append to the rest reversed groups
        head.next = self.reverseKGroup(p, k)
    
        return pre

Updated on 07/18/2021. Update for a simpler recursive solution.

[LeetCode] 24. Swap Nodes in Pairs

Problem : https://leetcode.com/problems/swap-nodes-in-pairs/

Swap nodes in pairs recursively.

Time Complexity : O ( N ) ,  N = length of list

Space Complexity: O ( 1 ),  swap in space.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if head and head.next:
            tmp = head.next.next
        
            left, right = head, head.next
            
            right.next = left
            left.next = self.swapPairs(tmp)
            
            return right
        
        return head

[LeetCode] 23. Merge k Sorted Lists

Problem : https://leetcode.com/problems/merge-k-sorted-lists/

Must divide and conquer approach to avoid exceeding time limit. 

Time Complexity = O( N log(len(lists) )

Space Complexity: O(1)

 
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
    
        def merge(l1, l2):
            if l1 and l2:
                if l1.val < l2.val:
                    l1.next = merge(l1.next, l2)
                    return l1
                else:
                    l2.next = merge(l1, l2.next)
                    return l2
                
            return l1 if l1 else l2
        
        
        def helper(left, right):
            if left == right:
                return None
            
            if right - left == 1:
                return lists[left]
            
            if right - left == 2:
                return merge(lists[left], lists[left+1])
            
            
            mid = left + (right - left) // 2
            return merge(helper(left, mid), helper(mid, right))
    
            
        return helper(0, len(lists))

Use priority queue to merge K sorted list. N = max length of lists

Time Compleixty = O(N * Log K)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) pq.offer(head);
        }
        
        while (!pq.isEmpty()) {
            p.next = pq.poll();
            p = p.next;
            if (p.next != null) pq.offer(p.next);
        }

        return dummy.next;
    }
}

[LeetCode] 22. Generate Parentheses

Problem : https://leetcode.com/problems/generate-parentheses/

Recursively add open bracket and close bracket for valid sequence.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def helper(left, right, tmp):
            if left == right == n:
                yield "".join(tmp)
            else:
                if left < n:
                    tmp.append("(")
                    yield from helper(left + 1, right, tmp)
                    tmp.pop()
                
                if left > right:
                    tmp.append(")")
                    yield from helper(left, right + 1, tmp)
                    tmp.pop()
        
        return list(helper(0, 0, []))

Edited on 06/16/2021. Refactor by using 'yield'.

[LeetCode] 21. Merge Two Sorted Lists

Problem : https://leetcode.com/problems/merge-two-sorted-lists/

It is intuitive to create a dummy head then iteratively merge the 2 given sorted lists. 

[LeetCode] 20. Valid Parentheses

Problem : https://leetcode.com/problems/valid-parentheses/

Use stack to check if the close parenthesis match with the open parenthesis.

Time complexity: O( len(s) )

Space complexity: O( len(s) )

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> pairs = new HashMap<>() {
            {
                put('(', ')');
                put('[', ']');
                put('{', '}');
            }
        };
        
        for (char a : s.toCharArray()) {
            if (pairs.containsKey(a)) {
                stack.push(a);
            } else {
                if (stack.isEmpty() || pairs.get(stack.pop()) != a) return false;
            }
        }
        
        return stack.isEmpty();
    }
}

Edited on 03/12/2022. Use map to pair brackets.

[LeetCode] 19. Remove Nth Node From End of List

Problem : https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Use 2 pointers to iterate the linked list. The second pointer is n steps behind the first pointer.

Time Complexity :  O ( N )

Space Complexity : O ( 1 )

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        
        # use dummy head node to handle the case that needs to remove the first node.
        dummy = ListNode(0)
        dummy.next = head
        
        p1, p2 = dummy, dummy
        
        while p2 and n >= 0:
            p2 = p2.next
            n -= 1
            
        while p2 and p1:
            p2 = p2.next
            p1 = p1.next
            
        if p1 and p1.next:
            p1.next = p1.next.next
    
        
        return dummy.next

[LeetCode] 18. 4Sum

Problem : https://leetcode.com/problems/4sum/

Similar to 3Sum.

Time Complexity : O ( len(nums) *len(nums) * len(nums)/2 )

Space Complexity: O (len(nums)*len(nums)*len(nums)*len(nums))

 
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        nums.sort()
        L = len(nums)
        
        result = []
        
        for i in range(L-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            for j in range(i+1, L-2):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                    
                left, right = j + 1, L - 1
                
                while left < right:
                    # early termination
                    if nums[i] + nums[j] + nums[left] + nums[left] > target:
                        break
                        
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if tmp < target:
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                    elif tmp > target:
                         l = right - 1
                         while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                         right = l
                    else:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                        
                        l = right - 1
                        while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                        right = l
                        
        return result

[LeetCode] 17. Letter Combinations of a Phone Number

Problem : https://leetcode.com/problems/letter-combinations-of-a-phone-number/

This is a typical backtracking problem. Consider the code travels a tree. Each digit is represented as a node of this tree. Each node has the rest digits as its child node. On each node, the code has number N of letter to pick up. So the code does DFS on this tree to find all of the combination.

To simplify the calculation, consider each digits has 3 letters.

Time Complexity :  O ( 3 ** len(s) )

Space Complexity:  O ( 3 ** len(s) )

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
        
        result = []
        
        def backtrack(i, tmp):
            if i == len(digits):
                if tmp:
                    result.append(tmp)
                return
                
            for t in letters[digits[i]]:
                backtrack(i+1, tmp + t)
        
        backtrack(0, "")
        
        return result

BFS based solution:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
        
        if not digits: return []
                
        result = []
        
        queue = deque([[l, 1] for l in letters[digits[0]]])
     
        while queue:
            for _ in range(len(queue)):
                w , index = queue.popleft()
                
                if index == len(digits):
                    result.append(w)
                else:
                    for l in letters[digits[index]]:
                        queue.append([w + l, index + 1])
        
        return result

An iterative solution. Start from the last digit to the first digit, add letter of current digit to the front of last letter combinations.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        
        letters = {'2': 'abc', '3': 'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz' }
              
        ds = [d for d in digits]
        
        result = [[l] for l in letters[ds.pop()]]
        
        while ds:
            suffix = result[:]
            result = []
            
            for l in letters[ds.pop()]:
                for s in suffix:
                    result.append([l] + s)
            
        return [''.join(t) for t in result]

Edited 04/24/2021. Add the iterative solution.

[LeetCode] 16. 3Sum Closest

Problem : https://leetcode.com/problems/3sum-closest/

Use the same two pointers approach as the 3Sum quiz.

Time Complexity :  O ( N * LogN + N ** 2 )

Space Complexity: O ( log N ) or O ( N ), depending on the sort algorithm. 

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        
        nums.sort()
        N = len(nums)
        
        result = nums[0] + nums[1] + nums[2] # assume the init value of result
        
        for i in range(N-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            left, right = i + 1, N-1
                        
            while left < right:
                tmp = sum([nums[i], nums[left], nums[right]])
                
                if abs(result - target) > abs(tmp - target):
                    result = tmp
                
                if tmp == target:
                    return target
                
                if tmp < target:
                    j = left + 1
                    while j < right and nums[j] == nums[left]:
                        j += 1
                    left = j
                else:
                    k = right - 1
                    while k > left and nums[k] == nums[right]:
                        k -= 1
                    right = k
                    
        return result

Edited of 07/27/2021. Update result variable's init value.