Construct Binary Tree From Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree. Note You may assume that duplicates do not exist in the tree. For example, given: preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 Hint Solution: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(0, 0, inorder.

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

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome. Example 1 Input: 1->2 Output: false Example 2 Input: 1->2->2->1 Output: true Follow up: Could you do it in O(n) time and O(1) space? Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head: ListNode) -> bool: if not head: return True middle = self.

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

3sum With Multiplicity

Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < k and A[i] + A[j] + A[k] == target. As the answer can be very large, return it modulo 10^9 + 7. Example 1 Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8 Output: 20 Explanation: Enumerating by the values (A[i], A[j], A[k]): (1, 2, 5) occurs 8 times; (1, 3, 4) occurs 8 times; (2, 2, 4) occurs 2 times; (2, 3, 3) occurs 2 times.

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

3sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target. Example: Input: nums = [-2,0,1,3], and target = 2 Output: 2 Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3] Solution class Solution: def threeSumSmaller(self, nums: List[int], target: int) -> int: res = 0 if not nums: return res nums.

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

Two Sum Less Than K

Given an array A of integers and integer K, return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K. If no i, j exist satisfying this equation, return -1. Example 1 Input: A = [34,23,1,24,75,33,54,8], K = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60. Example 2 Input: A = [10,20,30], K = 15 Output: -1 Explanation: In this case it's not possible to get a pair sum less that 15.

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

Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node p is the node with the smallest key greater than p.val. Example 1 Input: root = [2,1,3], p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type. Example 2 Input: root = [5,3,6,2,4,null,null,1], p = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null.

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

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow-up the Recursive solution is trivial, could you do it iteratively? 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 inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ """Check root == None to reduce time on checking""" if root == None: return [] stack = [] result = [] current = root while (current!

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

Two Sum Iii Data Structure Design Design

Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value. Example 1 add(1); add(3); add(5); find(4) -> true find(7) -> false Example 2 add(3); add(1); add(2); find(3) -> true find(6) -> false Solution # Time: add is o(1), find is o(n) # Space: `O(n)` class TwoSum: def __init__(self): """ Initialize your data structure here.

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

Two Sum Iv Input Is a Bst

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1 Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True Example 2 Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False Solution # time: `O(n)` # space: `O(n)` # Definition for a binary tree node.

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

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. Solution # time: `O(n)` # space: `O(n)` class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ res = [-1, -1] if nums == None or len(nums) < 2: return res solutionMap = {} for pos in range(len(nums) - 1): if (target - nums[pos]) in solutionMap: res[0] = solutionMap[target - nums[pos]] res[1] = pos break solutionMap[nums[pos]] = pos return res # time: o(nlogn) # space: o(1) class Pair: def __init__(self, index, val): self.

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