Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1 Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2 Input: [-7,-3,2,3,11] Output: [4,9,9,49,121] Note 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order. Solution class Solution: def sortedSquares(self, A: List[int]) -> List[int]: result = A[:] leftPtr, rightPtr = 0, len(A)-1 i = 0 while leftPtr <= rightPtr: i += 1 if abs(A[leftPtr]) <= abs(A[rightPtr]): result[-i] = A[rightPtr] * A[rightPtr] rightPtr -= 1 else: result[-i] = A[leftPtr] * A[leftPtr] leftPtr += 1 return result

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

Minesweeper

Let’s play the minesweeper game (Wikipedia, online game)! You are given a 2D char matrix representing the game board. 'M' represents an unrevealed mine, 'E' represents an unrevealed empty square, 'B' represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit ('1' to '8') represents how many mines are adjacent to this revealed square, and finally 'X' represents a revealed mine.

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

Minimum Remove to Make Valid Parentheses

Given a string s of '(' , ')' and lowercase English characters. Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if and only if: It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.

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

Package Dependencies

Solution def package_dependencies(dependencies): result = [] visiting = set([]) visited = set([]) def dfs(node): if node in visited: return visiting.add(node) for dependency in node.dependencies: if dependency in visiting: raise Exception("Have cycle in dependency graph.") if dependency not in visited: dfs(dependency) visiting.remove(node) visited.add(node) result.add(node) for node in dependencies: dfs(node) return result

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

Concatenated Words

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array. Example: Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; "dogcatsdog" can be concatenated by "dog", "cats" and "dog"; "ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

Concatenate String Using Smaller Strings

Given a big string and a list of small strings, find whether the big string can be represented only by concatenation of smaller strings. Example: target = "abccbacbb" smallerStrings = ["abc", "cc", "ab", "bac", "b"] Output: True Solution Dynamic programming target = "abccbacbb" smallerStrings = ["abc", "cc", "ab", "bac", "b"] N = len(target) dp = [False for _ in range(N)] def check(i, target): for s in smallerStrings: l = len(s) # print(s) if i + l <= N: tryStr = target[i:i+l] # print(tryStr) if tryStr == s: dp[i+l-1] = True check(i+l, target) # print("-------") check(0, target) print(dp) print(dp[N-1])

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

Word Ladder II

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Example 1 Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] Example 2 Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

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

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1 Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()" Example 2 Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()" Solution Dynamic programming // Time: `O(n)` // Space: `O(n)` public class Solution { public int longestValidParentheses(String s) { int maxans = 0; // dp array: ith element of dp represents the length of the longest valid substring ending at ith index.

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

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. NOTE: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 Return: [ [5,4,11,2], [5,8,4,5] ] Solution # Definition for a binary tree node.

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

Best Time to Buy and Sell Stock III

Say you have an array for which the ithelement is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. NOTE: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1 Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

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