Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. You may assume no duplicate exists in the array. Example 1 Input: [3,4,5,1,2] Output: 1 Example 2 Input: [4,5,6,7,0,1,2] Output: 0 Solution class Solution: def findMin(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) == 1: return nums[0] if len(nums) == 2: return min(nums[0], nums[1]) if nums[0] < nums[len(nums)-1]: return nums[0] if nums[len(nums)-2] > nums[len(nums)-1]: return nums[len(nums)-1] for i in range(1, len(nums)-1): if nums[i] < nums[i-1] and nums[i] < nums[i+1]: return nums[i] def bsFindMin(self, nums): l, r = 0, len(nums) - 1 while l < r: m = (l + r) // 2 if nums[m] > nums[m - 1] and nums[m] > nums[m + 1]: return nums[m + 1] if nums[m] < nums[m - 1] and nums[m] < nums[m + 1]: return nums[m] if nums[m] >= nums[r]: l = m else: r = m return nums[0]

by lek tin in "algorithm" access_time 1-min read

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function. Solution # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.

by lek tin in "algorithm" access_time 1-min read

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 Solution # Definition for a binary tree node.

by lek tin in "algorithm" access_time 1-min read

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Example Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.

by lek tin in "algorithm" access_time 2-min read

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,2,3] Follow-up Recursive solution is trivial, could you do it iteratively? Solution # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def preorderTraversal_1(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] return [root.

by lek tin in "algorithm" access_time 1-min read

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values. Example Input: [1,null,2,3] 1 \ 2 / 3 Output: [3,2,1] Follow-up Recursive solution is trivial, could you do it iteratively? Solution Recursive👇 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ def traverse(node): if node == None: return [] return traverse(node.

by lek tin in "algorithm" access_time 1-min read

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths. Note: A leaf is a node with no children. Example Input: 1 / \ 2 3 \ 5 Output: ["1->2->5", "1->3"] Explanation: All root-to-leaf paths are: 1->2->5, 1->3 Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ res = [] def traverse(root, path): if root == None: return path += str(root.

by lek tin in "algorithm" access_time 1-min read

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). Example Given binary tree `[3,9,20,null,null,15,7]`, 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] Solution (recursion) # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.

by lek tin in "algorithm" access_time 1-min read

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ] Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.

by lek tin in "algorithm" access_time 1-min read

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Note: All numbers will be positive integers. The solution set must not contain duplicate combinations. Example 1 Input: k = 3, n = 7 Output: [[1,2,4]] Example 2 Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] Solution class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: # Equivalent to subsets results = [] combination = [] # Start DFS self.

by lek tin in "algorithm" access_time 1-min read