花花酱 LeetCode 1157. Online Majority Element In Subarray

By zxi on August 10, 2019

Implementing the class MajorityChecker, which has the following API:

MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
int query(int left, int right, int threshold) has arguments such that:
- 0 <= left <= right < arr.length representing a subarray of arr;
- 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right]that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

1 <= arr.length <= 20000
1 <= arr[i] <= 20000
For each query, 0 <= left <= right < len(arr)
For each query, 2 * threshold > right - left + 1
The number of queries is at most 10000

Solution 0: Brute Force TLE

For each range, find the majority element in O(n) time / O(n) or O(1) space.

Solution 1: Cache the range result

Cache the result for each range: mode and frequency

Time complexity:
init: O(1)
query: O(|right – left|)
total queries: O(sum(right_i – left_i)), right_i, left_i are bounds of unique ranges.
Space complexity:
init: O(1)
query: O(20000)

C++

// Author: Huahua, 568ms, 39.6 MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {}

int query(int left, int right, int threshold) {

int key = left * 20000 + right;

if (!seen.count(key)) {

int c[20001] = {0};

int best = (right - left) / 2;

int best_num = -1;

for (int i = left; i <= right; ++i) {

if (++c[nums[i]] > best) {

best = c[nums[i]];

best_num = nums[i];

}

seen[key] = {best_num, best};

}

return seen[key].second >= threshold ? seen[key].first : -1;

}

private:

unordered_map<int, pair<int, int>> seen;

const vector<int>& nums;

};

Solution 2: HashTable + binary search

Preprocessing: use a hashtable to store the indices of each element. And sort by frequency of the element in descending order.
Query: iterator over (total_freq, num) pair, if freq >= threshold do a binary search to find the frequency of the given range for num in O(logn).

Time complexity:
Init: O(nlogn)
Query: worst case: O(nlogn), best case: O(logn)

C++

// Author: Huahua, 156 ms, 44.7MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {

const int max_n = *max_element(begin(nums), end(nums));

m = vector<vector<int>>(max_n + 1);

for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);

for (int n = 1; n <= max_n; ++n) {

if (m[n].size()) f.emplace_back(m[n].size(), n);

}

sort(rbegin(f), rend(f));

}

int query(int left, int right, int threshold) {

for (const auto& p : f) {

if (p.first < threshold) return -1;

int n = p.second;

const auto& idx = m[n];

int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);

if (count >= threshold) return n;

}

return -1;

}

private:

const vector<int>& nums;

vector<vector<int>> m; // num -> {indices}

vector<pair<int, int>> f; // {freq, num}

};

Solution 2+: Randomization

Randomly pick a num in range [left, right] and check its freq, try k (e.g. 30) times. If a majority element exists, you should find it with error rate 1/2^k.

Time complexity:
Init: O(n)
Query: O(30 * logn)
Space complexity: O(n)

C++

// Author: Huahua, 240ms, 45.6MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {

for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);

}

int query(int left, int right, int threshold) {

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

int n = nums[rand() % (right - left + 1) + left];

const auto& idx = m[n];

int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);

if (count >= threshold) return n;

}

return -1;

}

private:

unordered_map<int, vector<int>> m; // num -> {indices}

const vector<int>& nums;

};

花花酱 LeetCode 303. Range Sum Query – Immutable

By zxi on August 17, 2018

Problem

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

You may assume that the array does not change.
There are many calls to sumRange function.

Solution: Prefix sum

sums[i] = nums[0] + nums[1] + … + nums[i]

sumRange(i, j) = sums[j] – sums[i – 1]

Time complexity: pre-compute: O(n), query: O(1)

Space complexity: O(n)

// Author: Huahua

// Running time: 112 ms

class NumArray {

public:

NumArray(vector<int> nums): sums_(nums) {

if (nums.empty()) return;

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

sums_[i] += sums_[i - 1];

}

int sumRange(int i, int j) {

if (i == 0) return sums_[j];

return sums_[j] - sums_[i-1];

}

private:

vector<int> sums_;

};

花花酱 LeetCode 304. Range Sum Query 2D – Immutable

By zxi on September 18, 2017

https://leetcode.com/problems/range-sum-query-2d-immutable/description/

Problem:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [

[3, 0, 1, 4, 2],

[5, 6, 3, 2, 1],

[1, 2, 0, 1, 5],

[4, 1, 0, 1, 7],

[1, 0, 3, 0, 5]

]

sumRegion(2, 1, 4, 3) : 8

sumRegion(1, 1, 2, 2) : 11

sumRegion(1, 2, 2, 4) : 12

Note:

You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Idea:

Dynamic programming

Time complexity:

O(n^2)

sumRegion: O(1)

Solution:

// Author: Huahua

// Time complexity:

// constructor: O(n^2)

// sumRegion: O(1)

// Running time: 22 ms 9/2017

class NumMatrix {

public:

NumMatrix(const vector<vector<int>>& matrix) {

sums_.clear();

if (matrix.empty()) return;

int m = matrix.size();

int n = matrix[0].size();

// sums_[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])

sums_ = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

for (int i = 1; i <= m; ++i)

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

sums_[i][j] = matrix[i - 1][j - 1]

+ sums_[i - 1][j]

+ sums_[i][j - 1]

- sums_[i - 1][j - 1];

}

int sumRegion(int row1, int col1, int row2, int col2) {

return sums_[row2 + 1][col2 + 1]

- sums_[row2 + 1][col1]

- sums_[row1][col2 + 1]

+ sums_[row1][col1];

}

private:

vector<vector<int>> sums_;

};

/**

* Your NumMatrix object will be instantiated and called as such:

* NumMatrix obj = new NumMatrix(matrix);

* int param_1 = obj.sumRegion(row1,col1,row2,col2);

Posts tagged as “range query”

花花酱 LeetCode 1157. Online Majority Element In Subarray

Solution 0: Brute Force TLE

Solution 1: Cache the range result

C++

Solution 2: HashTable + binary search

C++

Solution 2+: Randomization

C++

花花酱 LeetCode 303. Range Sum Query – Immutable

Problem

Solution: Prefix sum

花花酱 LeetCode 304. Range Sum Query 2D – Immutable