Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1 Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2 Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') Solution: class Solution { public int minDistance(String word1, String word2) { if (word1 == null || word2 == null) return -1; if (word1.

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

Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer. Example 1 Input: 123 Output: 321 Example 2 Input: -123 Output: -321 Example 3 Input: 120 Output: 21 Note Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. Solution class Solution(object): def reverse(self, x): """ :type x: int :rtype: int """ if x == "" or x == None: return x res = "" if x > 0 else "-" string = str(abs(x)) for i in range(len(string)-1, -1, -1): res += string[i] res = int(res) if res < -2**31 or res >= 2**31: return 0 return int(res) class Solution: def reverse(self, x: int) -> int: isNegative = x < 0 x = abs(x) new_x = 0 while x !

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

One Edit Distance

Given two strings s and t, determine if they are both one edit distance apart. Note There are 3 possiblities to satisify one edit distance apart: Insert a character into s to get t Delete a character from s to get t Replace a character of s to get t Example 1 Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t.

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

Find a Local Minima in an Array

Given an array arr[0 .. n-1] of distinct integers, the task is to find a local minima in it. We say that an element arr[x] is a local minimum if it is less than or equal to both its neighbors. For corner elements, we need to consider only one neighbor for comparison. There can be more than one local minima in an array, we need to find any one of them.

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

Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right. Example 1 Input: [3,9,20,null,null,15,7] 3 /\ / \ 9 20 /\ / \ 15 7 Output: [ [9], [3,15], [20], [7] ] Example 2 Input: [3,9,8,4,0,1,7] 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 Output: [ [4], [9], [3,0,1], [8], [7] ] Example 3 Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5) 3 /\ / \ 9 8 /\ /\ / \/ \ 4 01 7 /\ / \ 5 2 Output: [ [4], [9,5], [3,0,1], [8,2], [7] ] Solution # https://www.

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

Convert Binary Search Tree to Sorted Doubly Linked List

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list. Let’s take the following BST as an example, it may help you understand the problem better: We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

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

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note There may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity? Solution (Bottom-up) Python

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

Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray). Example 1 Input: [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. Example 2 Input: [2,2,2,2,2] Output: 1 Explanation: The longest continuous increasing subsequence is [2], its length is 1.

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

Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. The order of output does not matter. Example 1 Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc".

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

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? Example 1 Input: 2, [[1,0]] Output: true Explanation: There are a total of 2 courses to take.

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