All posts tagged algorithms
Problem statement Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. Solution Obviously the naive approach to this problem would be to subtract the divisor from the dividend until the dividend becomes less than the divisor, while keeping track of how many times . . . Read more
Problem statement Given a list, nums, of distinct numbers, return all possible unique permutations. Sample input
Sample output

[[1, 2, 1], [2, 1, 1], [1, 1, 2]] 
Solution In another post we showed how this problem can be solved iteratively. We can use the same technique but add a check to skip adding the number n to . . . Read more
Problem statement Given a list, nums, of distinct numbers, return all possible permutations. Sample input
Sample output

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 
Solution In another post we showed how this problem can be solved using a recursive technique by swapping. We stumbled upon a nice iterative solution that we thought might be worth . . . Read more
Problem statement Given a list, nums, of distinct numbers, return all possible permutations. Sample input
Sample output

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 
Solution We are using a technique called permutations by swapping. Full code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution(object): def swap(self, nums, i, j): tmp = nums[i] nums[i] = nums[j] nums[j] = tmp def solve(self, nums, i, result): if i == len(nums)1: result.append(list(nums)) return for j in range(i, len(nums)): self.swap(nums, i, j) self.solve(nums, i+1, result) self.swap(nums, i, j) def permute(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ ans = [] self.solve(nums, 0, ans) return ans def main(): solution = Solution() print(solution.permute([1,2,3])) if __name__ == "__main__": main() 
Problem statement You are given an 2D matrix / array representing an image. Rotate matrix by 90 degrees (clockwise) inplace. Solution We will work through the matrix layers. The layers of a matrix are illustrated below in different colours: There are a total of layers. We then iterate of the . . . Read more
Problem statement A time series is a series of data points indexed in time order. They are commonly used in the financial world, especially in stock markets. In this challenge you are working with a time series of stock prices. You are given historical records where the stock at time . . . Read more
Problem statement Given a string containing just the characters ( and ), find the length of the longest valid (wellformed) parentheses substring. Sample input
Sample output
Sample input 1
Sample output 1
Solution We will solve this problem using a Stack. We are going to iterate . . . Read more
Problem statement Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. If the target is not found in the array, return . Sample input
Sample output
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution(object): def search(self, nums, n, start, end, ans): if start > end: return mid = start + (end  start)//2 if n == nums[mid]: ans[0] = min(ans[0], mid) ans[1] = max(ans[1], mid) self.search(nums, n, start, mid1, ans) self.search(nums, n, mid+1, end, ans) def searchRange(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ ans = [len(nums), 1] self.search(nums, target, 0, len(nums)1, ans) if ans[0]==len(nums): return [1,1] return ans def main(): solution = Solution() print(solution.searchRange([5, 7, 7, 8, 8, 10], 8)) if __name__ == "__main__": main() 
Problem statement Given n nonnegative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. Sample input
Sample output
Solution We can solve this problem in time by iterating over the array twice. Once . . . Read more
Problem statement Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Sample input
Sample output

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] 
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

class Solution(object): def solve(self, digits, i, current, ans): """ :type digits: str :rtype: List[str] """ if len(digits) == 0: if len(current) > 0: ans.append(current) return mapping = {2:['a','b','c'], 3:['d','e','f'], 4:['g','h','i'], 5:['j','k','l'], 6:['m','n','o'], 7:['p','q','r', 's'], 8:['t','u','v'], 9:['w','x','y', 'z']} d = ord(digits[i])  48 chars = mapping[d] for c in chars: self.solve(digits[i+1:], i, current + c, ans) def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ ans = [] self.solve(digits, 0, '', ans) return ans def main(): solution = Solution() print(solution.letterCombinations("23")) print(solution.letterCombinations("")) if __name__ == "__main__": main() 