Huahua’s Tech Road

花花酱 LeetCode 1503. Last Moment Before All Ants Fall Out of a Plank

By zxi on July 5, 2020

We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with speed 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions doesn’t take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank imediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right. Return the moment when the last ant(s) fall out of the plank.

Example 1:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
Note that the last moment when an ant was on the plank is t = 4 second, after that it falls imediately out of the plank. (i.e. We can say that at t = 4.0000000001, there is no ants on the plank).

Example 2:

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

Example 3:

Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

Example 4:

Input: n = 9, left = [5], right = [4]
Output: 5
Explanation: At t = 1 second, both ants will be at the same intial position but with different direction.

Example 5:

Input: n = 6, left = [6], right = [0]
Output: 6

Constraints:

1 <= n <= 10^4
0 <= left.length <= n + 1
0 <= left[i] <= n
0 <= right.length <= n + 1
0 <= right[i] <= n
1 <= left.length + right.length <= n + 1
All values of left and right are unique, and each value can appear only in one of the two arrays.

Solution: Keep Walking

When two ants A –> and <– B meet at some point, they change directions <– A B –>, we can swap the ids of the ants as <– B A–>, so it’s the same as walking individually and passed by. Then we just need to find the max/min of the left/right arrays.

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

C++

// Author: Huahua

class Solution {

public:

int getLastMoment(int n, vector<int>& left, vector<int>& right) {

const int t1 = left.empty() ? 0 : *max_element(cbegin(left), cend(left));

const int t2 = right.empty() ? 0 : n - *min_element(cbegin(right), cend(right));

return max(t1, t2);

}

};

Java

// Author: Huahua

class Solution {

public int getLastMoment(int n, int[] left, int[] right) {

int t1 = left.length == 0 ? 0 : Arrays.stream(left).max().getAsInt();

int t2 = right.length == 0 ? 0 : n - Arrays.stream(right).min().getAsInt();

return Math.max(t1, t2);

}

Python3

# Author: Huahua

class Solution:

def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:

t1 = max(left) if left else 0

t2 = n - min(right) if right else 0

return max(t1, t2)

花花酱 LeetCode 1502. Can Make Arithmetic Progression From Sequence

By zxi on July 5, 2020

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Example 1:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

Example 2:

Input: arr = [1,2,4]
Output: false
Explanation: There is no way to reorder the elements to obtain an arithmetic progression.

Constraints:

2 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

Solution 1: Sort and check.

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

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

sort(begin(arr), end(arr));

const int diff = arr[1] - arr[0];

for (int i = 2; i < arr.size(); ++i)

if (arr[i] - arr[i - 1] != diff) return false;

return true;

}

};

Java

// Author: Huahua

class Solution {

public boolean canMakeArithmeticProgression(int[] arr) {

Arrays.sort(arr);

int diff = arr[1] - arr[0];

for (int i = 2; i < arr.length; ++i)

if (arr[i] - arr[i - 1] != diff) return false;

return true;

}

python3

class Solution:

def canMakeArithmeticProgression(self, arr: List[int]) -> bool:

arr.sort()

diff = arr[1] - arr[0]

return all(i - j == diff for i, j in zip(arr[1:], arr[:-1]))

Solution 2: Rearrange the array

Find min / max / diff and put each element into its correct position by swapping elements in place.

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

C++

// Author: Huahua

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

const int n = arr.size();

const auto [loit, hiit] = minmax_element(cbegin(arr), cend(arr));

const auto [lo, hi] = pair{*loit, *hiit};

if ((hi - lo) % (n - 1)) return false;

const int diff = (hi - lo) / (n - 1);

if (diff == 0) return true;

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

if ((arr[i] - lo) % diff) return false;

const int idx = (arr[i] - lo) / diff;

if (idx != i) swap(arr[i--], arr[idx]);

}

return true;

}

};

Iterables in Python

By zxi on June 29, 2020

Example Code:

Iterables in Python

# Author: Huahua

class MyListIterator:

def __init__(self, my_list, index=0):

self.my_list = my_list

self.index = index

def __next__(self):

if self.index < len(self.my_list.data):

val = self.my_list.data[self.index]

self.index += 1

return val

else:

raise StopIteration()

def __iter__(self):

return MyListIterator(self.my_list, self.index)

# return self

class MyList:

def __init__(self, data):

self.data = list(data)

def __getitem__(self, index):

return self.data[index]

def __len__(self):

return len(self.data)

def __iter__(self):

return MyListIterator(self)

my_list = MyList([1,2,3,4,5])

it = iter(my_list)

next(it)

it2 = iter(it)

next(it)

print('--- it ---')

for x in it:

print(x) # 3, 4, 5

print('--- it2 ---')

for x in it2:

print(x) # 2, 3, 4, 5

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

}

};

Huahua's Tech Road

花花酱 LeetCode 1503. Last Moment Before All Ants Fall Out of a Plank

Solution: Keep Walking

C++

Java

Python3

花花酱 LeetCode 1502. Can Make Arithmetic Progression From Sequence

Solution 1: Sort and check.

C++

Java

python3

Solution 2: Rearrange the array

C++

Iterables in Python

Example Code:

Iterables in Python

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