sliding-window:

Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string. Example 1: Input: s1 = "ab" s2 = "eidbaooo" Output: True Explanation: s2 contains one permutation of s1 ("ba"). Example 2: Input:s1= "ab" s2 = "eidboaoo" Output: False Constraints: The input strings only contain lower case letters.

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

Moving Average From Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Example MovingAverage m = new MovingAverage(3); m.next(1) = 1 m.next(10) = (1 + 10) / 2 m.next(3) = (1 + 10 + 3) / 3 m.next(5) = (10 + 3 + 5) / 3 Solution from collections import deque class MovingAverage: def __init__(self, size: int): """ Initialize your data structure here.

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

Logger Rate Limiter

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds. Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false. It is possible that several messages arrive roughly at the same time. Example Logger logger = new Logger(); // logging string "foo" at timestamp 1 logger.

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

Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes. Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1. It is possible that several hits arrive roughly at the same time. Example HitCounter counter = new HitCounter(); // hit at timestamp 1.

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

Shortest Subarray With Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K. If there is no non-empty subarray with sum at least K, return -1. Example 1 Input: A = [1], K = 1 Output: 1 Example 2 Input: A = [1,2], K = 4 Output: -1 Example 3 Input: A = [2,-1,2], K = 3 Output: 3 Note 1 <= A.length <= 50000 -10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9 Solution (sliding window using pointers) This version exceeds time limit Time: O(N)

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

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. *### Example 1 Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. *### Example 2 Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. *### Example 3 Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

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

Subarray Product Less Than K

Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k. Example 1 Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

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

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead. Example: Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint. Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

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

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC" Note If there is no such window in S that covers all characters in T, return the empty string “". If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

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

Longest Substring With at Most Two Distinct Characters

Given a string s, find the length of the longest substring t that contains at most 2 distinct characters. Example 1 Input: "eceba" Output: 3 Explanation: t is "ece" which its length is 3. Example 2 Input: "ccaabbb" Output: 5 Explanation: t is "aabbb" which its length is 5. Solution class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { HashMap<Character, Integer> countMap = new HashMap<Character, Integer>(); int left = 0; int max = 0; for (int i = 0; i < s.

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