


Longest Continuous Increasing Subsequence – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Longest Continuous Increasing Subsequence - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { public int findLengthOfLCIS(int[] nums) { if (nums.length == 0) return 0; int curr = 1, ans = 1; for (int i = 0; i < nums.length - 1; i++) { if (nums[i] < nums[i + 1]) { curr ++; if (curr >= ans) ans = curr; } else { curr = 1; } } return ans; } }

Convert BST to Greater Tree – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Convert BST to Greater Tree - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # https://leetcode.com/problems/convert-bst-to-greater-tree/solution/ # def __init__(self): # self.total = 0 # def convertBST(self, root): # if root is not None: # self.convertBST(root.right) # self.total += root.val # root.val = self.total # self.convertBST(root.left) # return root def convertBST(self, root): total = 0 node = root stack = [] while stack or node is not None: # push all nodes up to (and including) this subtree's maximum on # the stack. while node is not None: stack.append(node) node = node.right node = stack.pop() total += node.val node.val = total # all nodes with values between the current and its parent lie in # the left subtree. node = node.left return root

N-Repeated Element in Size 2N Array – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - N-Repeated Element in Size 2N Array - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { public int repeatedNTimes(int[] A) { HashMaphash = new HashMap<>(); int ans = A[0]; for (int n: A) { int count = hash.getOrDefault(n, 0) + 1; hash.put(n, count); if (count >= hash.get(ans)) ans = n; } return ans; } }

Add Strings – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Add Strings - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def addStrings(self, num1, num2): # """ # :type num1: str # :type num2: str # :rtype: str # """ # if num1 is None: # num1 = '0' # if num2 is None: # num2 = '0' # res = [] # carry = 0 # ls = min(len(num1), len(num2)) # pos = -1 # while pos + ls >= 0: # curr = int(num1[pos]) + int(num2[pos]) + carry # res.insert(0, str(curr % 10)) # carry = curr / 10 # pos -= 1 # while pos + len(num1) >= 0: # curr = int(num1[pos]) + carry # res.insert(0, str(curr % 10)) # carry = curr / 10 # pos -= 1 # while pos + len(num2) >= 0: # curr = int(num2[pos]) + carry # res.insert(0, str(curr % 10)) # carry = curr / 10 # pos -= 1 # if carry != 0: # res.insert(0, str(carry)) # return ''.join(res) def addStrings(self, num1, num2): res = [] pos1 = len(num1) - 1 pos2 = len(num2) - 1 carry = 0 # This conditon is great # https://leetcode.com/problems/add-strings/discuss/90436/Straightforward-Java-8-main-lines-25ms while pos1 >= 0 or pos2 >= 0 or carry == 1: digit1 = digit2 = 0 if pos1 >= 0: digit1 = ord(num1[pos1]) - ord('0') if pos2 >= 0: digit2 = ord(num2[pos2]) - ord('0') res.append(str((digit1 + digit2 + carry) % 10)) carry = (digit1 + digit2 + carry) / 10 pos1 -= 1 pos2 -= 1 # reverse res return ''.join(res[::-1])

Friend Circles – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Friend Circles - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def findCircleNum(self, M): """ :type M: List[List[int]] :rtype: int """ # because visited = [0] * len(M) count = 0 for i in range(len(M)): if visited[i] == 0: self.dfs(M, visited, i) count += 1 return count def dfs(self, M, visited, i): for j in range(len(M)): if M[i][j] == 1 and visited[j] == 0: visited[j] = 1 self.dfs(M, visited, j) # def findCircleNum(self, M): # # BFS # visited = [0] * len(M) # count = 0 # queue = [] # for i in range(len(M)): # if visited[i] == 0: # queue.append(i) # while queue: # curr = queue.pop(0) # visited[curr] = 1 # for j in range(len(M)): # if M[curr][j] == 1 and visited[j] == 0: # queue.append(j) # count += 1 # return count # def findCircleNum(self, M): # # Union Find # union = Union() # for i in range(len(M)): # union.add(i) # for i in range(len(M)): # for j in range(i + 1, len(M)): # if M[i][j] == 1: # union.union(i, j) # return union.count # class Union(object): # """ # weighted quick union find # """ # def __init__(self): # # both dic and list is fine # self.id = {} # self.sz = {} # self.count = 0 # def count(self): # return self.count # def connected(self, p, q): # return self.find(p) == self.find(q) # def add(self, p): # # init # self.id[p] = p # self.sz[p] = 1 # self.count += 1 # def find(self, p): # """ # find root of p, and compress path # """ # while p != self.id[p]: # self.id[p] = self.id[self.id[p]] # p = self.id[p] # return p # def union(self, p, q): # """ # connect p and q # """ # i, j = self.find(p), self.find(q) # if i == j: # return # if self.sz[i] > self.sz[j]: # i, j = j, i # self.id[i] = j # self.sz[j] += self.sz[i] # self.count -= 1

Maximum Product of Three Numbers – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Maximum Product of Three Numbers - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def maximumProduct(self, nums): # """ # :type nums: List[int] # :rtype: int # """ # nums.sort() # # Check min1*min2*max1 and max1*max2*max3 # return max(reduce(lambda x, y: x * y, nums[:2]) * nums[-1], # reduce(lambda x, y: x * y, nums[-3:])) def maximumProduct(self, nums): min1 = min2 = float('inf') max1 = max2 = max3 = float('-inf') for num in nums: if num <= min1: min2 = min1 min1 = num elif num <= min2: min2 = num if num >= max1: max3 = max2 max2 = max1 max1 = num elif num >= max2: max3 = max2 max2 = num elif num >= max3: max3 = num return max(min1 * min2 * max1, max1 * max2 * max3)

Find All Anagrams in a String – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find All Anagrams in a String - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """ res = [] if s is None or p is None or len(s) == 0 or len(p) == 0: return res char_map = [0] * 256 for c in p: char_map[ord(c)] += 1 left, right, count = 0, 0, len(p) while right < len(s): if char_map[ord(s[right])] >= 1: count -= 1 char_map[ord(s[right])] -= 1 right += 1 if count == 0: res.append(left) if right - left == len(p): if char_map[ord(s[left])] >= 0: count += 1 char_map[ord(s[left])] += 1 left += 1 return res # def findAnagrams(self, s, p): # if len(s) < len(p): # return [] # res = [] # p_len = len(p) # bit_map = [] # for _ in range(26): # bit_map.append(0) # for c in p: # bit_map[ord(c) - ord('a')] += 1 # s_p = str(bit_map) # for i in range(26): # bit_map[i] = 0 # for i in range(p_len - 1): # bit_map[ord(s[i]) - ord('a')] += 1 # for i in range(p_len - 1, len(s)): # bit_map[ord(s[i]) - ord('a')] += 1 # if i - p_len >= 0: # bit_map[ord(s[i - p_len]) - ord('a')] -= 1 # if str(bit_map) == s_p: # res.append(i - p_len + 1) # return res # def findAnagrams(self, s, p): # """ # :type s: str # :type p: str # :rtype: List[int] # """ # res = [] # pCounter = collections.Counter(p) # sCounter = collections.Counter(s[:len(p)-1]) # for i in range(len(p)-1,len(s)): # sCounter[s[i]] += 1 # include a new char in the char_map # if sCounter == pCounter: # This step is O(1), since there are at most 26 English letters # res.append(i-len(p)+1) # append the starting index # sCounter[s[i-len(p)+1]] -= 1 # decrease the count of oldest char in the window # if sCounter[s[i-len(p)+1]] == 0: # del sCounter[s[i-len(p)+1]] # remove the count if it is 0 # return res

Find Pivot Index – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find Pivot Index - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def pivotIndex(self, nums): """ :type nums: List[int] :rtype: int """ totalsum = sum(nums) leftsum = 0 for i, v in enumerate(nums): # leftsum == rightsum if leftsum == totalsum - leftsum - v: return i leftsum += v return -1

Reorder Log Files – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Reorder Log Files - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import java.util.List; class Solution { public String[] reorderLogFiles(String[] logs) { Arrays.sort(logs, (log1, log2) -> { String[] split1 = log1.split(" ", 2); String[] split2 = log2.split(" ", 2); boolean isDigit1 = Character.isDigit(split1[1].charAt(0)); boolean isDigit2 = Character.isDigit(split2[1].charAt(0)); if (!isDigit1 && !isDigit2) { int cmp = split1[1].compareTo(split2[1]); if (cmp != 0) return cmp; return split1[0].compareTo(split2[0]); } return isDigit1 ? (isDigit2 ? 0 : 1) : -1; }); return logs; } }

K Closest Points to Origin – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - K Closest Points to Origin - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def kClosest(self, points, K): # """ # :type points: List[List[int]] # :type K: int # :rtype: List[List[int]] # """ # # Sort # return sorted(points, key=lambda x: x[0] ** 2 + x[1] ** 2)[:K] def kClosest(self, points, K): # K smallest heaq return heapq.nsmallest(K, points, key=lambda x: x[0] ** 2 + x[1] ** 2)

Transpose Matrix – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Transpose Matrix - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def transpose(self, A): """ :type A: List[List[int]] :rtype: List[List[int]] """ R, C = len(A), len(A[0]) ans = [[None] * R for _ in xrange(C)] for r, row in enumerate(A): for c, val in enumerate(row): ans[c][r] = val return ans # Alternative Solution: # return zip(*A) # def transpose(self, A): # res = [] # for i in range(len(A[0])): # temp = [] # for j in range(len(A)): # temp.append(A[j][i]) # res.append(temp) # return res

Fibonacci Number – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Fibonacci Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { /*public int fib(int N) { // Recursively, O(n) if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N - 2); }*/ private Listmemo; public Solution() { memo = new ArrayList(); memo.add(0); memo.add(1); } public int fib(int N) { // Dp with memo, O(n) if (N < memo.size()) return memo.get(N); for (int i = memo.size(); i <= N; i++) { memo.add(memo.get(i - 1) + memo.get(i - 2)); } return memo.get(N); } }

Path Sum III – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Path Sum III - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None # https://leetcode.com/problems/path-sum-iii/discuss/91892/Python-solution-with-detailed-explanation class Solution(object): # def find_paths(self, root, target): # if root: # return int(root.val == target) # + self.find_paths(root.left, target - root.val) # + self.find_paths(root.right, target - root.val) # return 0 # def pathSum(self, root, sum): # """ # :type root: TreeNode # :type sum: int # :rtype: int # """ # if root: # return self.find_paths(root, sum) # + self.pathSum(root.left, sum) # + self.pathSum(root.right, sum) # return 0 def pathSumHelper(self, root, target, so_far, cache): if root: # complement == 1, root->curr path complement = so_far + root.val - target if complement in cache: # S->E path, sum(root->S)-sum(root->E) = target self.result += cache[complement] cache[so_far + root.val] = cache.get(so_far + root.val, 0) + 1 self.pathSumHelper(root.left, target, so_far + root.val, cache) self.pathSumHelper(root.right, target, so_far + root.val, cache) cache[so_far + root.val] -= 1 return def pathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: int """ self.result = 0 self.pathSumHelper(root, sum, 0, {0: 1}) return self.result

Longest Substring with At Most K Distinct Characters – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Longest Substring with At Most K Distinct Characters - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def lengthOfLongestSubstringKDistinct(self, s, k): """ :type s: str :type k: int :rtype: int """ count = [0] * 256 i, numDistinct, maxLen = 0, 0, 0 for j in range(len(s)): # udpate j if count[ord(s[j])] == 0: numDistinct += 1 count[ord(s[j])] += 1 # udpate i while numDistinct > k: count[ord(s[i])] -= 1 if count[ord(s[i])] == 0: numDistinct -= 1 i += 1 maxLen = max(j - i + 1, maxLen) return maxLen

Diameter of Binary Tree – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Diameter of Binary Tree - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { // https://leetcode.com/problems/diameter-of-binary-tree/solution/ int ans; public int diameterOfBinaryTree(TreeNode root) { ans = 1; depth(root); return ans - 1; } public int depth(TreeNode node) { if (node == null) return 0; int L = depth(node.left); int R = depth(node.right); ans = Math.max(ans, L+R+1); return Math.max(L, R) + 1; } }

Convert a Number to Hexadecimal – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Convert a Number to Hexadecimal - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def toHex(self, num): """ :type num: int :rtype: str """ if num == 0: return '0' # letter map mp = '0123456789abcdef' ans = '' for _ in range(8): # get last 4 digits # num & 1111b n = num & 15 # hex letter for current 1111 c = mp[n] ans = c + ans # num = num / 16 num = num >> 4 #strip leading zeroes return ans.lstrip('0') # def toHex(self, num): # def tohex(val, nbits): # return hex((val + (1 << nbits)) % (1 << nbits)) # return tohex(num, 32)[2:] # def toHex(self, num, h=''): # return (not num or h[7:]) and h or self.toHex(num / 16, '0123456789abcdef'[num % 16] + h)

Unique Email Addresses – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Unique Email Addresses - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def numUniqueEmails(self, emails): """ :type emails: List[str] :rtype: int """ email_set = set() for email in emails: elements = email.split('@') email_set.add(elements[0].split('+')[0].replace('.', '') + elements[1]) return len(email_set)

Evaluate Reverse Polish Notation – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Evaluate Reverse Polish Notation - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def evalRPN(self, tokens): """ :type tokens: List[str] :rtype: int """ stack = [] for t in tokens: try: temp = int(t) stack.append(temp) except: b = stack.pop() a = stack.pop() if t == "+": a += b elif t == "-": a -= b elif t == "*": a *= b else: a = int(a * 1.0 / b) stack.append(a) return stack[-1]

Maximum 69 Number – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Maximum 69 Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { public int maximum69Number (int num) { // Replace first 6 with 9 if exists return Integer.valueOf(String.valueOf(num).replaceFirst("6", "9")); } /* public int maximum69Number (int num) { char[] chars = Integer.toString(num).toCharArray(); // Replace first 6 with 9 if exists for (int i = 0; i < chars.length; i++) { if (chars[i] == '6') { chars[i] = '9'; break; } } return Integer.parseInt(new String(chars)); }*/ }

Top K Frequent Words – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Top K Frequent Words - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def topKFrequent(self, words, k): # """ # :type words: List[str] # :type k: int # :rtype: List[str] # """ # counter = collections.Counter(words) # res = sorted(counter.items(), cmp=cmp_frequency, reverse=True) # return [k for k, _ in res[:k]] # def cmp_frequency(x, y): # if x[1] != y[1]: # return cmp(x[1], y[1]) # return cmp(y[0], x[0]) # def topKFrequent(self, words, k): # count = collections.Counter(words) # candidates = count.keys() # candidates.sort(key = lambda w: (-count[w], w)) # return candidates[:k] def topKFrequent(self, words, k): count = collections.Counter(words) # Note that python heapq only support min heap # So, we can make the value negative to create a max heap heap = [(-freq, word) for word, freq in count.items()] heapq.heapify(heap) return [heapq.heappop(heap)[1] for _ in xrange(k)]

Edit Distance – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Edit Distance - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # https://discuss.leetcode.com/topic/17639/20ms-detailed-explained-c-solutions-o-n-space/2 # def minDistance(self, word1, word2): # """ # :type word1: str # :type word2: str # :rtype: int # """ # ls_1, ls_2 = len(word1), len(word2) # dp = [[0] * (ls_2 + 1) for _ in range(ls_1 + 1)] # for i in range(1, ls_1 + 1): # dp[i][0] = i # for j in range(1, ls_2 + 1): # dp[0][j] = j # for i in range(1, ls_1 + 1): # for j in range(1, ls_2 + 1): # if word1[i - 1] == word2[j - 1]: # dp[i][j] = dp[i - 1][j - 1] # else: # dp[i][j] = min(dp[i - 1][j - 1] + 1, # dp[i][j - 1] + 1, # dp[i - 1][j] + 1) # return dp[ls_1][ls_2] def minDistance(self, word1, word2): ls_1, ls_2 = len(word1), len(word2) dp = list(range(ls_1 + 1)) for j in range(1, ls_2 + 1): pre = dp[0] dp[0] = j for i in range(1, ls_1 + 1): temp = dp[i] if word1[i - 1] == word2[j - 1]: dp[i] = pre else: dp[i] = min(pre + 1, dp[i] + 1, dp[i - 1] + 1) pre = temp return dp[ls_1] if __name__ == '__main__': # begin s = Solution() print (s.minDistance("horse","ros")) print (s.minDistance("intention","execution"))

Logger Rate Limiter – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Logger Rate Limiter - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# class Logger(object): # def __init__(self): # """ # Initialize your data structure here. # """ # self.timestamps = {} # def shouldPrintMessage(self, timestamp, message): # """ # Returns true if the message should be printed in the given timestamp, otherwise returns false. # If this method returns false, the message will not be printed. # The timestamp is in seconds granularity. # :type timestamp: int # :type message: str # :rtype: bool # """ # if timestamp < self.timestamps.get(message, 0): # return False # self.timestamps[message] = timestamp + 10 # return True import heapq class Logger(object): def __init__(self): """ Initialize your data structure here. """ self.heap = [] self.cache = {} def shouldPrintMessage(self, timestamp, message): """ Returns true if the message should be printed in the given timestamp, otherwise returns false. If this method returns false, the message will not be printed. The timestamp is in seconds granularity. :type timestamp: int :type message: str :rtype: bool """ while len(self.heap): if self.heap[0][0] <= timestamp: temp = heapq.heappop(self.heap) self.cache.pop(temp[1]) else: break if timestamp < self.cache.get(message, 0): return False self.cache[message] = timestamp + 10 heapq.heappush(self.heap, (timestamp + 10, message)) return True # Your Logger object will be instantiated and called as such: # obj = Logger() # param_1 = obj.shouldPrintMessage(timestamp,message)

Longest Consecutive Sequence – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Longest Consecutive Sequence - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def longestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ def longestConsecutive(self, num): # Pop adjacency O(n) and O(n) num = set(num) maxLen = 0 while num: n = num.pop() i = n + 1 l1 = 0 l2 = 0 while i in num: num.remove(i) i += 1 l1 += 1 i = n - 1 while i in num: num.remove(i) i -= 1 l2 += 1 maxLen = max(maxLen, l1 + l2 + 1) return maxLen

Convert Sorted Array to Binary Search Tree – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Convert Sorted Array to Binary Search Tree - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# 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 sortedArrayToBST(self, nums): # """ # :type nums: List[int] # :rtype: TreeNode # """ # # Recursion with slicing # if not nums: # return None # mid = len(nums) / 2 # root = TreeNode(nums[mid]) # root.left = self.sortedArrayToBST(nums[:mid]) # root.right = self.sortedArrayToBST(nums[mid + 1:]) # return root def sortedArrayToBST(self, nums): # Recursion with index return self.getHelper(nums, 0, len(nums) - 1) def getHelper(self, nums, start, end): if start > end: return None mid = (start + end) / 2 node = TreeNode(nums[mid]) node.left = self.getHelper(nums, start, mid - 1) node.right = self.getHelper(nums, mid + 1, end) return node

Two Sum II – Input array is sorted – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Two Sum II - Input array is sorted - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ # Two Points begin, end = 0, len(numbers) - 1 while begin < end: curr = numbers[begin] + numbers[end] if curr == target: return [begin + 1, end + 1] elif curr < target: begin += 1 else: end -= 1

Reverse Words in a String III – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Reverse Words in a String III - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution { public String reverseWords(String s) { String words[] = s.split(" "); StringBuilder ans = new StringBuilder(); for (String word: words) ans.append(new StringBuffer(word).reverse().toString() + " "); return ans.toString().trim(); } }

Find All Numbers Disappeared in an Array – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find All Numbers Disappeared in an Array - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ # https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/92956/Java-accepted-simple-solution res = [] if nums: n = len(nums) for i in range(n): val = abs(nums[i]) - 1 if nums[val] > 0: nums[val] = -nums[val] for i in range(n): if nums[i] > 0: res.append(i + 1) return res

Backspace String Compare – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Backspace String Compare - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { /*public boolean backspaceCompare(String S, String T) { // https://leetcode.com/problems/backspace-string-compare/discuss/135603/C%2B%2BJavaPython-O(N)-time-and-O(1)-space int i = S.length() - 1, j = T.length() - 1; while (true) { for (int back = 0; i >= 0 && (back > 0 || S.charAt(i) == '#'); --i) back += S.charAt(i) == '#' ? 1 : -1; for (int back = 0; j >= 0 && (back > 0 || T.charAt(j) == '#'); --j) back += T.charAt(j) == '#' ? 1 : -1; if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) { i--; j--; } else return i == -1 && j == -1; } }*/ public boolean backspaceCompare(String S, String T) { return trans(S).equals(trans(T)); } private String trans(String str) { StringBuilder sb = new StringBuilder(); for (char c : str.toCharArray()) { if (c != '#') { sb.append(c); } // if not '#', append it at the end of sb. else if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } // remove last char in sb, if sb is not empty. } return sb.toString(); } }

Count Primes – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Count Primes - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ # https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity isPrime = [True] * n for i in xrange(2, n): if i * i >= n: break if not isPrime[i]: continue for j in xrange(i * i, n, i): isPrime[j] = False count = 0 for i in xrange(2, n): if isPrime[i]: count += 1 return count

Search Insert Position – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Search Insert Position - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution: # def searchInsert(self, nums, target): # """ # :type nums: List[int] # :type target: int # :rtype: int # """ # min, pos = 0, 0 # max = len(nums) - 1 # while min <= max: # # binary search # pos = (max + min) / 2 # if nums[pos] == target: # return pos # elif nums[pos] > target: # max = pos - 1 # else: # min = pos + 1 # if min > pos: # # this means that target is great than pos, and target # # is not in nums # return pos + 1 # return pos def searchInsert(self, nums, target): l, r = int(0), len(nums) - 1 while l < r: mid = int((l + r) / 2) if nums[mid] < target: l = mid + 1 else: r = mid if nums[l] < target: return l + 1 return l if __name__ == '__main__': # begin s = Solution() print (s.searchInsert([1,3,5,6],5))

Convert a Number to Hexadecimal – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Convert a Number to Hexadecimal - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import com.sun.corba.se.spi.orbutil.fsm.Guard.Result; class Solution { public String toHex(int num) { String hex_map = "0123456789abcdef"; if (num == 0) return "0"; String res = ""; // To avoid infinite loop caused by negative num while (num != 0 && res.length() < 8) { res = hex_map.charAt(num & 15) + res; num = num >> 4; } return res; } /* public String toHex(int num) { String hex = Integer.toHexString(num); return hex; } */ }

Valid Palindrome – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Valid Palindrome - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def isPalindrome(self, s): """ :type s: str :rtype: bool """ alnum_s = [t.lower() for t in s if t.isalnum()] ls = len(alnum_s) if ls <= 1: return True mid = ls / 2 for i in range(mid): if alnum_s[i] != alnum_s[ls - 1 - i]: return False return True

Poor Pigs – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Poor Pigs - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { public int poorPigs(int buckets, int minutesToDie, int minutesToTest) { int n = minutesToTest / minutesToDie + 1; int pigs = 0; while (Math.pow(n, pigs) < buckets) pigs++; return pigs; } }

Unique Paths II – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Unique Paths II - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def uniquePathsWithObstacles(self, obstacleGrid): # """ # :type obstacleGrid: List[List[int]] # :rtype: int # """ # m, n = len(obstacleGrid), len(obstacleGrid[0]) # dmap = [[0] * n for _ in range(m)] # for i in range(m): # if obstacleGrid[i][0] != 1: # dmap[i][0] = 1 # else: # break # for j in range(n): # if obstacleGrid[0][j] != 1: # dmap[0][j] = 1 # else: # break # for i in range(1, m): # for j in range(1, n): # if obstacleGrid[i][j] == 1: # continue # l = u = 0 # if i - 1 >= 0: # u = dmap[i - 1][j] # if j - 1 >= 0: # l = dmap[i][j - 1] # dmap[i][j] = l + u # return dmap[m - 1][n - 1] def uniquePathsWithObstacles(self, obstacleGrid): m, n = len(obstacleGrid), len(obstacleGrid[0]) if m == 0: return 0 dmap = [[0] * (n + 1) for _ in range(m + 1)] dmap[m - 1][n] = 1 for i in range(m - 1, -1, -1): for j in range(n - 1, -1, -1): if obstacleGrid[i][j] == 1: dmap[i][j] = 0 else: dmap[i][j] = dmap[i][j + 1] + dmap[i + 1][j] return dmap[0][0]

Min Stack – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Min Stack - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import java.util.ArrayList; import java.util.List; /* class MinStack { private Stackstack; private Stack minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x) { stack.push(x); if (minStack.size() == 0 || x <= minStack.peek()) minStack.push(x); } public void pop() { if (stack.size() > 0) { int curr = stack.pop(); if (minStack.size() > 0 && curr == minStack.peek()) minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { if (minStack.size() > 0) return minStack.peek(); else return stack.peek(); } } */ class MinStack { private Stack stack; private Stack minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int x) { stack.push(x); if (minStack.size() == 0 || x <= minStack.peek()) minStack.push(x); else minStack.push(minStack.peek()); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }

Min Stack – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Min Stack - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# class MinStack(object): # def __init__(self): # """ # initialize your data structure here. # """ # self.stack = [] # self.min_stack = [] # def push(self, x): # """ # :type x: int # :rtype: nothing # """ # self.stack.append(x) # if len(self.min_stack) == 0 or x <= self.min_stack[-1]: # self.min_stack.append(x) # def pop(self): # """ # :rtype: nothing # """ # if len(self.stack) > 0: # last = self.stack[-1] # # Need to check whether pop minStack # if len(self.min_stack) > 0 and last == self.min_stack[-1]: # self.min_stack.pop() # self.stack.pop() # def top(self): # """ # :rtype: int # """ # if len(self.stack) > 0: # return self.stack[-1] # return None # def getMin(self): # """ # :rtype: int # """ # if len(self.min_stack) > 0: # return self.min_stack[-1] # else: # if len(self.stack) > 0: # return self.stack[-1] # return None class MinStack(object): def __init__(self): """ initialize your data structure here. """ self.stack = [] self.min_stack = [] def push(self, x): """ :type x: int :rtype: nothing """ self.stack.append(x) if len(self.min_stack) == 0: self.min_stack.append(x) return if x <= self.min_stack[-1]: self.min_stack.append(x) else: # Push top of min stack again self.min_stack.append(self.min_stack[-1]) def pop(self): """ :rtype: nothing """ if len(self.stack) > 0: # Much simple than solution 1 # But use more space self.min_stack.pop() self.stack.pop() def top(self): """ :rtype: int """ if len(self.stack) > 0: return self.stack[-1] return None def getMin(self): """ :rtype: int """ if len(self.min_stack) > 0: return self.min_stack[-1] return None

Linked List Cycle – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Linked List Cycle - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): # def hasCycle(self, head): # """ # :type head: ListNode # :rtype: bool # """ # # Add max and check if reach max # if head is None: # return False # count = 0 # max = 100000 # pos = head # while pos is not None: # count += 1 # pos = pos.next # if count > max: # return True # return False # def hasCycle(self, head): # # Hash or set # dic = {} # pos = head # while pos is not None: # try: # dic[pos] # return True # except KeyError: # dic[pos] = pos # pos = pos.next # return False def hasCycle(self, head): # Two points try: fast = head.next.next slow = head.next while fast != slow: fast = fast.next.next slow = slow.next return True except: return False

Binary Gap – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Binary Gap - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution: # def binaryGap(self, n: int) -> int: # # Store index # A = [i for i in xrange(32) if (N >> i) & 1] # if len(A) < 2: return 0 # return max(A[i+1] - A[i] for i in xrange(len(A) - 1)) def binaryGap(self, n: int) -> int: # one pass and store max current = 1 last1 = -1 out = 0 while n > 0: if n % 2 == 1: if last1 >= 1: out = max(out, current - last1) last1 = current current += 1 n = n // 2 return out # def binaryGap(self, n: int) -> int: # # one pass and store max # res = 0 # last = -1 # # Get binary encoding with bin # for i, curr in enumerate(bin(n)[2:]): # if curr == '1': # if last >= 0: # res = max(res, i - last) # last = i # return res

Paint Fence – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Paint Fence - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def numWays(self, n, k): # """ # :type n: int # :type k: int # :rtype: int # """ # w = [0, k, k*k] # while len(w) <= n: # w += sum(w[-2:]) * (k-1), # return w[n] def numWays(self, n, k): if n == 0: return 0 elif n == 1: return k # two step dp # ways[1] = k # ways[2] = k * k # ways[i>2] = (ways[i-1] + ways[i-2]) * (k - 1) dp = [0] * 2 dp[0] = k dp[1] = k * k for i in range(2, n): temp = dp[1] dp[1] = sum(dp) * (k - 1) dp[0] = temp return dp[1]

Hamming Distance – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Hamming Distance - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); } }

Walls and Gates – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Walls and Gates - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def wallsAndGates(self, rooms): """ :type rooms: List[List[int]] :rtype: void Do not return anything, modify rooms in-place instead. """ # BFS with queue direction = [(0, 1), (1, 0), (0, -1), (-1, 0)] m = len(rooms) if m == 0: return n = len(rooms[0]) q = [] for row in range(m): for col in range(n): # gate if rooms[row][col] == 0: q.append((row, col)) while len(q) > 0: point = q.pop(0) row, col = point[0], point[1] for d in direction: r = row + d[0] c = col + d[1] # wall or out of rooms if r < 0 or c < 0 or r >= m or c >= n or rooms[r][c] != 2147483647: continue rooms[r][c] = rooms[row][col] + 1 q.append((r, c))

Combination Sum III – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Combination Sum III - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
import itertools as it class Solution(object): def combinationSum3(self, k, n): """ :type k: int :type n: int :rtype: List[List[int]] """ return list(it.ifilter(lambda x: sum(x) == n, list(it.combinations(range(1, 10), k))))

Max Consecutive Ones – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Max Consecutive Ones - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def findMaxConsecutiveOnes(self, nums): """ :type nums: List[int] :rtype: int """ ans = 0 curr = 0 for n in nums: if n == 1: # Add 1 to curr when encounter 1 curr += 1 if curr > ans: ans = curr else: # Add 1 to curr when encounter 1 curr = 0 return ans

Subarray Sum Equals K – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Subarray Sum Equals K - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution { /*public int subarraySum(int[] nums, int k) { int count = 0; for (int start = 0; start < nums.length; start++) { int sum = 0; for (int end = start; end < nums.length; end++) { sum += nums[end]; if (sum == k) count++; } } return count; }*/ public int subarraySum(int[] nums, int k) { int count = 0, sum = 0; HashMap < Integer, Integer > map = new HashMap < > (); map.put(0, 1); for (int i = 0; i < nums.length; i++) { sum += nums[i]; // check if sum - k in hash if (map.containsKey(sum - k)) count += map.get(sum - k); // push sum into hash map.put(sum, map.getOrDefault(sum, 0) + 1); } return count; } }

Diameter of Binary Tree – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Diameter of Binary Tree - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# 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): # https://leetcode.com/problems/diameter-of-binary-tree/solution/ def diameterOfBinaryTree(self, root): self.ans = 1 def depth(node): if not node: return 0 L = depth(node.left) R = depth(node.right) self.ans = max(self.ans, L+R+1) return max(L, R) + 1 depth(root) # number of nodes - 1 = length return self.ans - 1

Two Sum III – Data structure design – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Two Sum III - Data structure design - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class TwoSum(object): def __init__(self): """ initialize your data structure here """ self.internal = [] self.dic = {} def add(self, number): """ Add the number to an internal data structure. :rtype: nothing """ self.internal.append(number) if number in self.dic: # more than once self.dic[number] = True return # once self.dic[number] = False def find(self, value): """ Find if there exists any pair of numbers which sum is equal to the value. :type value: int :rtype: bool """ for v in self.internal: if value - v in self.dic: if v << 1 == value and not self.dic[v]: continue return True return False # Your TwoSum object will be instantiated and called as such: # twoSum = TwoSum() # twoSum.add(number) # twoSum.find(value)

Product of Array Except Self – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Product of Array Except Self - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] res = new int[n]; res[0] = 1; for (int i = 1; i < n; i++) { // left part res[i] = res[i - 1] * nums[i - 1]; } int right = 1; for (int i = n - 1; i >= 0; i--) { res[i] *= right; // right part right *= nums[i]; } return res; } }

Missing Number – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Missing Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { /* public int missingNumber(int[] nums) { int n = nums.length; int total = n * (n + 1) / 2; for (int i = 0; i < nums.length; i++) { total -= nums[i]; } return total; } */ public int missingNumber(int[] nums) { int res = nums.length; for (int i = 0; i < nums.length; i++) { res ^= i; res ^= nums[i]; } return res; } /* public int missingNumber(int[] nums) { Arrays.sort(nums); int left = 0, right = nums.length - 1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > mid) right = mid - 1; else left = mid + 1; } return left; } */ }

Maximum Subarray – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Maximum Subarray - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def maxSubArray(self, nums): # return self.maxSubArrayHelper(nums, 0, len(nums) - 1) # # def maxSubArrayHelper(self, nums, l, r): # if l > r: # return -2147483647 # mid = (l + r) / 2 # leftAns = self.maxSubArrayHelper(nums, l, mid - 1) # rightAns = self.maxSubArrayHelper(nums, mid + 1, r) # lMaxSum = res = 0 # for i in range(mid - 1, l -1, -1): # res += nums[i] # lMaxSum = max(res, lMaxSum) # rMaxSum = res = 0 # for i in range(mid + 1, r + 1): # res += nums[i] # rMaxSum = max(res, rMaxSum) # return max(lMaxSum + nums[mid] + rMaxSum, max(leftAns, rightAns)) # def maxSubArray(self, nums): # """ # :type nums: List[int] # :rtype: int # """ # ls = len(nums) # start = [0] * ls # all = [0] * ls # start[-1], all[-1] = nums[-1], nums[-1] # for i in reversed(range(ls - 1)): # start[i] = max(nums[i], nums[i] + start[i + 1]) # all[i] = max(start[i], all[i + 1]) # return all[0] # def maxSubArray(self, nums): # ls = len(nums) # start, all = nums[-1], nums[-1] # for i in reversed(range(ls - 1)): # start = max(nums[i], nums[i] + start) # all = max(start, all) # return all def maxSubArray(self, nums): maxEndingHere = maxSofFar = nums[0] for i in range(1, len(nums)): maxEndingHere = max(maxEndingHere + nums[i], nums[i]) maxSofFar = max(maxEndingHere, maxSofFar) return maxSofFar

Copy List with Random Pointer – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Copy List with Random Pointer - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for singly-linked list with a random pointer. # class RandomListNode(object): # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution(object): # def copyRandomList(self, head): # """ # :type head: RandomListNode # :rtype: RandomListNode # """ # # hash O(n) and O(n) # dic = collections.defaultdict(lambda: RandomListNode(0)) # dic[None] = None # n = head # while n: # dic[n].label = n.label # dic[n].next = dic[n.next] # dic[n].random = dic[n.random] # n = n.next # return dic[head] # def copyRandomList(self, head): # # hash O(n) and O(n) # dic = {} # dic[None] = None # dummyHead = RandomListNode(0) # p, q = head, dummyHead # while p is not None: # q.next = RandomListNode(p.label) # dic[p] = q.next # p = p.next # q = q.next # p, q = head, dummyHead # while p is not None: # q.next.random = dic[p.random] # p = p.next # q = q.next # return dummyHead.next def copyRandomList(self, head): # Modify original structure: Original->Copy->Original->Copy # node.next.random = node.random.next # O(n) and O(1) p = head while p is not None: next = p.next copy = RandomListNode(p.label) p.next = copy copy.next = next p = next p = head while p is not None: if p.random is not None: p.next.random = p.random.next p = p.next.next p = head if p is not None: headCopy = p.next else: headCopy = None while p is not None: copy = p.next p.next = copy.next p = p.next if p is not None: copy.next = p.next return headCopy

Single Number – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Single Number - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def singleNumber(self, nums): # """ # :type nums: List[int] # :rtype: int # """ # # hash # dic = {} # for num in nums: # try: # dic[num] += 1 # except KeyError: # dic[num] = 1 # for num in nums: # if dic[num] == 1: # return num # def singleNumber(self, nums): # # set # s = set() # for num in nums: # if num in s: # s.remove(num) # else: # s.add(num) # return s.pop() def singleNumber(self, nums): # xor res = 0 for num in nums: res ^= num return res

Find Minimum in Rotated Sorted Array II – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find Minimum in Rotated Sorted Array II - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def findMin(self, nums): # """ # :type nums: List[int] # :rtype: int # """ # return self.get_min(nums, 0, len(nums) - 1) # def get_min(self, nums, start, end): # mid = (start + end) / 2 # if start == end: # # one element # return nums[start] # if mid == start or mid == end: # # two element # return min(nums[start], nums[end]) # if nums[mid] < nums[end]: # # right side sorted # if nums[mid] > nums[start]: # # not rotated # return nums[start] # return self.get_min(nums, start, mid) # elif nums[mid] > nums[end]: # # left side sorted # return self.get_min(nums, mid, end) # else: # # cannot judge which direction is sorted # return min(self.get_min(nums, start, mid), self.get_min(nums, mid, end)) # def findMin(self, nums): # start, end = 0, len(nums) - 1 # while start < end: # mid = (start + end) / 2 # if nums[mid] > nums[end]: # start = mid + 1 # elif nums[mid] < nums[end]: # end = mid # else: # end -= 1 # return nums[start] def findMin(self, nums): l, r = 0, len(nums) - 1 while l < r and nums[l] >= nums[r]: mid = (l + r) / 2 if nums[mid] > nums[r]: l = mid + 1 elif nums[mid] < nums[l]: r = mid else: # nums[l] = nums[r] = nums[mid] l += 1 return nums[l]

Fizz Buzz – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Fizz Buzz - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): # def fizzBuzz(self, n): # """ # :type n: int # :rtype: List[str] # """ # res = [] # for i in range(1, n + 1): # if i % 3 == 0: # if i % 5 == 0: # res.append('FizzBuzz') # else: # res.append('Fizz') # elif i % 5 == 0: # res.append('Buzz') # else: # res.append(str(i)) # return res # def fizzBuzz(self, n): # """ # :type n: int # :rtype: List[str] # """ # res = [] # for i in range(1, n + 1): # curr = '' # if i % 3 == 0: # curr += 'Fizz' # if i % 5 == 0: # curr += 'Buzz' # if not len(curr): # curr += str(i) # res.append(curr) # return res def fizzBuzz(self, n): return [str(i) * (i % 3 != 0 and i % 5 != 0) + "Fizz" * (i % 3 == 0) + "Buzz" * (i % 5 == 0) for i in range(1, n + 1)] # def fizzBuzz(self, n): # return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]

Squares of a Sorted Array – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Squares of a Sorted Array - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution { /* public int[] sortedSquares(int[] A) { int[] res = new int[A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i] * A[i]; Arrays.sort(res); return res; } */ public int[] sortedSquares(int[] A) { int pos = 0; int[] res = new int[A.length]; int curr = 0; while (pos < A.length && A[pos] < 0) pos++; int npos = pos - 1; while (pos < A.length && npos >= 0) { if (A[pos] * A[pos] < A[npos] * A[npos]) { res[curr++] = A[pos] * A[pos]; pos++; } else { res[curr++] = A[npos] * A[npos]; npos--; } } while (npos >= 0) { res[curr++] = A[npos] * A[npos]; npos--; } while (pos < A.length) { res[curr++] = A[pos] * A[pos]; pos++; } return res; } }

Count Primes – Leetcode Challenge – C++ Solution
This is the c++ solution for the Leetcode problem - Count Primes - Leetcode Challenge - C++ Solution.
Source - qiyuangong's repository.
// Source : https://leetcode.com/problems/count-primes/ /********************************************************************************** * * Description: * Count the number of prime numbers less than a non-negative number, n. * * Credits:Special thanks to @mithmatt for adding this problem and creating all test cases. * * Let's start with a isPrime function. To determine if a number is prime, we need to check if * it is not divisible by any number less than n. The runtime complexity of isPrime function * would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better? * * As we know the number must not be divisible by any number > n / 2, we can immediately cut the total * iterations half by dividing only up to n / 2. Could we still do better? * * Let's write down all of 12's factors: * * 2 × 6 = 12 * 3 × 4 = 12 * 4 × 3 = 12 * 6 × 2 = 12 * * As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider * factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n. * * Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach? * * public int countPrimes(int n) { * int count = 0; * for (int i = 1; i < n; i++) { * if (isPrime(i)) count++; * } * return count; * } * * private boolean isPrime(int num) { * if (num <= 1) return false; * // Loop's ending condition is i * i <= num instead of i <= sqrt(num) * // to avoid repeatedly calling an expensive function sqrt(). * for (int i = 2; i * i <= num; i++) { * if (num % i == 0) return false; * } * return true; * } * * The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. * But don't let that name scare you, I promise that the concept is surprisingly simple. * * [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) * * [https://leetcode.com/static/images/solutions/Sieve_of_Eratosthenes_animation.gif] * [http://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif] * * Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation"() * by SKopp is licensed under CC BY 2.0. * * * [Skoop](http://de.wikipedia.org/wiki/Benutzer:SKopp) * * [CC BY 2.0](http://creativecommons.org/licenses/by/2.0/) * * We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 * must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, * all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. * Now we look at the next number, 4, which was already marked off. What does this tell you? Should you * mark off all multiples of 4 as well? * * 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible * by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, * all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off. * There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off? * * In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off * by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current * number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ... * Now what should be the terminating loop condition? * * It is easy to say that the terminating loop condition is p n, which is certainly correct but not efficient. * Do you still remember Hint #3? * * Yes, the terminating loop condition can be p n, as all non-primes ≥ √n must have already been marked off. * When the loop terminates, all the numbers in the table that are non-marked are prime. * * The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). * For the more mathematically inclined readers, you can read more about its algorithm complexity on * [Wikipedia](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity). * * public int countPrimes(int n) { * boolean[] isPrime = new boolean[n]; * for (int i = 2; i < n; i++) { * isPrime[i] = true; * } * // Loop's ending condition is i * i < n instead of i < sqrt(n) * // to avoid repeatedly calling an expensive function sqrt(). * for (int i = 2; i * i < n; i++) { * if (!isPrime[i]) continue; * for (int j = i * i; j < n; j += i) { * isPrime[j] = false; * } * } * int count = 0; * for (int i = 2; i < n; i++) { * if (isPrime[i]) count++; * } * return count; * } * * **********************************************************************************/ #include#include #include using namespace std; int countPrimes(int n) { vector isPrimer(n, true); for (int i = 2; i * i < n; i++) { if (isPrimer[i]) { for (int j = i * i; j < n; j += i) { isPrimer[j] = false; } } } int cnt = 0; for (int i = 2; i < n; i++) { if (isPrimer[i]) { //cout << i << ", "; cnt++; } } return cnt; } int main(int argc, char **argv) { int n = 100; if (argc > 1) { n = atoi(argv[1]); } cout << endl << n << " : " << countPrimes(n) << endl; return 0; }

XOR Queries of a Subarray – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - XOR Queries of a Subarray - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution: def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]: pref = [0] # Compute accumulated xor from head for e in arr: pref.append(e ^ pref[-1]) ans = [] # query result equal to xor[0, l] xor x[0, r] for [l, r] in queries: ans.append(pref[r+1] ^ pref[l]) return ans # def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]: # for i in range(len(arr) - 1): # arr[i + 1] ^= arr[i] # return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries]

Maximum Product of Three Numbers – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Maximum Product of Three Numbers - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution { /*public int maximumProduct(int[] nums) { Arrays.sort(nums); return Math.max(nums[0] * nums[1] * nums[nums.length - 1], nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]); }*/ public int maximumProduct(int[] nums) { int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE; int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE; for (int n: nums) { if (n <= min1) { min2 = min1; min1 = n; } else if (n <= min2) { // n lies between min1 and min2 min2 = n; } if (n >= max1) { // n is greater than max1, max2 and max3 max3 = max2; max2 = max1; max1 = n; } else if (n >= max2) { // n lies betweeen max1 and max2 max3 = max2; max2 = n; } else if (n >= max3) { // n lies betwen max2 and max3 max3 = n; } } return Math.max(min1 * min2 * max1, max1 * max2 * max3); } }

Contains Duplicate – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Contains Duplicate - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ # use set to check duplicate return len(nums) != len(set(nums)) # def containsDuplicate(self, nums): # nums.sort() # for i in range(len(nums) - 1): # if nums[i] == nums[i + 1]: # return True # return False

Palindrome Permutation – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Palindrome Permutation - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object): def canPermutePalindrome(self, s): """ :type s: str :rtype: bool """ dic = {} for c in s: dic[c] = dic.get(c, 0) + 1 odd, even = 0, 0 for c in dic: if dic[c] % 2 == 0: even += 1 else: odd += 1 if odd <= 1: return True return False