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

Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language. Example 1 Input: [ "wrt", "wrf", "er", "ett", "rftt" ] Output: "wertf" Example 2 Input: [ "z", "x" ] Output: "zx" Example 3 Input: [ "z", "x", "z" ] Output: "" Explanation The order is invalid, so return "".

by lek tin in "algorithm" access_time 3-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

Intersection of Two Arrays

Given two arrays, write a function to compute their intersection. Example 1 Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2 Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Note Each element in the result must be unique. The result can be in any order. Solution Use binary search when one of the lists is very long and the other is short class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: if len(nums1) < len(nums2): return self.

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

Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1 Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ] Example 2 Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.

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

Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file. The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file. By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file. Example 1 Input: buf = "abc", n = 4 Output: "abc" Explanation: The actual number of characters read is 3, which is "abc".

by lek tin in "algorithm" access_time 2-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

Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list – whose elements may also be integers or other lists. Example 1 Input: [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,1,2,1,1]`. Example 2 Input: [1,[4,[6]]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: `[1,4,6]`.

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