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

Two Sum II Input Array Is Sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note Your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.

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

Super Useful Bash Commands

List all services sudo service --status-all Create a nested directory if it doesn’t exist already. mkdir -p /nested/directory To list detailed information about all items (visible and invisible) in the current directory (the -a option is to show all files, the -l option is to show details) ls -al To list the contents of your Documents folder and all sub folders (this may take a while if you have a large Documents folder)

by lek tin in "linux" access_time 3-min read

Copy List With Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Solution Solution 1: Insert cloned nodes in between original nodes then connect the cloned nodes # Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.

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