Huahua’s Tech Road

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;

}

};

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

}

};

Huahua's Tech Road

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

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

Solution: Mod and Count

C++

花花酱 LeetCode 1496. Path Crossing

Solution: Simulation + Hashtable

C++