Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? Example: Input: [4,3,2,7,8,2,3,1] Output: [2,3] Solution # Time: O(n) # Space: O(1) class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: """ :type nums: List[int] :rtype: List[int] """ result = [] for i in nums: if nums[abs(i)-1] < 0: result.

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

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