花花酱 LeetCode 715. Range Module

By zxi on October 22, 2017

Problem:

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example 1:

addRange(10, 20): null

removeRange(14, 16): null

queryRange(10, 14): true (Every number in [10, 14) is being tracked)

queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)

queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Note:

A half open interval [left, right) denotes all real numbers left <= x < right.
0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
The total number of calls to addRange in a single test case is at most 1000.
The total number of calls to queryRange in a single test case is at most 5000.
The total number of calls to removeRange in a single test case is at most 1000.

Idea:

map / ordered ranges

Solution:

C++ / vector

// Author: Huahua

// Runtime: 276 ms

class RangeModule {

public:

RangeModule() {}

void addRange(int left, int right) {

vector<pair<int, int>> new_ranges;

bool inserted = false;

for (const auto& kv : ranges_) {

if (kv.first > right && !inserted) {

new_ranges.emplace_back(left, right);

inserted = true;

}

if (kv.second < left || kv.first > right) {

new_ranges.push_back(kv);

} else {

left = min(left, kv.first);

right = max(right, kv.second);

}

if (!inserted) new_ranges.emplace_back(left, right);

ranges_.swap(new_ranges);

}

bool queryRange(int left, int right) {

const int n = ranges_.size();

int l = 0;

int r = n - 1;

// Binary search

while (l <= r) {

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

if (ranges_[m].second < left)

l = m + 1;

else if (ranges_[m].first > right)

r = m - 1;

else

return ranges_[m].first <= left && ranges_[m].second >= right;

}

return false;

}

void removeRange(int left, int right) {

vector<pair<int, int>> new_ranges;

for (const auto& kv : ranges_) {

if (kv.second <= left || kv.first >= right) {

new_ranges.push_back(kv);

} else {

if (kv.first < left)

new_ranges.emplace_back(kv.first, left);

if (kv.second > right)

new_ranges.emplace_back(right, kv.second);

}

ranges_.swap(new_ranges);

}

vector<pair<int, int>> ranges_;

};

C++ / map

// Author: Huahua

// Runtime: 199 ms

class RangeModule {

public:

RangeModule() {}

void addRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// At least one range overlapping with [left, right)

if (l != r) {

// Merge intervals into [left, right)

auto last = r; --last;

left = min(left, l->first);

right = max(right, last->second);

// Remove all overlapped ranges

ranges_.erase(l, r);

}

// Add a new/merged range

ranges_[left] = right;

}

bool queryRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// No overlapping range

if (l == r) return false;

return l->first <= left && l->second >= right;

}

void removeRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// No overlapping range

if (l == r) return;

auto last = r; --last;

int start = min(left, l->first);

int end = max(right, last->second);

// Delete overlapping ranges

ranges_.erase(l, r);

if (start < left) ranges_[start] = left;

if (end > right) ranges_[right] = end;

}

private:

typedef map<int, int>::iterator IT;

map<int, int> ranges_;

void getOverlapRanges(int left, int right, IT& l, IT& r) {

l = ranges_.upper_bound(left);

r = ranges_.upper_bound(right);

if (l != ranges_.begin())

if ((--l)->second < left) l++;

}

};

Related Problems:

花花酱 LeetCode 347. Top K Frequent Elements

By zxi on October 22, 2017

Problem:

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Idea:

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

// Author: Huahuas

// Running time: 16 ms

class Solution {

public:

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

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

priority_queue<pair<int, int>> q;

for (const auto& pair : count) {

q.emplace(-pair.second, pair.first);

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

}

vector<int> ans;

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

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

q.pop();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 56 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> x[0] - y[0]);

for (Integer num : counts.keySet()) {

queue.offer(new int[]{counts.get(num), num});

if (queue.size() > k) queue.poll();

}

List<Integer> ans = new ArrayList<>();

for (int i = 0; i < k; ++i)

ans.add(queue.poll()[1]);

return ans;

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

h = []

for num in counts.keys():

heapq.heappush(h, (counts[num], num))

if len(h) > k: heapq.heappop(h)

return [heapq.heappop(h)[1] for i in range(k)]

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

class Solution {

public:

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

unordered_map<int, int> count;

int max_freq = 1;

for (const int num : nums)

max_freq = max(max_freq, ++count[num]);

map<int, vector<int>> buckets;

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (int i = max_freq; i >= 1; --i) {

auto it = buckets.find(i);

if (it == buckets.end()) continue;

ans.insert(ans.end(), it->second.begin(), it->second.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

C++/array

class Solution {

public:

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

unordered_map<int, int> count;

for (const int num : nums)

++count[num];

vector<vector<int>> buckets(nums.size() + 1);

for (const auto& kv : count)

buckets[kv.second].push_back(kv.first);

vector<int> ans;

for (auto it = buckets.rbegin(); it != buckets.rend(); ++it) {

const vector<int>& keys = *it;

if (keys.empty()) continue;

ans.insert(ans.begin(), keys.begin(), keys.end());

if (ans.size() == k) return ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 23 ms

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

List[] buckets = new List[nums.length + 1];

Map<Integer, Integer> counts = new HashMap<>();

for (int num : nums)

counts.put(num, counts.getOrDefault(num, 0) + 1);

for (int num : counts.keySet()) {

int count = counts.get(num);

if (buckets[count] == null)

buckets[count] = new ArrayList<Integer>();

buckets[count].add(num);

}

List<Integer> ans = new ArrayList<>();

for (int i = buckets.length - 1; i > 0 && ans.size() < k; --i) {

if (buckets[i] != null) ans.addAll(buckets[i]);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def topKFrequent(self, nums, k):

counts = collections.Counter(nums)

buckets = [[] for _ in range(len(nums) + 1)]

for num in counts.keys():

buckets[counts[num]].append(num)

ans = []

for i in range(len(nums), 0, -1):

ans += buckets[i]

if len(ans) == k: return ans

return ans

Solution 1: Topological Sort

C++

// Author: Huahua

// Time complexity: O(n)

// Runtime: 12 ms

class Solution {

public:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

graph_ = vector<vector<int>>(numCourses);

for(const auto& p : prerequisites)

graph_[p.first].push_back(p.second);

// states: 0 = unkonwn, 1 == visiting, 2 = visited

vector<int> v(numCourses, 0);

for(int i = 0; i < numCourses; ++i)

if(dfs(i, v)) return false;

return true;

}

private:

vector<vector<int>> graph_;

bool dfs(int cur, vector<int>& v) {

if(v[cur] == 1) return true;

if(v[cur] == 2) return false;

v[cur] = 1;

for(const int t : graph_[cur])

if(dfs(t, v)) return true;

v[cur] = 2;

return false;

}

};

Java

// Author: Huahua

// Runtime: 6 ms

// HashMap is slower than ArrayList in this problem.

class Solution {

public boolean canFinish(int numCourses, int[][] prerequisites) {

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

for (int i = 0; i < numCourses; ++i)

graph.add(new ArrayList<Integer>());

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

int course = prerequisites[i][0];

int prerequisite = prerequisites[i][1];

graph.get(course).add(prerequisite);

}

int[] visited = new int[numCourses];

for (int i = 0; i < numCourses; ++i)

if (dfs(i, graph, visited)) return false;

return true;

}

private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited) {

if (visited[curr] == 1) return true;

if (visited[curr] == 2) return false;

visited[curr] = 1;

for (int next : graph.get(curr))

if (dfs(next, graph, visited)) return true;

visited[curr] = 2;

return false;

}

Solution 2: DFS Finding cycles

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Time complexity: O(n^2)

// Runtime: 179 ms

class Solution {

public:

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

graph_.clear();

for(const auto& p : prerequisites)

graph_[p.first].insert(p.second);

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

vector<int> visited(numCourses, 0);

if (cycle(i, i, visited)) return false;

}

return true;

}

private:

unordered_map<int, unordered_set<int>> graph_;

bool cycle(int start, int curr, vector<int>& visited) {

if (curr == start && visited[start]) return true;

if (!graph_.count(curr)) return false;

for (const int next : graph_.at(curr)) {

if (visited[next]) continue;

visited[next] = true;

if (cycle(start, next, visited)) return true;

}

return false;

}

};

Related Pr0blems:

花花酱 LeetCode 149. Max Points on a Line

By zxi on October 19, 2017

Problem:

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Idea:

count by slope

Time complexity: O(n^2)

Space complexity: O(n)

Solution:

C++ / pair

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int maxPoints(vector<Point>& points) {

int n = points.size();

int ans = 0;

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

std::map<std::pair<int,int>, int> count;

int same_points = 1;

int max_points = 0;

for (int j = i + 1; j < n; ++j) {

const Point& p1 = points[i];

const Point& p2 = points[j];

if (p1.x == p2.x && p1.y == p2.y)

++same_points;

else

max_points = max(max_points, ++count[getSlope(p1, p2)]);

}

ans = max(ans, same_points + max_points);

}

return ans;

}

private:

// slope dy/dx : <dy, dx>

std::pair<int, int> getSlope(const Point& p1, const Point& p2) {

const int dx = p2.x - p1.x;

const int dy = p2.y - p1.y;

// horizontal line

if (dy == 0) return { p1.y, 0 };

// vertical line

if (dx == 0) return { 0, p1.x };

const int d = gcd(dx, dy);

return { dy / d, dx / d };

}

int gcd(int m, int n) {

return n == 0 ? m : gcd(n, m % n);

}

};

C++ / long

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int maxPoints(vector<Point>& points) {

int n = points.size();

int ans = 0;

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

unordered_map<long, int> count;

int same_points = 1;

int max_points = 0;

const Point& p1 = points[i];

for (int j = i + 1; j < n; ++j) {

const Point& p2 = points[j];

if (p1.x == p2.x && p1.y == p2.y)

++same_points;

else

max_points = max(max_points, ++count[getSlope(p1, p2)]);

}

ans = max(ans, same_points + max_points);

}

return ans;

}

private:

// slope dy/dx : dy << 32 | dx

long getSlope(const Point& p1, const Point& p2) {

const int dx = p2.x - p1.x;

const int dy = p2.y - p1.y;

// horizontal line

if (dy == 0) return static_cast<long>(p1.y) << 32 | 0;

// vertical line

if (dx == 0) return static_cast<long>(0)<< 32 | p1.x;

const int d = __gcd(dx, dy);

return static_cast<long>(dy / d) << 32 | (dx / d);

}

};

花花酱 LeetCode 715. Range Module

花花酱 LeetCode 347. Top K Frequent Elements

Solution 2: Priority queue / max heap

C++

Java

Python

Solution 3: Bucket Sort

C++/hashmap

C++/array

Java

Python

Related Problems

花花酱 LeetCode 692. Top K Frequent Words

花花酱 LeetCode 207. Course Schedule

Solution 1: Topological Sort

C++

Java

Solution 2: DFS Finding cycles

C++

Related Pr0blems:

花花酱 LeetCode 149. Max Points on a Line

Solution:

C++ / pair

C++ / long

Huahua's Tech Road

花花酱 LeetCode 715. Range Module

花花酱 LeetCode 347. Top K Frequent Elements

Solution 2: Priority queue / max heap

C++

Java

Python

Solution 3: Bucket Sort

C++/hashmap

C++/array

Java

Python

Related Problems

花花酱 LeetCode 692. Top K Frequent Words

花花酱 LeetCode 207. Course Schedule

Solution 1: Topological Sort

C++

Java

Solution 2: DFS Finding cycles

C++

Related Pr0blems:

花花酱 LeetCode 149. Max Points on a Line

Solution:

C++ / pair

C++ / long