Huahua’s Tech Road

花花酱 LeetCode 1828. Queries on Number of Points Inside a Circle

By zxi on April 17, 2021

You are given an array points where points[i] = [x_i, y_i] is the coordinates of the i^th point on a 2D plane. Multiple points can have the same coordinates.

You are also given an array queries where queries[j] = [x_j, y_j, r_j] describes a circle centered at (x_j, y_j) with a radius of r_j.

For each query queries[j], compute the number of points inside the j^th circle. Points on the border of the circle are considered inside.

Return an array answer, where answer[j] is the answer to the j^th query.

Example 1:

Input: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
Output: [3,2,2]
Explanation: The points and circles are shown above.
queries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.

Example 2:

Input: points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
Output: [2,3,2,4]
Explanation: The points and circles are shown above.
queries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.

Constraints:

1 <= points.length <= 500
points[i].length == 2
0 <= x_i, y_i <= 500
1 <= queries.length <= 500
queries[j].length == 3
0 <= x_j, y_j <= 500
1 <= r_j <= 500
All coordinates are integers.

Solution: Brute Force

Time complexity: O(P * Q)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {

vector<int> ans;

ans.reserve(queries.size());

for (const auto& q : queries) {

const int rs = q[2] * q[2];

int cnt = 0;

for (const auto& p : points)

if ((q[0] - p[0]) * (q[0] - p[0]) +

(q[1] - p[1]) * (q[1] - p[1]) <= rs)

++cnt;

ans.push_back(cnt);

}

return ans;

}

};

花花酱 LeetCode 1827. Minimum Operations to Make the Array Increasing

By zxi on April 17, 2021

You are given an integer array nums (0-indexed). In one operation, you can choose an element of the array and increment it by 1.

For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,3,3].

Return the minimum number of operations needed to make nums strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for all 0 <= i < nums.length - 1. An array of length 1 is trivially strictly increasing.

Example 1:

Input: nums = [1,1,1]
Output: 3
Explanation: You can do the following operations:
1) Increment nums[2], so nums becomes [1,1,2].
2) Increment nums[1], so nums becomes [1,2,2].
3) Increment nums[2], so nums becomes [1,2,3].

Example 2:

Input: nums = [1,5,2,4,1]
Output: 14

Example 3:

Input: nums = [8]
Output: 0

Constraints:

1 <= nums.length <= 5000
1 <= nums[i] <= 10⁴

Solution: Track Last

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

C++

class Solution {

public:

int minOperations(vector<int>& nums) {

int ans = 0, last = 0;

for (int x : nums)

if (x <= last)

ans += ++last - x;

else

last = x;

return ans;

}

};

花花酱 LeetCode 1825. Finding MK Average

By zxi on April 13, 2021

You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:

If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.
Remove the smallest k elements and the largest k elements from the container.
Calculate the average value for the rest of the elements rounded down to the nearest integer.

Implement the MKAverage class:

MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.
void addElement(int num) Inserts a new element num into the stream.
int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.

Example 1:

Input
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]
Explanation MKAverage obj = new MKAverage(3, 1); obj.addElement(3); // current elements are [3] obj.addElement(1); // current elements are [3,1] obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist. obj.addElement(10); // current elements are [3,1,10] obj.calculateMKAverage(); // The last 3 elements are [3,1,10]. // After removing smallest and largest 1 element the container will be [3]. // The average of [3] equals 3/1 = 3, return 3 obj.addElement(5); // current elements are [3,1,10,5] obj.addElement(5); // current elements are [3,1,10,5,5] obj.addElement(5); // current elements are [3,1,10,5,5,5] obj.calculateMKAverage(); // The last 3 elements are [5,5,5]. // After removing smallest and largest 1 element the container will be [5]. // The average of [5] equals 5/1 = 5, return 5

Constraints:

3 <= m <= 10⁵
1 <= k*2 < m
1 <= num <= 10⁵
At most 10⁵ calls will be made to addElement and calculateMKAverage.

**Solution 1: Multiset * 3**

Use three multiset to track the left part (smallest k elements), right part (largest k elements) and mid (middle part of m – 2*k elements).

Time complexity: addElememt: O(logn), average: O(1)
Space complexity: O(n)

C++

class MKAverage {

public:

MKAverage(int m, int k):

sum(0), m(m), k(k), n(m - 2*k) {}

void addElement(int num) {

if (q.size() == m) {

remove(q.front());

q.pop();

}

q.push(num);

add(num);

}

int calculateMKAverage() {

return (q.size() < m) ? -1 : sum / n;

}

private:

void add(int x) {

left.insert(x);

if (left.size() > k) {

auto it = prev(end(left));

sum += *it;

mid.insert(*it);

left.erase(it);

}

if (mid.size() > n) {

auto it = prev(end(mid));

sum -= *it;

right.insert(*it);

mid.erase(it);

}

void remove(int x) {

if (x <= *rbegin(left)) {

left.erase(left.find(x));

} else if (x <= *rbegin(mid)) {

sum -= x;

mid.erase(mid.find(x));

} else {

right.erase(right.find(x));

}

if (left.size() < k) {

auto it = begin(mid);

sum -= *it;

left.insert(*it);

mid.erase(it);

}

if (mid.size() < n) {

auto it = begin(right);

sum += *it;

mid.insert(*it);

right.erase(it);

}

queue<int> q;

multiset<int> left, mid, right;

long sum;

const int m;

const int k;

const int n;

};

花花酱 LeetCode 1824. Minimum Sideway Jumps

By zxi on April 13, 2021

There is a 3 lane road of length n that consists of n + 1 points labeled from 0 to n. A frog starts at point 0 in the second laneand wants to jump to point n. However, there could be obstacles along the way.

You are given an array obstacles of length n + 1 where each obstacles[i] (ranging from 0 to 3) describes an obstacle on the lane obstacles[i] at point i. If obstacles[i] == 0, there are no obstacles at point i. There will be at most one obstacle in the 3 lanes at each point.

For example, if obstacles[2] == 1, then there is an obstacle on lane 1 at point 2.

The frog can only travel from point i to point i + 1 on the same lane if there is not an obstacle on the lane at point i + 1. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane.

For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.

Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0.

Note: There will be no obstacles on points 0 and n.

Example 1:

Input: obstacles = [0,1,2,3,0]
Output: 2 
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).
Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).

Example 2:

Input: obstacles = [0,1,1,3,3,0]
Output: 0
Explanation: There are no obstacles on lane 2. No side jumps are required.

Example 3:

Input: obstacles = [0,2,1,0,3,0]
Output: 2
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps.

Constraints:

obstacles.length == n + 1
1 <= n <= 5 * 10⁵
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0

Solution: DP

Time complexity: O(n*k)
Space complexity: O(n*k) -> O(k)

C++

class Solution {

public:

int minSideJumps(vector<int>& obstacles) {

const int n = obstacles.size();

vector<vector<int>> dp(3, vector<int>(n, INT_MAX / 2));

dp[1][0] = 0;

dp[0][0] = dp[2][0] = 1;

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

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

if (obstacles[i] != k + 1)

dp[k][i] = dp[k][i - 1];

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

if (obstacles[i] != k + 1)

dp[k][i] = min({dp[k][i],

dp[(k + 1) % 3][i] + 1,

dp[(k + 2) % 3][i] + 1});

}

return min({dp[0].back(), dp[1].back(), dp[2].back()});

}

};

C++/O(1) Space

class Solution {

public:

int minSideJumps(vector<int>& obstacles) {

const int n = obstacles.size();

vector<int> dp{1, 0, 1};

for (int o : obstacles) {

if (o) dp[o - 1] = 1e9;

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

if (k == o - 1) continue;

dp[k] = min({dp[k],

dp[(k + 1) % 3] + 1,

dp[(k + 2) % 3] + 1});

}

return *min_element(begin(dp), end(dp));

}

};

花花酱 LeetCode 1823. Find the Winner of the Circular Game

By zxi on April 12, 2021

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the i^th friend brings you to the (i+1)^th friend for 1 <= i < n, and moving clockwise from the n^th friend brings you to the 1^st friend.

The rules of the game are as follows:

Start at the 1^st friend.
Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
The last friend you counted leaves the circle and loses the game.
If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

Example 1:

Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

Example 2:

Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.

Constraints:

1 <= k <= n <= 500

Solution 1: Simulation w/ Queue / List

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

C++/Queue

// Author: Huahua, 56 ms, 24.3 MB

class Solution {

public:

int findTheWinner(int n, int k) {

queue<int> q;

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

q.push(i);

while (q.size() != 1) {

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

int x = q.front();

q.pop();

q.push(x);

}

q.pop();

}

return q.front();

}

};

C++/List

// Author: Huahua, 12 ms, 6.8 MB

class Solution {

public:

int findTheWinner(int n, int k) {

list<int> l;

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

l.push_back(i);

auto it = l.begin();

while (l.size() != 1) {

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

if (++it == l.end())

it = l.begin();

it = l.erase(it);

if (it == l.end())

it = l.begin();

}

return l.front();

}

};

Huahua's Tech Road

花花酱 LeetCode 1828. Queries on Number of Points Inside a Circle

Solution: Brute Force

C++

花花酱 LeetCode 1827. Minimum Operations to Make the Array Increasing

Solution: Track Last

C++

花花酱 LeetCode 1825. Finding MK Average

Solution 1: Multiset * 3

C++

花花酱 LeetCode 1824. Minimum Sideway Jumps

Solution: DP

C++

C++/O(1) Space

花花酱 LeetCode 1823. Find the Winner of the Circular Game

Solution 1: Simulation w/ Queue / List

C++/Queue

C++/List

**Solution 1: Multiset * 3**