Huahua’s Tech Road

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

}

};

花花酱 LeetCode 1822. Sign of the Product of an Array

By zxi on April 12, 2021

There is a function signFunc(x) that returns:

1 if x is positive.
-1 if x is negative.
0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

Example 1:

Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1

Example 2:

Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 3:

Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1

Constraints:

1 <= nums.length <= 1000
-100 <= nums[i] <= 100

Solution: Sign Only

No need to compute the product, only track the sign changes. Flip the sign when encounter a negative number, return 0 if there is any 0 in the array.

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

C++

// Author: Huahua

class Solution {

public:

int arraySign(vector<int>& nums) {

int sign = 1;

for (int x : nums) {

if (x == 0) return 0;

else if (x < 0) sign = -sign;

}

return sign;

}

};

花花酱 LeetCode 1819. Number of Different Subsequences GCDs

By zxi on April 6, 2021

You are given an array nums that consists of positive integers.

The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.

For example, the GCD of the sequence [4,6,16] is 2.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

Return the number of different GCDs among all non-empty subsequences of nums.

Example 1:

Input: nums = [6,10,3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.

Example 2:

Input: nums = [5,15,40,5,6]
Output: 7

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁵

Solution: Math

Enumerate all possible gcds (1 to max(nums)), and check whether there is a subset of the numbers that can form a given gcd i.
If we want to check whether 10 is a valid gcd, we found all multipliers of 10 in the array and compute their gcd.
ex1 gcd(10, 20, 30) = 10, true
ex2 gcd(20, 40, 80) = 20, false

Time complexity: O(mlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

int countDifferentSubsequenceGCDs(vector<int>& nums) {

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

vector<int> s(kMax + 1);

for (int x : nums) s[x] = 1;

int ans = 0;

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

int g = 0;

for (int j = i; j <= kMax; j += i)

if (s[j]) g = gcd(g, j);

ans += g == i;

}

return ans;

}

};

花花酱 LeetCode 1818. Minimum Absolute Sum Difference

By zxi on April 6, 2021

You are given two positive integer arrays nums1 and nums2, both of length n.

The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).

You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.

Return the minimum absolute sum difference after replacing at most oneelement in the array nums1. Since the answer may be large, return it modulo 10⁹ + 7.

|x| is defined as:

x if x >= 0, or
-x if x < 0.

Example 1:

Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: There are two possible optimal solutions:
- Replace the second element with the first: [1,7,5] => [1,1,5], or
- Replace the second element with the third: [1,7,5] => [1,5,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.

Example 2:

Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output: 0
Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an 
absolute sum difference of 0.

Example 3:

Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7].
This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁵

Solution: Binary Search

Greedy won’t work, e.g. finding the max diff pair and replace it. Counter example:
nums1 = [7, 5], nums2 = [1, -2]
pair1 = abs(7 – 1) = 6
pair2 = abs(5 – (-2)) = 7
If we replace 5 with 7, we got pair2′ = abs(7 – (-2)) = 9 > 7.

Every pair of numbers can be the candidate, we just need to find the closest number for each nums2[i].

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

C++

class Solution {

public:

int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {

constexpr int kMod = 1e9 + 7;

const int n = nums1.size();

long ans = 0;

int gain = 0;

set<int> s(begin(nums1), end(nums1));

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

const int diff = abs(nums1[i] - nums2[i]);

ans += diff;

if (diff <= gain) continue;

auto it = s.lower_bound(nums2[i]);

if (it != s.end())

gain = max(gain, diff - abs(*it - nums2[i]));

if (it != s.begin())

gain = max(gain, diff - abs(*prev(it) - nums2[i]));

}

return (ans - gain) % kMod;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 1822. Sign of the Product of an Array

Solution: Sign Only

C++

花花酱 LeetCode 1819. Number of Different Subsequences GCDs

Solution: Math

C++

花花酱 LeetCode 1818. Minimum Absolute Sum Difference

Solution: Binary Search

C++