Given an array of meeting time intervals consisting of start and end timesContinue reading “[Leetcode]253. Meeting Rooms II”[[s1,e1],[s2,e2],...]
(si < ei), find the minimum number of conference rooms required. Example 1: Input:[[0, 30],[5, 10],[15, 20]]
Output: 2
[Leetcode problems]1488. Avoid Flood in The City
Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over theContinue reading “[Leetcode problems]1488. Avoid Flood in The City”nth
lake, thenth
lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake. Given an integer arrayrains
where:rains[i] > 0
means there will be rains over therains[i]
lake.rains[i] == 0
means there are no rains this day and you can choose one lake this day and dry it. Return an arrayans
where:ans.length == rains.length
ans[i] == -1
ifrains[i] > 0
.ans[i]
is the lake you choose to dry in theith
day ifrains[i] == 0
. If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array. Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4) Example 1: Input: rains = [1,2,3,4] Output: [-1,-1,-1,-1] Example 2: Input: rains = [1,2,0,0,2,1] Output: [-1,-1,2,1,-1,-1]
Top K problem – Sort, Heap, and Quickselect
Top K problem refers to those asking to find the Kth largest/smallest element or the top K largest/smallest items from an unsorted array. Sorting first and returning the Kth item definitely works, yet it yields O(n^2) or O(nlogn) time complexity. With heap or quickselect, O(n) is achievable.
Continue reading “Top K problem – Sort, Heap, and Quickselect”