Huahua’s Tech Road

花花酱 LeetCode 1499. Max Value of Equation

By zxi on June 28, 2020

Given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [x_i, y_i] such that x_i < x_j for all 1 <= i < j <= points.length. You are also given an integer k.

Example 1:

Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
Output: 4
Explanation: The first two points satisfy the condition |x_i - x_j| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1.
No other pairs satisfy the condition, so we return the max of 4 and 1.

Example 2:

Input: points = [[0,0],[3,0],[9,2]], k = 3
Output: 3
Explanation: Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.

Constraints:

2 <= points.length <= 10^5
points[i].length == 2
-10^8 <= points[i][0], points[i][1] <= 10^8
0 <= k <= 2 * 10^8
points[i][0] < points[j][0] for all 1 <= i < j <= points.length
x_i form a strictly increasing sequence.

Observation

Since xj > xi, so |xi – xj| + yi + yj => xj + yj + (yi – xi)
We want to have yi – xi as large as possible while need to make sure xj – xi <= k.

Solution 1: Priority Queue / Heap

Put all the points processed so far onto the heap as (y-x, x) sorted by y-x in descending order.
Each new point (x_j, y_j), find the largest y-x such that x_j – x <= k.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

priority_queue<pair<int, int>> q; // {y - x, x}

q.emplace(0, -1e9);

int ans = INT_MIN;

for (const auto& p : points) {

const int x = p[0], y = p[1];

while (!q.empty() && x - q.top().second > k) q.pop();

if (!q.empty())

ans = max(ans, x + y + q.top().first);

q.emplace(y - x, x);

}

return ans;

}

};

Solution 2: Monotonic Queue

Maintain a monotonic queue:
1. The queue is sorted by y – x in descending order.
2. Pop then front element when xj – x_front > k, they can’t be used anymore.
3. Record the max of {xj + yj + (y_front – x_front)}
4. Pop the back element when yj – xj > y_back – x_back, they are smaller and lefter. Won’t be useful anymore.
5. Finally, push the j-th element onto the queue.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

deque<pair<int, int>> q; // {y - x, x} Sort by y - x.

int ans = INT_MIN;

for (const auto& p : points) {

const int xj = p[0];

const int yj = p[1];

// Remove invalid points, e.g. xj - xi > k

while (!q.empty() && xj - q.front().second > k)

q.pop_front();

if (!q.empty())

ans = max(ans, xj + yj + q.front().first);

while (!q.empty() && yj - xj >= q.back().first)

q.pop_back();

q.emplace_back(yj - xj, xj);

}

return ans;

}

};

Java

class Solution {

public int findMaxValueOfEquation(int[][] points, int k) {

var q = new ArrayDeque<Integer>();

int ans = Integer.MIN_VALUE;

for (int i = 0; i < points.length; ++i) {

int xj = points[i][0];

int yj = points[i][1];

while (!q.isEmpty() && xj - points[q.getFirst()][0] > k) {

q.removeFirst();

}

if (!q.isEmpty()) {

ans = Math.max(ans, xj + yj

+ points[q.getFirst()][1] - points[q.getFirst()][0]);

}

while (!q.isEmpty() && yj - xj

>= points[q.getLast()][1] - points[q.getLast()][0]) {

q.removeLast();

}

q.offer(i);

}

return ans;

}

python3

# Author: Huahua

class Solution:

def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:

ans = float('-inf')

q = deque() # {(y - x, x)}

for x, y in points:

while q and x - q[0][1] > k: q.popleft()

if q: ans = max(ans, x + y + q[0][0])

while q and y - x >= q[-1][0]: q.pop()

q.append((y - x, x))

return ans

花花酱 LeetCode 1498. Number of Subsequences That Satisfy the Given Sum Condition

By zxi on June 28, 2020

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6

Solution: Two Pointers

Since order of the elements in the subsequence doesn’t matter, we can sort the input array.
Very similar to two sum, we use two pointers (i, j) to maintain a window, s.t. nums[i] +nums[j] <= target.
Then fix nums[i], any subset of (nums[i+1~j]) gives us a valid subsequence, thus we have 2^(j-(i+1)+1) = 2^(j-i) valid subsequence for window (i, j).

Time complexity: O(nlogn) // Sort
Space complexity: O(n) // need to precompute 2^n % kMod.

C++

// Author: Huahua

class Solution {

public:

int numSubseq(vector<int>& nums, int target) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

vector<int> p(n + 1, 1);

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

p[i] = (p[i - 1] << 1) % kMod;

sort(begin(nums), end(nums));

int ans = 0;

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

while (i <= j && nums[i] + nums[j] > target) --j;

if (i > j) continue;

// In subarray nums[i~j]:

// min = nums[i], max = nums[j]

// nums[i] + nums[j] <= target

// {nums[i], (j - i - 1 + 1 values)}

// Any subset of the right part gives a valid subsequence

// in the original array. And There are 2^(j - i) ones.

ans = (ans + p[j - i]) % kMod;

}

return ans;

}

};

花花酱 LeetCode 1497. Check If Array Pairs Are Divisible by k

By zxi on June 28, 2020

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return True If you can find a way to do that or False otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

Example 4:

Input: arr = [-10,10], k = 2
Output: true

Example 5:

Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true

Constraints:

arr.length == n
1 <= n <= 10^5
n is even.
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5

Solution: Mod and Count

Count the frequency of (x % k + k) % k.
f[0] should be even (zero is also even)
f[1] = f[k -1] ((1 + k – 1) % k == 0)
f[2] = f[k -2] ((2 + k – 2) % k == 0)
…
Time complexity: O(n)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

bool canArrange(vector<int>& arr, int k) {

vector<int> f(k);

for (int x : arr) ++f[(x % k + k) % k];

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

if (f[i] != f[k - i]) return false;

return f[0] % 2 == 0;

}

};

花花酱 LeetCode 1496. Path Crossing

By zxi on June 28, 2020

Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return True if the path crosses itself at any point, that is, if at any time you are on a location you’ve previously visited. Return False otherwise.

Example 1:

Input: path = "NES"
Output: false 
Explanation: Notice that the path doesn't cross any point more than once.

Example 2:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

1 <= path.length <= 10^4
path will only consist of characters in {'N', 'S', 'E', 'W}

Solution: Simulation + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

bool isPathCrossing(string path) {

unordered_set<int> s;

int x = 0;

int y = 0;

s.insert(x * 10000 + y);

for (char d : path) {

if (d == 'N') ++y;

else if (d == 'S') --y;

else if (d == 'E') ++x;

else if (d == 'W') --x;

if (!s.insert(x * 10000 + y).second)

return true;

}

return false;

}

};

花花酱 LeetCode 1494. Parallel Courses II

By zxi on June 27, 2020

Given the integer n representing the number of courses at some university labeled from 1 to n, and the array dependencies where dependencies[i] = [x_i, y_i] represents a prerequisite relationship, that is, the course x_i must be taken before the course y_i. Also, you are given the integer k.

In one semester you can take at most k courses as long as you have taken all the prerequisites for the courses you are taking.

Return the minimum number of semesters to take all courses. It is guaranteed that you can take all courses in some way.

Example 1:

Input: n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
Output: 3 
Explanation: The figure above represents the given graph. In this case we can take courses 2 and 3 in the first semester, then take course 1 in the second semester and finally take course 4 in the third semester.

Example 2:

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 
Explanation: The figure above represents the given graph. In this case one optimal way to take all courses is: take courses 2 and 3 in the first semester and take course 4 in the second semester, then take course 1 in the third semester and finally take course 5 in the fourth semester.

Example 3:

Input: n = 11, dependencies = [], k = 2
Output: 6

Constraints:

1 <= n <= 15
1 <= k <= n
0 <= dependencies.length <= n * (n-1) / 2
dependencies[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
All prerequisite relationships are distinct, that is, dependencies[i] != dependencies[j].
The given graph is a directed acyclic graph.

Solution: DP / Bitmask

NOTE: This is a NP problem, any polynomial-time algorithm is incorrect otherwise P = NP.

Variant 1:
dp[m] := whether state m is reachable, where m is the bitmask of courses studied.
For each semester, we enumerate all possible states from 0 to 2^n – 1, if that state is reachable, then we choose c (c <= k) courses from n and check whether we can study those courses.
If we can study those courses, we have a new reachable state, we set dp[m | courses] = true.

Time complexity: O(n*2^n*2^n) = O(n*n^4) <– This will be much smaller in practice.
and can be reduced to O(n*3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 52 ms, 14.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp(i)[s] := reachable(s) at semester i.

vector<int> dp(S);

dp[0] = 1;

for (int d = 1; d <= n; ++d) { // at most n semesters.

vector<int> tmp(S); // start a new semesters.

for (int s = 0; s < S; ++s) {

if (!dp[s]) continue; // not a reachable state.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

tmp[s | mask] = 1;

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k) {

tmp[s | c] = 1;

}

if (tmp.back()) return d;

}

dp.swap(tmp);

}

return -1;

}

};

Variant 2:
dp[m] := min semesters to reach state m.
dp[m | c] = min{dp[m | c], dp[m] + 1}, if we can reach m | c from m.
This allows us to get rid of enumerate n semesters.
Time complexity: O(2^n*2^n) <– This will be much smaller in practice.
and can be reduced to O(3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 16 ms, 8.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int kInf = 1e9;

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp[m] := min semesters to reach state m.

vector<int> dp(S, kInf);

dp[0] = 0;

for (int s = 0; s < S; ++s) {

if (dp[s] == kInf) continue; // not reachable.

// Generate a mask of courses we can study under state s.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

dp[s | mask] = min(dp[s | mask], dp[s] + 1);

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k)

dp[s | c] = min(dp[s | c], dp[s] + 1);

}

// Early termination?

if (dp.back() != kInf) return dp.back();

}

return dp.back();

}

};

Huahua's Tech Road

花花酱 LeetCode 1499. Max Value of Equation

Observation

Solution 1: Priority Queue / Heap

C++

Solution 2: Monotonic Queue

C++

Java

python3

花花酱 LeetCode 1498. Number of Subsequences That Satisfy the Given Sum Condition

Solution: Two Pointers

C++

花花酱 LeetCode 1497. Check If Array Pairs Are Divisible by k

Solution: Mod and Count

C++

花花酱 LeetCode 1496. Path Crossing

Solution: Simulation + Hashtable

C++

花花酱 LeetCode 1494. Parallel Courses II

Solution: DP / Bitmask

C++

C++