Leetcode 239. Sliding window maximum

Sept. 13, 2018

Introduction 

I like to write a solution for the hard level algorithm called sliding window maximum. My last submission on Leetcode is more than 15 month ago.

My practice

It is important for me to review what I have practiced, and learn from my own experience. I shared the code I wrote in August, 2015. Here is the link.

Sunday - Algorithm day (4) - 25 algorithms study

Feb. 13, 2016

  Algorithm Sunday, work on it, not just Google. Think by yourself first, work hard on it first.

1. Maximum number of overlapping intervals

For example – { (0,2), (3, 7), (4,6), (7,8), (1,5) }. The maximum number of intervals overlapped is 3 during (4,5).

Recall Leetcode merge interval

Good solutions maybe: Using two arrays, one is to sort interval by start, another is by end.

2. Merge two sorted linked lists

Recursive solution

Itearativesolution 1

Iteration solution 2

Julia's practice:

Recursivesolution

3. LRU Cache Miss

Read blogs about LRU first:

program creek 

Leetcode discussion

This blog is excellent. Julia will write the implementation in C#.

Jeffwan

acmerblog

jiuzhang

4. Leetcode 64: Minimum Path Sum

http://codingmelon.com/2015/12/12/minimal-path-sum-from-root-to-leaves/

5. Disk scheduling algorithm: Round Robin

6. K closest point

Read blogs on this website:

blog 

Julia could not believe that she always reads excellent code, and then, also great stories how technologies are different.

shepherdyuan blog 1

shepherdyuan blog 2

7. Rearrange array - 区分正负数

 8. Window sum 

countinversions 

9. Rearrange array in alternating positive negative items with O(1) extra space

shepherdyuan 

idea: 如果用O(1)的话那需要有一个pointer指向第一个错误的数字，比如偶数index的正数和奇数index的负数。然后碰到当前的数如果符号和错误的那个数不一样，那就rotate那段sub array。

10. Iterative binary tree traversal

11. Binary tree insert/search/update

12. Trie - Java Implementation

13. Moore's voting algorithm

14. First Missing Positive

O(n)的解法，很巧妙，利用数组的特性，暂且称之为“派送法”哈哈，派送A[i]到A[A[i]-1]。

Decimal representation 

15. Implement list, stack and map

16. HeapSort

Read 10 minutes lecture notes. 

17. Sorting algorithms

about partition, quick sorting:

Julia'sblog and her quick sorting partition explanation with a test case.

quicksort algorithm practice

18. Merge Intervals

上来给一串start time － end time，格式是Apr 2010 － Mar 2011这种，要求计算出这些时间的总跨度，重叠的跨度不重复计算。举例：["Apr 2010 - Dec 2010", "Aug 2010 - Dec 2010", "Jan 2011 - Mar 2011"]这一个string数组，结果为（12-4+3-1）＝10个月。一出这题有点蒙，感觉代码量很大，时间又不多了，只能硬着头皮上。写完string->time的解析函数之后，发现其实就是一道mergeinterval的题.

19. 写一个函数，给一个node，代表一个人，返回他linkedin 或者facebook network

BFS - graph traversal 

如果一个用户 用这个api，那个node 的朋友很多，million to billion 级别，那么response感觉很慢怎么办? 

20. validBST

如果有duplicate 而且 duplicate return false 的时候会 failed 一个corner case

21. Given a tree, find the smallest subtree that contains all of the tree's deepest nodes.
                  a
               /  |  \
             b   c   d
           /   \       |
         e      f      g
       /       /  \
      h      i     j

depth of tree: 4
deepest nodes:[h,i,j]
least common ancestor of [h,i,j]:
return: b

leetcode上面哪个lowest common ancestor of binary tree

22. insert node in circular list, 

23. LRU miss count

输入 maxSize， input int array 

输出是miss cout

example：   size = 4， input array   【1，2，3，4，5，4，1】

1 miss

2 miss

3 miss

4 miss

5 miss  替换 1

4 hit    把4提前到第一位

1 miss  替换 2

大概就是这样。。。

February 2, 2016

Read blogs:

blog 1

blog 2 

February 2, 2016

http://blog.csdn.net/rollycoris/article/category/5884445

http://blog.csdn.net/rollycoris/article/category/5884447

Julia's practice

24.

8 个 cell  

example：【0，1，1，1，1，1，1，0】

规律每天变化：两边相同--》0， 两边不同--》1

输入：8个cell，  天数n

问n天后cell长啥样

ps：两端cell两边假设const = 0；

小example：

day0:  (0)0,1,1,1(0)

day1:  (0)1,1,0,1(0)

day2:  (0)1,1,0,0(0)

25. Longest path from root to leaf in binary tree

Diameter

Feb. 17, 2016

Check out topcoder training about testing cases, maybe, use it for a while for practice.

a top coder's blog

https://www.zhihu.com/question/40463511

Leetcode 239: sliding window maximum

August 7, 2015

Julia spent 20-30 minutes to think about solution first, and read the following blogs, write some code as well. She practised three time using C# and here are the details.

C# practices

Here are 3 practice Julia did using LinkedList, List and SortedList. 

1. C# LinkedList

C# code implementation

2. C# List<int>

C# practice code

3. C# SortedList

C# practice code

More detail

Double ended queue is implemented using C# LinkedList class, here is Julia's C# practice code: C# code implementation

Julia chose to study the blog on Leetcode: sliding window maximum

C# code implementation (C# does not have deque class, so using C# List<int>, 

convert Python code implementation to C#, time limit exceeded)

Good workout on C# List<int>, Julia experienced different style on removing head element if out of sliding window. 

C# practice code 

Julia chose to read the blog on geekforgeek.com called "maximum of all subarrays of size k". 

Method A: naive solution, time complexity O(nw)
C# practice code is here. 

Method B: using Self-Balancing Tree (Time complexity: O(nk), need to write c# code)

C# practice code is here. 

4. blog:

http://yuanhsh.iteye.com/blog/2190852

http://n00tc0d3r.blogspot.ca/2013/04/sliding-window-maximum.html

Good comment about Deque:

We can use a Deque which allow insertions/deletions on both ends. For a Deque implemented by Circular Array/Buffer or Double Linked List, the basic insert/delete operations run in constant time.

discussion of using heap: 

 The first thought might be heap.

By maintaining a heap for all numbers in the window can give us a O(nlogw)-time solution, where

• building up a heap for initial window takes time O(wlogw)
• when window moves to the next number, each insertion and deletion take time O(logw) and there are n-w moves in total.
• after updating the heap, findMax only takes time O(1) since we know the top of heap is the largest.
•  

So, if w << n, the performance of this solution is good, close to O(n); but if w is not that small, say w = n/3 or n/4, the running time goes up to O(nlogn).

5. blog:   C++ code 

using C++ multiset in the above solution, so try to convert it to C# class using SortedList

C# practice code

6. blog:
http://www.mamicode.com/info-detail-927510.html

Convert Java Script code to C#; I spent over 12 months to try to be expert on Java Script, so much fun to read the Java Script code again, and enjoyed the blog about the analysis. 

Others:
https://github.com/jianminchen/slidingWindowMaximum/blob/master/slidingWindowMaximu5.cs

http://www.cnblogs.com/grandyang/p/4656517.html

http://techinpad.blogspot.ca/2015/05/lintcodeleetcode-sliding-window-maximum.html