Friedrich Ewald My Personal Website

Posts


  • Leetcode: Kth smallest element in matrix

    Given a n*n matrix, find the kth smallest element. Each row in the matrix is sorted in ascending order and independent of the other rows. Do not use O(n*n) space when solving this. One example matrix looks like this:

      1  5  9
     10 11 13
     12 13 15
    
    For k = 8 return 13 because 13 is the 8th smallest element.
    If we could use all the space we wanted, we could just perform an n-way merge sort on every row at once. This would work because the rows itself are sorted already. Afterwards, we would need to pick the kth element from the list and would be done.

    Continue reading

  • Leetcode: Copy list with random pointer

    Given a head of a list with pointers to next and a random element, copy the list to a new list without any random pointers pointing to the old list.

    # Definition for a Node.
    class Node:
      def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

    Continue reading

  • Leetcode: Decode ways

    Characters can be encoded via different numbers. A -> 1, B -> 2, ..., Z -> 26. Given a string s of numbers, return the number of possible decodings. For example 12 can be decoded as A,B and as L.

    Continue reading

  • Leetcode: Reconstruct binary tree

    Given two lists of a preorder and inorder, create a tree and return the root node.

    preorder: [3,9,20,15,7]
    inorder:  [9,3,15,20,7]
    
    Resulting tree:
    
          3
        /   \
       9    20
           /  \
          15   7
    The problem is not so obvious at first. If the preorder list would also contain null values for the places where the tree does not contain nodes, we could simply iterate over this list and reconstruct the tree from there. But since the null values are missing, we also need to take a look at the inorder list.

    Continue reading

  • Leetcode: Validate Binary Search Tree

    Given the root node of a tree, validate whether it is a valid Binary Search Tree. This is a tree where each node is unique, left children are smaller than the root and right children are greater than the root.

    Continue reading

Page: 4 of 28