2.4.3. Questions

2.4.3.1. Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

Example Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] Output: [20,24]

This problem can be solved by K-Way Merge. k-way merge algorithms or multiway merges are a specific type of sequence merge algorithms that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges.

 1vector<int> smallestRange(vector<vector<int>>& nums) {
 2  using PVI = pair<vector<int>::iterator, vector<int>::iterator>;
 3  struct comp { // comparator for min-heap
 4    bool operator()(const PVI& p1, const PVI& p2) {
 5      return *p1.first > *p2.first;
 6    }
 7  };
 8  priority_queue<PVI, vector<PVI>, comp> pq;
 9  int hi = INT_MIN;
10  for (auto &row : nums) {
11    hi = max(hi, row[0]);
12    pq.push({row.begin(), row.end()});
13  }
14  vector<int> ans = {*pq.top().first, hi};
15  while (1) {
16    auto p = pq.top(); pq.pop();
17    ++p.first;
18    if (p.first == p.second) break;
19    pq.push(p);
20    int lo = *pq.top().first;
21    hi = max(hi, *p.first);
22    if (hi - lo < ans[1] - ans[0])
23      ans = {lo, hi};
24  }
25  return ans;
26}

Refer to Section 2.3.1.3 for K-way merge of linked lists.

2.4.3.2. Top K Frequent Elements

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(NlogN), where n is the array’s size.

2.4.3.3. Remove Smallest Peaks in Order

You are given a list of unique integers nums with length of N. Return a new list created by repeatedly removing the smallest peak from nums and appending to a resulting list. A number nums[i] is called a peak if:

nums[i] > nums[i + 1] if i = 0
nums[i - 1] < nums[i] if i = N - 1
nums[i - 1] < nums[i] > nums[i + 1]
(Constraints: 0 ≤ N ≤ 100,000 where N is the length of nums)

Otherwise, if a list has one element, that element is considered to be a peak.

Example:

Input: nums = [3, 5, 1, 4, 2]
Output: [4, 2, 5, 3, 1]
Explanation:
We remove 4 and get [3, 5, 1, 2]
We remove 2 and get [3, 5, 1]
We remove 5 and get [3, 1]
We remove 3 and get [1]
We remove 1 and get []

Other examples:

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

Input  : [3]
Output : [3]

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

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

It is easy to find the \(O(N^2)\) solution. To reduce the time complexity, we can use priority_queue. To be more efficient on removing item, we need to construct a doubly linked list.

The node definition is:

1struct Node {  // a min heap node
2  Node *pre = nullptr, *next = nullptr;
3  int key = -1;
4  Node(int key_ = -1) { key = key_; }
5};
6struct comp{  // a min heap comparator
7  bool operator()(const Node* a, const Node* b){return a->key > b->key;}
8};

The algorithm goes like this:

  1. In first for loop, create a doubly linked list and push all peaks into a priority queue.

  2. In the second for loop, pop the minimum heap and remove it from the linked list and add its predecessor or successor if one of them is peak.

 1struct RemoveSmallestPeaksInOrder {
 2  Node head, tail;          // dummy nodes
 3  priority_queue<Node*, vector<Node*>, comp> pq;  // min heap
 4
 5  RemoveSmallestPeaksInOrder() { head.next = &tail, tail.pre = &head; }
 6  bool is_peak_vec(int idx, const vector<int>& nums) {  // O(1)
 7    if (idx == 0) return nums[idx] > nums[idx + 1];
 8    if (idx == nums.size() - 1) return nums[idx] > nums[idx - 1];
 9    return nums[idx] > nums[idx - 1] and nums[idx] > nums[idx + 1];
10  }
11  void remove_dl_node(Node* node) {  // O(1)
12    auto pre = node->pre, next = node->next;
13    pre->next = next, next->pre = pre;
14    delete node;
15  }
16  bool is_peak_dl(Node* node) {  // is peak in doubly linked list
17    auto pre = node->pre, next = node->next;
18    return (node->key > pre->key and node->key > next->key);
19  }
20  void create_dl(Node* node) {  // create a double linked list
21    auto beforeTail = tail.pre;
22    beforeTail->next = node;
23    node->pre = beforeTail;
24    node->next = &tail;
25    tail.pre = node;
26  }
27  vector<int> run(vector<int> nums) {  // O(NLogN)
28    int L = nums.size();
29    if (L == 1) return nums;
30    for (int i = 0; i < L; i++) {  // push all peaks O(N)
31      Node* node = new Node(nums[i]);
32      create_dl(node);  // create doubly linked list
33      if (is_peak_vec(i, nums)) pq.push(node);
34    }
35    vector<int> ans(L);
36    for (int i = 0; i < L; i++) {  // O(N)
37      auto min_peak = pq.top();
38      pq.pop();
39      ans[i] = min_peak->key;
40      auto pre = min_peak->pre, next = min_peak->next;
41      remove_dl_node(min_peak);
42      if (pre != &head and is_peak_dl(pre)) pq.push(pre);  // O(LogN)
43      if (next != &tail and is_peak_dl(next)) pq.push(next);
44    }
45    return ans;
46  }
47};

2.4.3.4. Minimize Max Distance to Gas Station

On a horizontal number line, we have gas stations at positions stations[0], stations[1], … stations[N-1], where N is the number of the stations. Now, you need to add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized. Return the smallest possible value of D.

stations = [0, 1, 2, 3, 5]

     s[0]---------s[1]---------s[2]----------s[3]------------------------s[4]      D
K=2:  0 -----x---- 1 ---------- 2 ----------- 3 ------------x------------ 5 -----> 1
K=3:  0 -----x---- 1 ---------- 2 ----------- 3 ------x----------x------- 5 -----> 1
K=5:  0 -----x---- 1 -----x---- 2 -----x----- 3 ------x----------x------- 5 -----> 2/3

function signature: double minmaxGasDist(vector<int> v, int k);

 1#include <gtest/gtest.h>
 2#include <sein.hpp>
 3
 4namespace ns_gas_station {
 5struct interval {
 6double total, avg;
 7int n = 1;
 8
 9explicit interval(double d) : total(d), n(1), avg(d) {}
10};
11
12struct comp {
13bool operator()(const interval &x, const interval &y) { return x.avg < y.avg; }
14};
15
16double minmaxGasDist(vector<int> v, int k) {  // TC: O(N*LogN+k*LogN) -> O(N+K*LogN)
17  priority_queue<interval, vector<interval>, comp> pq;
18  for (int i = 0; i < (int) v.size() - 1; ++i) { // N
19    double ds = (double) (v[i + 1]) - v[i];
20    pq.emplace(ds);
21  }
22  while (k--) {
23    auto tp = pq.top();
24    pq.pop();
25    tp.avg = tp.total / ++tp.n;
26    pq.push(tp);
27  }
28  return pq.top().avg;
29}
30
31double minmaxGasDist_binary_search(vector<int> v, int K) {
32  adjacent_difference(v.begin(), v.end(), v.begin());
33  v.erase(v.begin());
34  int mx = *max_element(v.begin(), v.end());
35  double h = 0, t = (double) mx;
36  while (t - h > 1e-9) { // O(?)
37    double m = h + (t - h) / 2.0;
38    long long required = 0;
39    for (int i: v) // O(N)
40      required += ceil(i / m) - 1;
41    if (required > K) {
42      h = m;
43    } else {
44      t = m;
45    }
46  }
47  return t;
48}
49}
50
51using namespace ns_gas_station;
52TEST(_ns_gas_station, a) {
53  EXPECT_EQ(minmaxGasDist({0, 1, 2, 3, 5}, 1), 1);
54  EXPECT_EQ(minmaxGasDist({0, 1, 2, 3, 5}, 2), 1);
55  EXPECT_EQ(minmaxGasDist({0, 1, 2, 3, 5}, 3), 1);
56  EXPECT_EQ(minmaxGasDist({0, 1, 2, 3, 5}, 4), 1);
57  EXPECT_DOUBLE_EQ(minmaxGasDist({0, 1, 2, 3, 5}, 5), 0.66666666666666663);
58}

2.4.3.5. Customer Total Waiting Time

Calculate the total waiting time for a customer C to speak to an agent given N agents, M customers, and T[] time for an agent to serve a customer. T[i] represents the amount of time it takes for an agent i to serve one customer. One agent can serve one customer at a time. All N agents can serve concurrently. The customer chooses the agent with the lowest wait time.

N = 2, M = 2, T = [4, 5]
First customer chooses agent 1. Second customer chooses agent 2. Customer C will wait 4 minutes.

N = 2, M = 4, T = [4, 5]
First customer chooses agent 1. Second customer chooses agent 2. Third customer chooses agent 1. Forth customer chooses agent 2. Customer C will wait 8 minutes.

A minheap is ued to solve this problem.

 1#include <gtest/gtest.h>
 2#include <sein.hpp>
 3
 4namespace ns_total_waiting_time {
 5int total_waiting_time(vector<int> agents, int customers){
 6    if(agents.size()>customers) return 0;
 7    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
 8    for (int i=0; i<agents.size(); i++)
 9      pq.emplace(0, agents[0]);
10    for (int i=0; i<customers; i++){
11      auto [tot, unit] = pq.top(); pq.pop();
12      pq.emplace(tot+unit, unit);
13    }
14    return pq.top().first;
15}
16}
17
18using namespace ns_total_waiting_time;
19TEST(_total_waiting_time, a) {
20  EXPECT_EQ(total_waiting_time({4,5},2), 4);
21  EXPECT_EQ(total_waiting_time({4,5},4), 8);
22}