Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1 Input: [2,2,1] Output: 1 Example 2 Input: [4,1,2,1,2] Output: 4 Solution // Java class Solution { public int singleNumber(int[] nums) { int result=0; for(int num : nums) { result=result^num; } return result; } } Solution class Solution: def singleNumber(self, nums: List[int]) -> int: singleNum = nums[0] for i in range(1, len(nums)): singleNum ^= nums[i] return singleNum

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

Find Peak Element

A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that nums[-1] = nums[n] = -∞. Example 1 Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.

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

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