Printing a pyramid matrix

How to print a pyramid matrix like that:

n = 2
[1, 1, 1]
[1, 2, 1]
[1, 1, 1]

n = 3
[1, 1, 1, 1]
[1, 2, 2, 1]
[1, 2, 2, 1]
[1, 1, 1, 1]

n = 4
[1, 1, 1, 1, 1]
[1, 2, 2, 2, 1]
[1, 1, 3, 2, 1]
[1, 2, 2, 2, 1]
[1, 1, 1, 1, 1]
def func(N):
    N += 1
    matrix = [[1 for _ in range(N)] for _ in range(N)]
    cnt = 0

    while cnt < N:
        # UP
        for i in range(cnt, N - cnt - 1):
            matrix[cnt][i] = cnt + 1

        # RIGHT
        for i in range(cnt, N - cnt - 1):
            matrix[i][N - cnt - 1] = cnt + 1

        # DOWN
        for i in range(N - cnt - 1, cnt, -1):
            matrix[N - cnt - 1][i] = cnt + 1

        # LEFT
        for i in range(N - cnt, cnt, -1):
            matrix[N - cnt - 1][cnt] = cnt + 1

        cnt += 1

    return matrix


if __name__ == "__main__":
    matrix = func(N=4)

    for line in matrix:
        print(line)

Path In Zigzag Labelled Binary Tree

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]
from math import log

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        ans = [label]
        
        def findParent(label):
            level =  math.floor(math.log(label,2))            
            diff = math.ceil((label - 2**level + 1) / 2)       
            parent = 2**(level) - diff
            return parent
            
        while label != 1:
            label = findParent(label)
            ans.append(label)
            
        return ans[::-1]

Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.









Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.
class Solution:
    def removeDuplicates(self, nums: List[int]):
        if not nums:
            return 0

        newTail = 0

        for i in range(1, len(nums)):
            if nums[i] != nums[newTail]:
                newTail += 1
                nums[newTail] = nums[i]

        return newTail + 1

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.result = []

        def perm(data, begin, end):
            if begin == end:
                self.result += [[item for item in data]]
            else:
                i = begin
                for j in range(begin, end):
                    data[i], data[j] = data[j], data[i]
                    perm(data, begin + 1, end)
                    data[i], data[j] = data[j], data[i]
                    
        perm(nums, 0, len(nums))

        return self.result

Permutation Sequence

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"
class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        res, nums = "", list(range(1, n + 1))

        k -= 1

        for n in range(n, 0, -1):
            index, k = divmod(k, math.factorial(n-1))
            res += str(nums.pop(index))

        return res

Lowest Common Ancestor with N nodes

Similar with finding lowest common ancestor of two nodes, we can extend this function to N nodes.

The method buildTree in the solution is in order to building a tree instantly by given strings.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, inorder, postorder):
        if not inorder or not postorder:
            return None

        while postorder:
            if postorder[-1] not in inorder:
                postorder.pop()
            else:
                break

        if len(postorder) == 1:
            return TreeNode(postorder[0])

        else:
            node = TreeNode(postorder[-1])
            in_index = inorder.index(postorder[-1])
            node.left = self.buildTree(inorder[:in_index], postorder[:-1])
            node.right = self.buildTree(inorder[in_index + 1:], postorder[:-1])
            return node

    def find(self, root, nodes):
        if not root:
            return None
        else:
            if root.val in nodes:
                return root

            left = self.find(root.left, nodes)
            right = self.find(root.right, nodes)

            if left and right:
                return root

            return right if not left else left


if __name__ == "__main__":
    obj = Solution()
    root = obj.buildTree([6, 5, 7, 2, 4, 3, 0, 1, 8], [6, 7, 4, 2, 5, 0, 8, 1, 3])
    nodes = [0, 1, 8]
    result = obj.find(root, nodes)
    print(result.val)

House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: [3,2,3,null,3,null,1]      
3
/ \
2 3
\ \
3 1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: [3,4,5,1,3,null,1]      
3
/ \
4 5
/ \ \
1 3 1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        def superrob(node):
            # returns tuple of size two (now, later)
            # now: max money earned if input node is robbed
            # later: max money earned if input node is not robbed
            
            # base case
            if not node: return (0, 0)
            
            # get values
            left, right = superrob(node.left), superrob(node.right)
            
            # rob now
            now = node.val + left[1] + right[1]
            
            # rob later
            later = max(left) + max(right)
            
            return (now, later)
            
        return max(superrob(root))

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Continue reading

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Continue reading