Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Solution # Time: `O(n)` class Solution: def longestConsecutive(self, nums: List[int]) -> int: # Count occurence of nums mapping = {} for num in nums: mapping[num] = True # init longest length longest = 0 # iterate over nums for num in nums: if num in mapping: # num exists in mapping => init l = 1 l = 1 # num was counted, so we delete num del mapping[num] left, right = num-1, num+1 # Move left while left in mapping: # left was counted, so we delete left del mapping[left] left -= 1 l += 1 # Move right while right in mapping: # right was counted, so we delete right del mapping[right] right += 1 l += 1 # Update longest longest = max(longest, l) return longest

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

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note Given n will be a positive integer. Example 1 Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2 Input: 3 Output: 3 Explanation: There are three ways to climb to the top.

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

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Solution class Solution: def generateParenthesis(self, n: int) -> List[str]: """ :type n: int :rtype: List[str] """ ans = [] self.dfs(ans, '', 0, 0, n) return ans def dfs(self, ans, S, left, right, n): if len(S) == 2 * n: ans.

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

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “". Example 1 Input: ["flower","flow","flight"] Output: "fl" Example 2 Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Note All given inputs are in lowercase letters a-z. Note # Time: O(n*l), l: number of strings class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs or len(strs) == 0: return "" res = strs[0] for s in strs: # string.

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

Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note The array size can be very large. Solution that uses too much extra space will not pass the judge. Example int[] nums = new int[] {1,2,3,3,3}; Solution solution = new Solution(nums); // pick(3) should return either index 2, 3, or 4 randomly.

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

Find the Celebrity

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them. Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: “Hi, A.

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

Arrays in Python

Reverse an array arr = [1, 2, 3, 4, 5, 6, 7, 8] reversedArray = arr[::-1] # [8, 7, 6, 5, 4, 3, 2, 1] arr[3:5] = arr[3:5][::-1] Slices with step s[i:j:k] means “slice of s from i to j with step k”. When i and j are absent, the whole sequence is assumed and thus s[::k] means “every k-th item” in the entire sequence. s = range(20) # output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] # 3rd item from s: s[::3] # output: [0, 3, 6, 9, 12, 15, 18] # 3rd item from s[2:]: s[2:] # output: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] s[2::3] # output: [2, 5, 8, 11, 14, 17] # 3rd item from s[5:12]: s[5:12] # output: [5, 6, 7, 8, 9, 10, 11] s[5:12:3] # output: [5, 8, 11] # 3rd item from s[:10]: s[:10] # output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] s[:10:3] # output: [0, 3, 6, 9] Clone a list newArr = oldArr[:]

by lek tin in "programming-language" access_time 2-min read

Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1. Example 1 Input: 123 Output: "One Hundred Twenty Three" Example 2 Input: 12345 Output: "Twelve Thousand Three Hundred Forty Five" Example 3 Input: 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Example 4 Input: 1234567891 Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One" Solution class Solution: def __init__(self): self.

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

Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Note Your algorithm should run in O(n) time complexity and O(1) space complexity. Example 1 Input: [1,2,3,4,5] Output: true Example 2 Input: [5,4,3,2,1] Output: false Solution import math class Solution: def increasingTriplet(self, nums: List[int]) -> bool: if not nums or len(nums) < 3: return False # min_1 < min_2 min_1, min_2 = math.

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

Simplify Path

Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" path = "/a/../../b/../c//.//", => "/c" path = "/a//b////c/d//././/..", => "/a/b/c" In a UNIX-style file system, a period ('.') refers to the current directory, so it can be ignored in a simplified path. Additionally, a double period ("..") moves up a directory, so it cancels out whatever the last directory was.

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