Posts published in “Heap”

花花酱 LeetCode 778. Swim in Rising Water

By zxi on January 31, 2019

On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).

Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.

You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Example 1:

Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Note:

2 <= N <= 50.
grid[i][j] is a permutation of [0, …, N*N – 1].

Solution 1: Dijkstra’s Algorithm

Time complexity: O(n^2*logn)
Space complexity: O(n^2)

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int swimInWater(vector<vector<int>>& grid) {

const int n = grid.size();

priority_queue<pair<int, int>> q; // {-time, y * N + x}

q.push({-grid[0][0], 0 * n + 0});

vector<int> seen(n * n);

vector<int> dirs{-1, 0, 1, 0, -1};

seen[0 * n + 0] = 1;

while (!q.empty()) {

auto node = q.top(); q.pop();

int t = -node.first;

int x = node.second % n;

int y = node.second / n;

if (x == n - 1 && y == n - 1) return t;

for (int i = 0; i < 4; ++i) {

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;

if (seen[ty * n + tx]) continue;

seen[ty * n + tx] = 1;

q.push({-max(t, grid[ty][tx]), ty * n + tx});

}

return -1;

}

};

Solution 2: Binary Search + BFS

Time complexity: O(2logn * n^2)
Space complexity: O(n^2)

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int swimInWater(vector<vector<int>>& grid) {

const int n = grid.size();

auto hasPath = [&grid, n](int t) {

if (grid[0][0] > t) return false;

queue<int> q;

vector<int> seen(n * n);

vector<int> dirs{1, 0, -1, 0, 1};

q.push(0);

while (!q.empty()) {

const int x = q.front() % n;

const int y = q.front() / n;

q.pop();

if (x == n - 1 && y == n - 1) return true;

for (int i = 0; i < 4; ++i) {

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx >= n || ty >= n || grid[ty][tx] > t) continue;

const int key = ty * n + tx;

if (seen[key]) continue;

seen[key] = 1;

q.push(key);

}

return false;

};

int l = 0;

int r = n * n;

while (l < r) {

int m = l + (r - l) / 2;

if (hasPath(m)) {

r = m;

} else {

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 703. Kth Largest Element in a Stream

By zxi on July 12, 2018

Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Note:
You may assume that nums‘ length ≥ k-1 and k ≥ 1.

Solution: BST / Min Heap

Time complexity: O(nlogk)

Space complexity: O(k)

C++ / BST

// Author: Huahua

// Running time: 32 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.insert(val);

if (s_.size() > k_)

s_.erase(s_.begin());

return *s_.begin();

}

private:

const int k_;

multiset<int> s_;

};

C++ / Min Heap

// Author: Huahua

// Running time: 28 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.push(val);

if (s_.size() > k_)

s_.pop();

return s_.top();

}

private:

const int k_;

priority_queue<int, vector<int>, greater<int>> s_; // min heap

};

花花酱 LeetCode 239. Sliding Window Maximum

By zxi on January 24, 2018

题目大意：给你一个数组，让你输出移动窗口的最大值。

Problem:

https://leetcode.com/problems/sliding-window-maximum/

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Idea:

Solution 1: Brute Force

Time complexity: O((n – k + 1) * k)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 180 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

for (int i = k - 1; i < nums.size(); ++i) {

ans.push_back(*max_element(nums.begin() + i - k + 1, nums.begin() + i + 1));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 80 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return new int[0];

int[] ans = new int[nums.length - k + 1];

for (int i = k - 1; i < nums.length; ++i) {

int maxNum = nums[i];

for (int j = 1; j < k; ++j)

if (nums[i - j] > maxNum) maxNum = nums[i - j];

ans[i - k + 1] = maxNum;

}

return ans;

}

Python

"""

Author: Huahua

Running time: 1044 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

if not nums: return []

return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

Solution 2: BST

Time complexity: O((n – k + 1) * logk)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

if (nums.empty()) return ans;

multiset<int> window(nums.begin(), nums.begin() + k - 1);

for (int i = k - 1; i < nums.size(); ++i) {

window.insert(nums[i]);

ans.push_back(*window.rbegin());

if (i - k + 1 >= 0)

window.erase(window.equal_range(nums[i - k + 1]).first);

}

return ans;

}

};

Solution 3: Monotonic Queue

Time complexity: O(n)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 70 ms

class MonotonicQueue {

public:

void push(int e) {

while(!data_.empty() && e > data_.back()) data_.pop_back();

data_.push_back(e);

}

void pop() {

data_.pop_front();

}

int max() const { return data_.front(); }

private:

deque<int> data_;

};

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

MonotonicQueue q;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

q.push(nums[i]);

if (i - k + 1 >= 0) {

ans.push_back(q.max());

if (nums[i - k + 1] == q.max()) q.pop();

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 65 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> index;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

while (!index.empty() && nums[i] >= nums[index.back()]) index.pop_back();

index.push_back(i);

if (i - k + 1 >= 0) ans.push_back(nums[index.front()]);

if (i - k + 1 >= index.front()) index.pop_front();

}

return ans;

}

};

C++ V3

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> q;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

while (!q.empty() && nums[i] > q.back()) q.pop_back();

q.push_back(nums[i]);

const int s = i - k + 1;

if (s < 0) continue;

ans.push_back(q.front());

if (nums[s] == q.front()) q.pop_front();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 19 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return nums;

int[] ans = new int[nums.length - k + 1];

Deque<Integer> indices = new LinkedList<>();

for (int i = 0; i < nums.length; ++i) {

while (indices.size() > 0 && nums[i] >= nums[indices.getLast()])

indices.removeLast();

indices.addLast(i);

if (i - k + 1 >= 0) ans[i - k + 1] = nums[indices.getFirst()];

if (i - k + 1 >= indices.getFirst()) indices.removeFirst();

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 238 ms

"""

class MaxQueue:

def __init__(self):

self.q_ = collections.deque()

def push(self, e):

while self.q_ and e > self.q_[-1]: self.q_.pop()

self.q_.append(e)

def pop(self):

self.q_.popleft()

def max(self):

return self.q_[0]

class Solution:

def maxSlidingWindow(self, nums, k):

q = MaxQueue()

ans = []

for i in range(len(nums)):

q.push(nums[i])

if i >= k - 1:

ans.append(q.max())

if nums[i - k + 1] == q.max(): q.pop()

return ans

Python3 V2

"""

Author: Huahua

Running time: 193 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

indices = collections.deque()

ans = []

for i in range(len(nums)):

while indices and nums[i] >= nums[indices[-1]]: indices.pop()

indices.append(i)

if i >= k - 1: ans.append(nums[indices[0]])

if i - k + 1 == indices[0]: indices.popleft()

return ans

花花酱 LeetCode 692. Top K Frequent Words

By zxi on October 21, 2017

Problem:

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2

Output: ["i", "love"]

Explanation: "i" and "love" are the two most frequent words.

Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4

Output: ["the", "is", "sunny", "day"]

Explanation: "the", "is", "sunny" and "day" are the four most frequent words,

with the number of occurrence being 4, 3, 2 and 1 respectively.

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.

Follow up:

Try to solve it in O(n log k) time and O(n) extra space.

Idea:

Priority queue / min heap

Solution

C++ / priority_queue O(n log k) / O(n)

// Author: Huahua

// Runtime: 13 ms (< 90.31 %)

class Solution {

private:

typedef pair<string, int> Node;

typedef function<bool(const Node&, const Node&)> Compare;

public:

vector<string> topKFrequent(vector<string>& words, int k) {

unordered_map<string, int> count;

for (const string& word : words)

++count[word];

Compare comparator = [](const Node& a, const Node& b) {

// order by alphabet ASC

if (a.second == b.second)

return a.first < b.first;

// order by freq DESC

return a.second > b.second;

};

// Min heap by frequency

priority_queue<Node, vector<Node>, Compare> q(comparator);

// O(n*logk)

for (const auto& kv : count) {

q.push(kv);

if (q.size() > k) q.pop();

}

vector<string> ans;

while (!q.empty()) {

ans.push_back(q.top().first);

q.pop();

}

std::reverse(ans.begin(), ans.end());

return ans;

}

};

Related Problems

[解题报告] LeetCode 347. Top K Frequent Elements

花花酱 LeetCode 295. Find Median from Data Stream O(logn) + O(1)

By zxi on September 12, 2017

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) – Add a integer number from the data stream to the data structure.
double findMedian() – Return the median of all elements so far.

For example:

addNum(1)

addNum(2)

findMedian() = 1.5

addNum(3)

findMedian() = 2

Idea:

Min/Max heap
Balanced binary search tree

Time Complexity:

add(num): O(logn)

findMedian(): O(logn)

Solution1:

// Author: Huahua

// Running Time: 152 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder() {}

// l_.size() >= r_.size()

void addNum(int num) {

if (l_.empty() || num <= l_.top()) {

l_.push(num);

} else {

r_.push(num);

}

// Step 2: Balence left/right

if (l_.size() < r_.size()) {

l_.push(r_.top());

r_.pop();

} else if (l_.size() - r_.size() == 2) {

r_.push(l_.top());

l_.pop();

}

double findMedian() {

if (l_.size() > r_.size()) {

return static_cast<double>(l_.top());

} else {

return (static_cast<double>(l_.top()) + r_.top()) / 2;

}

private:

priority_queue<int, vector<int>, less<int>> l_; // max-heap

priority_queue<int, vector<int>, greater<int>> r_; // min-heap

};

Solution 2:

// Author: Huahua

// Running time: 172 ms

class MedianFinder {

public:

/** initialize your data structure here. */

MedianFinder(): l_(m_.cend()), r_(m_.cend()) {}

// O(logn)

void addNum(int num) {

if (m_.empty()) {

l_ = r_ = m_.insert(num);

return;

}

m_.insert(num);

const size_t n = m_.size();

if (n & 1) {

// odd number

if (num >= *r_) {

l_ = r_;

} else {

// num < *r_, l_ could be invalidated

l_ = --r_;

}

} else {

if (num >= *r_)

++r_;

else

--l_;

}

// O(1)

double findMedian() {

return (static_cast<double>(*l_) + *r_) / 2;

}

private:

multiset<int> m_;

multiset<int>::const_iterator l_; // current left median

multiset<int>::const_iterator r_; // current right median

};

Related Problems