Sliding Window Maximum

Sliding Window Maximum

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Example

For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8] , return the maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Challenge

o(n) time and O(k) memory

Solution:

1. 首先这道题最容易想到得是用heap做,维护一个heap,但是sliding window需要删除node,于是如果用HashHeap的话可以将时间复杂度降到O(nlogn). 即每次slide一次用logn时间添加结点再用logn时间删除结点。

2. 第二个方法是线性的 需要用到Deque即双端队列。比较难想到。

做法是:先考虑用stack,就是每次扫到新node时,先看stack.peek是不是比node小,如果小得话就把peek pop出去。直到peek比node小时,把node push进stack

然后此题因为需要每当slide window时,要把第一个数remove掉,这就需要用到deque,因为第一个数往往是在栈底。

public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0 || nums.length < k) {
        return result;
    }
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerLast(0);
    for (int i = 1; i < k; i++) {
        addElement(deque, i, nums);
    }
    result.add(nums[deque.peekFirst()]);
    for (int i = 1; i < nums.length + 1 - k; i++) {
        removeElement(deque, i - 1);
        addElement(deque, i + k - 1, nums);
        result.add(nums[deque.peekFirst()]);
    }
    return result;
}
//when adding a new element i,
//if nums[i]>=peakLast, we should keep popping the peak until the peak <nums[i]
//then we push nums[i]
public void addElement(Deque<Integer> deque, int index, int[] nums) {
    while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[index]) {
        //pop the peak element
        deque.pollLast();
    }
    deque.offerLast(index);
}

//when removing element, only check if the first of the deck is the same index
//then remove it. It is likely that it has already been popped out of the deque.
public void removeElement(Deque<Integer> deque, int index) {
    if (index == deque.peekFirst()) {
        deque.pollFirst();
    }
}

 

FacebookTwitterGoogle+Share

Sliding Window Median

Sliding Window Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]

At first the window is at the start of the array like this

[ | 1,2,7 | ,8,5] , return the median 2;

then the window move one step forward.

[1, | 2,7,8 | ,5], return the median 7;

then the window move one step forward again.

[1,2, | 7,8,5 | ], return the median 7;

Challenge

O(nlog(n)) time

Solution: 用分别用两个heap来维护这个median结构,左边一个maxHeap,右边一个minHeap,在加上当中一个median数值,两个Heap的size差最多为1,即leftSize==rightSize||leftSize+1==rightSize.

首先是要先初始化这个结构,把前k个数放进去,接下里window每向右移一格,等于是加上第nums[i+k-1] 然后 remove nums[i-1]。

注意的是:java里有heap的实现,可用PriorityQueue然后可以定义Comparator, 默认是minHeap, 如果要用maxHeap要自己写一个comparator传入constructor. 但是PriorityQueue的remove方法是O(n)的 即每次remove需要遍历一遍这个Heap找到那个数再Remove,面试时可以和面试官讨论,这一步可以用HashHeap来做,这样remove变成了O(logn), (找到这个数是O(1), remove相当于和最后一个数swap 然后siftdown操作所以是O(logn)).

如果用HashHeap的话,整个Time Complexity就是O(nlogn).

 

public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0 || nums.length < k) {
        return result;
    }
    PriorityQueue<Integer> leftMaxHeap = new PriorityQueue<>(1, new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            if (a < b) {
                return 1;
            } else if (a == b) {
                return 0;
            } else {
                return -1;
            }
        }
    });
    PriorityQueue<Integer> rightMinHeap = new PriorityQueue<>();
    int median = nums[0];
    //init the two heaps for the first k elements
    for (int i = 1; i < k; i++) {
        median = addElement(nums, i, median, leftMaxHeap, rightMinHeap);
    }
    result.add(median);
    //start moving the window forward
    for (int i = 1; i <= nums.length - k; i++) {
        //add nums[i+k-1]
        median = addElement(nums, i + k - 1, median, leftMaxHeap, rightMinHeap);
        //remove nums[i-1]
        median = removeElement(nums, i - 1, median, leftMaxHeap, rightMinHeap);
        result.add(median);
    }

    return result;
}

public int addElement(int[] nums, int index, int median,
                      PriorityQueue<Integer> leftMaxHeap, PriorityQueue<Integer> rightMinHeap) {
    //the left heap can only be the same size as the right heap
    //or left size + 1 = right size
    if (leftMaxHeap.size() == rightMinHeap.size()) {
        if (nums[index] < median) {
            leftMaxHeap.offer(nums[index]);
            rightMinHeap.offer(median);
            median = leftMaxHeap.poll();
        } else {
            rightMinHeap.offer(nums[index]);
        }
    } else {
        if (nums[index] <= median) {
            leftMaxHeap.offer(nums[index]);
        } else {
            leftMaxHeap.offer(median);
            rightMinHeap.offer(nums[index]);
            median = rightMinHeap.poll();
        }
    }
    return median;
}

public int removeElement(int[] nums, int index, int median,
                         PriorityQueue<Integer> leftMaxHeap, PriorityQueue<Integer> rightMinHeap) {
    //the left heap can only be the same size as the right heap
    //or left size + 1 = right size
    if (leftMaxHeap.size() == rightMinHeap.size()) {
        if (nums[index] == median) {
            median = leftMaxHeap.poll();
        } else if (nums[index] < median) {
            leftMaxHeap.remove(nums[index]);
        } else {
            rightMinHeap.remove(nums[index]);
            if (!leftMaxHeap.isEmpty()) {
                rightMinHeap.offer(median);
                median = leftMaxHeap.poll();
            }
        }
    } else {
        if (nums[index] == median) {
            median = rightMinHeap.poll();
        } else if (nums[index] <= median) {
            leftMaxHeap.remove(nums[index]);
            if (!rightMinHeap.isEmpty()) {
                leftMaxHeap.offer(median);
                median = rightMinHeap.poll();
            }
        } else {
            rightMinHeap.remove(nums[index]);
        }
    }
    return median;
}

Longest Increasing Continuous subsequence I & II

Longest Increasing Continuous subsequence I 

Give you an integer array (index from 0 to n-1, where n is the size of this array),find the longest increasing continuous subsequence in this array. (The definition of the longest increasing continuous subsequence here can be from right to left or from left to right)

Example

For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.

For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4.

Note

O(n) time and O(1) extra space.

Solution:

Longest Increasing Continuous subsequence II

Give you an integer matrix (with row size n, column size m),find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

Example

Given a matrix:

<code>[
  [1 ,2 ,3 ,4 ,5],
  [16,17,24,23,6],
  [15,18,25,22,7],
  [14,19,20,21,8],
  [13,12,11,10,9]
]
</code>

return 25

Challenge

O(nm) time and memory.

Solution:

Longest Increasing Subsequence

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Example

For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What’s the definition of longest increasing subsequence?

* The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

* https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Solution: DP O(n^2)

lis[i]表示结尾为nums[i]的子序列的最长长度。

所以lis[i] =for all the j<i && nums[j]<=nums[i] max(lis[j])+1

其实还有可以优化为lis[i] = lis[j] +1 where nums[j] 是比nums[i]小的数里最大的一个

public int longestIncreasingSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    //lis[i] means the lis of nums[0-i] which i is the last element selected in the lis
    int[] lis = new int[nums.length];
    int maxLis = 0;
    for (int i = 0; i < nums.length; i++) {
        lis[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] >= nums[j]) {
                lis[i] = Math.max(lis[j] + 1, lis[i]);
            }
        }
        maxLis = Math.max(maxLis, lis[i]);
    }
    return maxLis;
}

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Note

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: O(n) Time 先参考 Best Time to Buy and Sell Stock I 的做法

这次的不同点在与要做两次交易,所以我们要找一个分界点,分别算左右两边的一次交易利润和的最大值。所以我们可以做Best Time to Buy and Sell Stock I两次

第一次是从左到右扫[0-i]区间,也就是先确定buyDay,然后根据每个prices[i]来确定sellDay。

第二次是从右到左扫[i-end]区间,也就是先确定sellDay,然后根据每个prices[i]来确定buyDay。

所以这两个循环时间都是O(n)

最后我们要用一个循环来设分界点,然后取

max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])

注意这个max不是最终答案,假设只有两天[1,2] 这种情况算下来是0,因为分界点两边都是1天不足以完成交易,而且有可能的情况是第一天买入,最后一天买进,这种情况按两次交易算也无法取到最大值,所以最后结果还要考虑到只做一次交易的情况,因为没有规定必须做两次交易

Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);

这一部分的时间复杂度也是O(n)

所以整体的时间复杂度就是O(n)

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int length = prices.length;
    int[] maxProfitEndedAt = new int[length];
    int[] maxProfitStartedFrom = new int[length];

    //get the max profit from 0 to i with one transaction
    maxProfitEndedAt[0] = 0;
    int buyDay = 0;
    for (int i = 1; i < length; i++) {
        maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
        if (prices[i] < prices[buyDay]) {
            buyDay = i;
        }
    }
    //get the max profit form i to length-1 with one transaction
    maxProfitStartedFrom[length - 1] = 0;
    int sellDay = length - 1;
    for (int i = length - 2; i >= 0; i--) {
        maxProfitStartedFrom[i] = Math.max(maxProfitStartedFrom[i + 1], prices[sellDay] - prices[i]);
        if (prices[i] > prices[sellDay]) {
            sellDay = i;
        }
    }
    //to have two transactions
    //pick a pivot day i, to get the max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])
    int maxWithTwoTransaction = 0;
    for (int i = 0; i < length - 2; i++) {
        maxWithTwoTransaction = Math.max(maxWithTwoTransaction,
                                         maxProfitEndedAt[i] + maxProfitStartedFrom[i + 1]);
    }
    return Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);
}

 

Maximal Square

Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

Example

For example, given the following matrix:

<code>1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
</code>

Return 4.

Solution: DP side[i][j] 表示以(i,j)这个点为右下角可以组成的最大square的边长

由下图可知,大正方形由三个小正方形和(i,j)这个点这个点决定

maximum square草图

side[i][j] = min(side[i-1][j-1], side[i][j-1], side[i-1][j]) +1 //when matrix[i][j]==1

= 0 //when matrix[i][j] = 0

public int maxSquare(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    //side[i][j] = the length of the max square which (i,j) is the at right bottom corner.
    int[][] side = new int[matrix.length][matrix[0].length];
    int max = 0;
    for (int i = 0; i < matrix.length; i++) {
        side[i][0] = matrix[i][0];
        max = Math.max(max, side[i][0]);
    }
    for (int j = 0; j < matrix[0].length; j++) {
        side[0][j] = matrix[0][j];
        max = Math.max(max, side[0][j]);
    }

    for (int i = 1; i < matrix.length; i++) {
        for (int j = 1; j < matrix[i].length; j++) {
            if (matrix[i][j] == 0) {
                side[i][j] = 0;
            } else {
                side[i][j] = Math.min(side[i - 1][j], Math.min(side[i][j - 1], side[i - 1][j - 1])) + 1;
                max = Math.max(max, side[i][j]);
            }
        }
    }
    return max * max;
}

House Robber

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example

Given [3, 8, 4], return 8.

Challenge

O(n) time and O(1) memory.

Solution: max[i]表示从0-i个房子里,要抢房子i的最大值

max[i] = Math.max(max[i – 2] + A[i], max[i – 1]);

public long houseRobber(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    if (A.length == 1) {
        return A[0];
    }
    if (A.length == 2) {
        return Math.max(A[0], A[1]);
    }

    //max[i] = for [0-i], the max value if rob house i
    long[] max = new long[A.length];
    max[0] = A[0];
    max[1] = A[1];
    for (int i = 2; i < A.length; i++) {
        max[i] = Math.max(max[i - 2] + A[i], max[i - 1]);
    }
    return Math.max(max[A.length - 1], max[A.length - 2]);
}

Find the Connected Component in the Undirected Graph

Find the Connected Component in the Undirected Graph

Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.)

Example

Given graph:

A------B  C
 \     |  | 
  \    |  |
   \   |  |
    \  |  |
      D   E

Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B,D}, {C,E}

Solution: BFS

public List<List<Integer>> connectedSet(ArrayList<UndirectedGraphNode> nodes) {
    List<List<Integer>> result = new ArrayList<>();
    if (nodes == null || nodes.size() == 0) {
        return result;
    }
    Queue<UndirectedGraphNode> q = new LinkedList<>();
    q.offer(nodes.get(0));
    List<Integer> component = new ArrayList<>();
    Set<UndirectedGraphNode> visited = new HashSet<>();
    while (!nodes.isEmpty()) {
        if (q.isEmpty()) {
            Collections.sort(component);
            result.add(new ArrayList<>(component));
            q.offer(nodes.get(0));
            component = new ArrayList<>();
        } else {
            UndirectedGraphNode curr = q.poll();
            if (!visited.contains(curr)) {
                visited.add(curr);
                nodes.remove(curr);
                component.add(curr.label);
                for (UndirectedGraphNode neighbor : curr.neighbors) {
                    q.offer(neighbor);
                }
            }
        }
    }
    if (!component.isEmpty()) {
        result.add(component);
    }
    return result;
}