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.
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.
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Solution 1 Time: O(n) Space: O(1) class Solution { public int trap(int[] height) { int n = height.
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note You may not slant the container and n is at least 2. The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
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.
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Note Your algorithm should run in O(n) time complexity and O(1) space complexity. Example 1 Input: [1,2,3,4,5] Output: true Example 2 Input: [5,4,3,2,1] Output: false Solution import math class Solution: def increasingTriplet(self, nums: List[int]) -> bool: if not nums or len(nums) < 3: return False # min_1 < min_2 min_1, min_2 = math.
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. Note You must do this in-place without making a copy of the array. Minimize the total number of operations. Credit Special thanks to @jianchao.
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1 Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2 Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4 Note You may assume k is always valid, 1 ≤ k ≤ array's length. Solution Average time complexity: O(n) if we don’t need the sorted output, otherwise O(n+kLogk)
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? Observation: Solution: /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (head == null) return null; ListNode slow = head; ListNode fast = head; boolean hasCycle = false; while (slow.
Given a linked list, determine if it has a cycle in it. Follow-up Can you solve it without using extra space? Solution # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ slow = head fast = head while fast: # fast reaches the end, no cycle was detected if fast and not fast.