Posts published in “Algorithms”

花花酱 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;

};

花花酱 1054. Distant Barcodes

By zxi on May 28, 2019

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

Example 1:

Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,2,1,2,1]

Note:

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

Soluton: Sorting

Sort the element by their frequency in descending order. Fill the most frequent element first in even positions, if reach the end of the array, start from position 1 then 3, 5, …

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, 216 ms, 18.2 MB

class Solution {

public:

vector<int> rearrangeBarcodes(vector<int>& barcodes) {

const int n = barcodes.size();

vector<int> f(10001);

for (int v : barcodes) ++f[v];

sort(begin(barcodes), end(barcodes), [&](const int a, const int b){

return f[a] == f[b] ? a > b : f[a] > f[b];

});

vector<int> ans(n);

int pos = 0;

for (int v : barcodes) {

ans[pos] = v;

if ((pos += 2) >= n) pos = 1;

}

return ans;

}

};

Solution 2: Find the most frequent

Actually, we only need to find the most frequent element and put in the even positions, then put the rest of the groups of elements in any order.

e.g. [1, 1, 2, 2, 2, 2, 2, 3, 4]
Can be
5*2 [2 – 2 – 2 – 2 – 2]
4*1 [2 4 2 – 2 – 2 – 2]
3*1 [2 4 2 3 2 – 2 – 2]
1*2 [ 2 3 2 3 2 1 2 1 2]

if we start with any other groups rather than 2, if will become:
[3 2 2 – 2 – 2 – 2 ] which is wrong…

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 172 ms (99.89%), 18 MB (< 100%)

class Solution {

public:

vector<int> rearrangeBarcodes(vector<int>& barcodes) {

constexpr int kMaxV = 10001;

const int n = barcodes.size();

vector<int> f(kMaxV);

int max_f = 0;

int max_v = 0;

for (int v : barcodes)

if (++f[v] > max_f) {

max_f = f[v];

max_v = v;

}

vector<int> ans(n);

int pos = 0;

while (f[max_v]-- > 0) {

ans[pos] = max_v;

if ((pos += 2)>= n) pos = 1;

}

for (int v = 1; v < kMaxV; ++v) {

while (f[v]-- > 0) {

ans[pos] = v;

if ((pos += 2) >= n) pos = 1;

}

return ans;

}

};

花花酱 LeetCode 1051. Height Checker

By zxi on May 27, 2019

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students not standing in the right positions. (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)

Example 1:

Input: [1,1,4,2,1,3]
Output: 3
Explanation: 
Students with heights 4, 3 and the last 1 are not standing in the right positions.

Note:

1 <= heights.length <= 100
1 <= heights[i] <= 100

Solution: Sorting

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

int heightChecker(vector<int>& heights) {

vector<int> h(heights);

sort(begin(h), end(h));

int ans = 0;

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

ans += (heights[i] != h[i]);

return ans;

}

};

花花酱 LeetCode 1011. Capacity To Ship Packages Within D Days

By zxi on March 16, 2019

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation: 
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Solution: Binary Search

Find the smallest capacity such that can finish in D days.

Time complexity: O(n * log(sum(weights))
Space complexity: O(1)

C++

// Author: Huahua, running time: 52 ms, 11.9 MB

class Solution {

public:

int shipWithinDays(vector<int>& weights, int D) {

int l = *max_element(begin(weights), end(weights));

int r = accumulate(begin(weights), end(weights), 0) + 1;

while (l < r) {

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

int d = 1;

int t = 0;

for (int w : weights)

if ((t += w) > m) {

t = w;

++d;

}

d > D ? l = m + 1 : r = m;

}

return l;

}

};

LeetCode 930. Binary Subarrays With Sum

By zxi on March 11, 2019

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Note:

A.length <= 30000
0 <= S <= A.length
A[i] is either 0 or 1.

Solution: Prefix Sum

counts[s] := # of subarrays start from 0 that have sum of s
ans += counts[s – S] if s >= S

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 28 ms, 12.3 MB

class Solution {

public:

int numSubarraysWithSum(vector<int>& A, int S) {

const int n = A.size();

vector<int> counts(n + 1);

counts[0] = 1;

int ans = 0;

int sum = 0;

for (int a : A) {

sum += a;

if (sum >= S) ans += counts[sum - S];

++counts[sum];

}

return ans;

}

};