Skip to content

Poopcode

Code snippets | Coding interview questions with solutions | JavaScript tutorials | Python tutorials

Menu

  • JavaScript
  • Java
  • Node JS
  • MongoDB
  • Python
  • Linux
  • SQL
  • Angular
Trending Topics: Snippets•Solutions•TypeScript•JavaScript•Node JS

Author Archives

Bathrinathan

Feature image for Java related posts.

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

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

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

Feature image for Java related posts.

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;
    }
}

Feature image for Java related posts.

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) {
        HashMap hash = 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;
    }
}

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)

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)

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])

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

Feature image for Java related posts.

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)

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)

Feature image for Java related posts.

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 List memo;

    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

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

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

Feature image for Java related posts.

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; 
    }
}

Feature image for Java related posts.

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 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);
    }
    
    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();
    }
}

Feature image for Java related posts.

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();
    }

}

Feature image for Java related posts.

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));
    }*/
}

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)

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

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

Feature image for Java related posts.

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();
    }
}

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

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

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

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

Feature image for Java related posts.

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;
    } */
}

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))    
    

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

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

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]

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]

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"))        

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))

Feature image for Java related posts.

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);
    }
}

Feature image for Java related posts.

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;
    }
}

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

Feature image for Java related posts.

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;
    }
}

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))))

Feature image for Java related posts.

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;
    } */
}

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)

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

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]

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]


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

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)]

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]

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;
}

Feature image for Java related posts.

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;
    }
}

Feature image for Java related posts.

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);
    }
}

Top K Frequent Elements – Leetcode Challenge – Python Solution

This is the python solution for the Leetcode problem - Top K Frequent Elements - Leetcode Challenge - Python Solution.

Source - qiyuangong's repository.

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        counter = collections.Counter(nums)
        return [k for k,v in counter.most_common(k)]
        # return heapq.nlargest(k, count.keys(), key=count.get)

House Robber II – Leetcode Challenge – Python Solution

This is the python solution for the Leetcode problem - House Robber II - Leetcode Challenge - Python Solution.

Source - qiyuangong's repository.

class Solution(object):
    # def rob(self, nums):
    #     """
    #     :type nums: List[int]
    #     :rtype: int
    #     """
    #     if nums is None or len(nums) == 0:
    #         return 0
    #     ls = len(nums)
    #     dp = [0] * ls
    #     # dp from 0 ~ ls - 2
    #     dp[0] = nums[0]
    #     for i in range(1, ls - 1):
    #         if i < 2:
    #             dp[i] = max(nums[i], dp[i - 1])
    #         else:
    #             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    #     res = dp[ls - 2]
    #     # dp from 1 ~ ls - 1
    #     dp[0] = 0
    #     for i in range(1, ls):
    #         if i < 2:
    #             dp[i] = max(nums[i], dp[i - 1])
    #         else:
    #             dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    #     return max(res, dp[ls - 1])

    def rob(self, nums):
        if len(nums) == 1:
            return nums[0]
        return max(self.rob_helper(nums, 0, len(nums) - 2),
                   self.rob_helper(nums, 1, len(nums) - 1))


    def rob_helper(self, nums, low, high):
        prevMax = currMax = 0
        for index in range(low, high + 1):
            temp = currMax
            currMax = max(prevMax + nums[index], currMax)
            prevMax = temp
        return currMax

Permutations II – Leetcode Challenge – Python Solution

This is the python solution for the Leetcode problem - Permutations II - Leetcode Challenge - Python Solution.

Source - qiyuangong's repository.

class Solution(object):
    # def __init__(self):
    #     self.result = {}
    #
    # def permuteUnique(self, num):
    #     """
    #         :type nums: List[int]
    #         :rtype: List[List[int]]
    #         """
    #     if num is None:
    #         return []
    #     num.sort()
    #     self.getPermute([], num)
    #     return self.result.values()
    #
    # def getPermute(self, prefix, rest):
    #     ls = len(rest)
    #     if ls == 0:
    #         return
    #     elif ls == 1:
    #         temp = prefix + rest
    #         stemp = ''.join(str(t) for t in temp)
    #         self.result[stemp] = temp
    #     else:
    #         for i in range(ls):
    #             if i + 1 < ls and rest[i] == rest[i + 1]:
    #                 continue
    #             temp = prefix[:]
    #             temp.append(rest[i])
    #             self.getPermute(temp, rest[:i] + rest[i + 1:])

    def permuteUnique(self, num):
        res = []
        if len(num) == 0:
            return res
        self.permute(res, num, 0)
        return res

    def permute(self, res, num, index):
        if index == len(num):
            res.append(list(num))
            return
        appeared = set()
        for i in range(index, len(num)):
            if num[i] in appeared:
                continue
            appeared.add(num[i])
            num[i], num[index] = num[index], num[i]
            self.permute(res, num, index + 1)
            num[i], num[index] = num[index], num[i]

    def permuteUnique(self, num):
        # iterative solution
        res = [[]]
        for i in range(len(nums)):
            cache = set()
            while len(res[0]) == i:
                curr = res.pop(0)
                for j in range(len(curr) + 1):
                    # generate new n permutations from n -1 permutations
                    new_perm = curr[:j] + [nums[i]] + curr[j:]
                    stemp = ''.join(map(str, new_perm))
                    if stemp not in cache:
                        cache.add(stemp)
                        res.append(new_perm)
        return res

1 2 3 4 … 6 Older ›
Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here: Cookie Policy

Apps made with 💩

  • JSON Tree Viewer
  • _
  • JWT Decoder
  • _
  • Image to Base64 Converter
  • _
  • Mongo ObjectID to Timestamp Converter
  • _
  • URL Decoder
  • _
  • URL Encoder
  • _
  • Binary to Text Converter
  • _
  • Text to Binary Converter
  • _
  • SQL Formatter
  • _
  • Number to Words Converter
Top
 

Loading Comments...