Huahua’s Tech Road

花花酱 LeetCode 1851. Minimum Interval to Include Each Query

By zxi on May 8, 2021

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i^th interval starting at left_i and ending at right_i (inclusive). The size of an interval is defined as the number of integers it contains, or more formally right_i - left_i + 1.

You are also given an integer array queries. The answer to the j^th query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

1 <= intervals.length <= 10⁵
1 <= queries.length <= 10⁵
intervals[i].length == 2
1 <= left_i <= right_i <= 10⁷
1 <= queries[j] <= 10⁷

Solution: Offline Processing + Priority Queue

Sort intervals by right in descending order, sort queries in descending. Add valid intervals into the priority queue (or treeset) ordered by size in ascending order. Erase invalid ones. The first one (if any) will be the one with the smallest size that contains the current query.

Time complexity: O(nlogn + mlogm + mlogn)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {

const int n = intervals.size();

const int m = queries.size();

sort(begin(intervals), end(intervals), [](const auto& a, const auto& b){

return a[1] > b[1];

});

vector<pair<int, int>> qs(m); // {query, i}

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

qs[i] = {queries[i], i};

sort(rbegin(qs), rend(qs));

vector<int> ans(m);

int j = 0;

priority_queue<pair<int, int>> pq; // {-size, left}

for (const auto& [query, i] : qs) {

while (j < n && intervals[j][1] >= query) {

pq.emplace(-(intervals[j][1] - intervals[j][0] + 1),

intervals[j][0]);

++j;

}

while (!pq.empty() && pq.top().second > query)

pq.pop();

ans[i] = pq.empty() ? -1 : -pq.top().first;

}

return ans;

}

};

花花酱 LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

By zxi on May 8, 2021

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

For example, when num = "5489355142":
- The 1^st smallest wonderful integer is "5489355214".
- The 2^nd smallest wonderful integer is "5489355241".
- The 3^rd smallest wonderful integer is "5489355412".
- The 4^th smallest wonderful integer is "5489355421".

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.

The tests are generated in such a way that k^th smallest wonderful integer exists.

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4^th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4^th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -> "11121"
- Swap index 2 with index 3: "11121" -> "11211"
- Swap index 1 with index 2: "11211" -> "12111"
- Swap index 0 with index 1: "12111" -> "21111"

Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1^st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"

Constraints:

2 <= num.length <= 1000
1 <= k <= 1000
num only consists of digits.

Solution: Next Permutation + Greedy

Time complexity: O(k*n + n^2)
Space complexity: O(n)

C++

class Solution {

public:

int getMinSwaps(string s, int k) {

string t(s);

while (k--) next_permutation(begin(t), end(t));

const int n = s.length();

int ans = 0;

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

if (s[i] == t[i]) continue;

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

if (s[i] != t[j]) continue;

ans += j - i;

t = t.substr(0, i + 1) + t.substr(i, j - i) + t.substr(j + 1);

break;

}

return ans;

}

};

花花酱 LeetCode 1849. Splitting a String Into Descending Consecutive Values

By zxi on May 2, 2021

You are given a string s that consists of only digits.

Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.

For example, the string s = "0090089" can be split into ["0090", "089"] with numerical values [90,89]. The values are in descending order and adjacent values differ by 1, so this way is valid.
Another example, the string s = "001" can be split into ["0", "01"], ["00", "1"], or ["0", "0", "1"]. However all the ways are invalid because they have numerical values [0,1], [0,1], and [0,0,1] respectively, all of which are not in descending order.

Return true if it is possible to split s as described above, or false otherwise.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "1234"
Output: false
Explanation: There is no valid way to split s.

Example 2:

Input: s = "050043"
Output: true
Explanation: s can be split into ["05", "004", "3"] with numerical values [5,4,3].
The values are in descending order with adjacent values differing by 1.

Example 3:

Input: s = "9080701"
Output: false
Explanation: There is no valid way to split s.

Example 4:

Input: s = "10009998"
Output: true
Explanation: s can be split into ["100", "099", "98"] with numerical values [100,99,98].
The values are in descending order with adjacent values differing by 1.

Constraints:

1 <= s.length <= 20
s only consists of digits.

Solution: DFS

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

C++

class Solution {

public:

bool splitString(string s) {

const int n = s.length();

vector<long> nums;

function<bool(int)> dfs = [&](int p) {

if (p == n) return nums.size() >= 2;

long cur = 0;

for (int i = p; i < n && cur < 1e11; ++i) {

cur = cur * 10 + (s[i] - '0');

if (nums.empty() || cur + 1 == nums.back()) {

nums.push_back(cur);

if (dfs(i + 1)) return true;

nums.pop_back();

}

if (!nums.empty() && cur >= nums.back()) break;

}

return false;

};

return dfs(0);

}

};

花花酱 LeetCode 1848. Minimum Distance to the Target Element

By zxi on May 2, 2021

Given an integer array nums (0-indexed) and two integers target and start, find an index i such that nums[i] == target and abs(i - start) is minimized. Note that abs(x) is the absolute value of x.

Return abs(i - start).

It is guaranteed that target exists in nums.

Example 1:

Input: nums = [1,2,3,4,5], target = 5, start = 3
Output: 1
Explanation: nums[4] = 5 is the only value equal to target, so the answer is abs(4 - 3) = 1.

Example 2:

Input: nums = [1], target = 1, start = 0
Output: 0
Explanation: nums[0] = 1 is the only value equal to target, so the answer is abs(0 - 0) = 1.

Example 3:

Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
Output: 0
Explanation: Every value of nums is 1, but nums[0] minimizes abs(i - start), which is abs(0 - 0) = 0.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 10⁴
0 <= start < nums.length
target is in nums.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int getMinDistance(vector<int>& nums, int target, int start) {

int ans = INT_MAX;

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

if (nums[i] == target)

ans = min(ans, abs(i - start));

return ans;

}

};

花花酱 LeetCode 1847. Closest Room

By zxi on May 1, 2021

There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomId_i, size_i] denotes that there is a room with room number roomId_i and size equal to size_i. Each roomId_i is guaranteed to be unique.

You are also given k queries in a 2D array queries where queries[j] = [preferred_j, minSize_j]. The answer to the j^th query is the room number id of a room such that:

The room has a size of at least minSize_j, and
abs(id - preferred_j) is minimized, where abs(x) is the absolute value of x.

If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1.

Return an array answer of length k where answer[j] contains the answer to the j^th query.

Example 1:

Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation: The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.

Example 2:

Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
Output: [2,1,3]
Explanation: The answers to the queries are as follows:
Query = [2,3]: Room number 2 is the closest as abs(2 - 2) = 0, and its size of 3 is at least 3. The answer is 2.
Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.
Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.

Constraints:

n == rooms.length
1 <= n <= 10⁵
k == queries.length
1 <= k <= 10⁴
1 <= roomId_i, preferred_j <= 10⁷
1 <= size_i, minSize_j <= 10⁷

Solution: Off Processing: Sort + Binary Search

Time complexity: O(nlogn + mlogm)
Space complexity: O(n + m)

Sort queries and rooms by size in descending order, only add valid rooms (size >= min_size) to the treeset for binary search.

C++

// Author: Huahua

class Solution {

public:

vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {

const int n = rooms.size();

const int m = queries.size();

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

queries[i].push_back(i);

// Sort queries by size DESC.

sort(begin(queries), end(queries), [](const auto& q1, const auto& q2){

return q1[1] > q2[1];

});

// Sort room by size DESC.

sort(begin(rooms), end(rooms), [](const auto& r1, const auto& r2) {

return r1[1] > r2[1];

});

vector<int> ans(m);

int j = 0;

set<int> ids;

for (const auto& q : queries) {

while (j < n && rooms[j][1] >= q[1])

ids.insert(rooms[j++][0]);

if (ids.empty()) {

ans[q[2]] = -1;

continue;

}

const int id = q[0];

auto it = ids.lower_bound(id);

int id1 = (it != end(ids)) ? *it : INT_MAX;

int id2 = id1;

if (it != begin(ids))

id2 = *prev(it);

ans[q[2]] = abs(id1 - id) < abs(id2 - id) ? id1 : id2;

}

return ans;

}

};

Solution 2: Fenwick Tree

Time complexity: O(nlogS + mlogSlogn)
Space complexity: O(nlogS)

C++

class Solution {

public:

vector<int> closestRoom(vector<vector<int>>& rooms,

vector<vector<int>>& queries) {

S = 0;

for (const auto& r : rooms) S = max(S, r[1]);

for (const auto& r : rooms) update(r[1], r[0]);

vector<int> ans;

for (const auto& q : queries)

ans.push_back(query(q[1], q[0]));

return ans;

}

private:

int S;

void update(int s, int id) {

for (s = S - s + 1; s <= S; s += s & (-s))

tree[s].insert(id);

}

int query(int s, int id) {

int ans = -1;

for (s = S - s + 1; s > 0; s -= s & (-s)) {

if (!tree.count(s)) continue;

int id1 = INT_MAX;

int id2 = INT_MAX;

auto it = tree[s].lower_bound(id);

if (it != end(tree[s])) id1 = *it;

if (it != begin(tree[s])) id2 = *prev(it);

int cid = (abs(id1 - id) < abs(id2 - id)) ? id1 : id2;

if (ans == -1 || abs(cid - id) < abs(ans - id))

ans = cid;

else if (abs(cid - id) == abs(ans - id))

ans = min(ans, cid);

}

return ans;

}

unordered_map<int, set<int>> tree;

};

Huahua's Tech Road

花花酱 LeetCode 1851. Minimum Interval to Include Each Query

Solution: Offline Processing + Priority Queue

C++

花花酱 LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

Solution: Next Permutation + Greedy

C++

花花酱 LeetCode 1849. Splitting a String Into Descending Consecutive Values

Solution: DFS

C++

花花酱 LeetCode 1848. Minimum Distance to the Target Element

Solution: Brute Force

C++

花花酱 LeetCode 1847. Closest Room

Solution: Off Processing: Sort + Binary Search

C++

Solution 2: Fenwick Tree

C++