Posts tagged as “two pointers”

花花酱 LeetCode 1898. Maximum Number of Removable Characters

By zxi on August 11, 2021

You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).

You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example 1:

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

Example 2:

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".

Example 3:

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints:

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Solution: Binary Search + Two Pointers

If we don’t remove any thing, p is a subseq of s, as we keep removing, at some point L, p is no longer a subseq of s. e.g [0:True, 1: True, …, L – 1: True, L: False, L+1: False, …, m:False], this array is monotonic. We can use binary search to find the smallest L such that p is no long a subseq of s. Ans = L – 1.

For each guess, we can use two pointers to check whether p is subseq of removed(s) in O(n).

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

C++

// Author: Huahua

class Solution {

public:

int maximumRemovals(string s, string p, vector<int>& removable) {

const int n = s.length();

const int t = p.length();

const int m = removable.size();

int l = 0;

int r = m + 1;

vector<int> idx(n, INT_MAX);

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

idx[removable[i]] = i;

while (l < r) {

int mid = l + (r - l) / 2;

int j = 0;

for (int i = 0; i < n && j < t; ++i)

if (idx[i] >= mid && s[i] == p[j]) ++j;

if (j != t)

r = mid;

else

l = mid + 1;

}

// l is the smallest number s.t. p is no longer a subseq of s.

return l - 1;

}

};

花花酱 LeetCode 1871. Jump Game VII

By zxi on August 5, 2021

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

i + minJump <= j <= min(i + maxJump, s.length - 1), and
s[j] == '0'.

Return true if you can reach index s.length - 1 in s, or false otherwise.

Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

Example 2:

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

Constraints:

2 <= s.length <= 10⁵
s[i] is either '0' or '1'.
s[0] == '0'
1 <= minJump <= maxJump < s.length

Solution 1: TreeSet /Dequq + Binary Search

Maintain a set of reachable indices so far, for each ‘0’ index check whether it can be reached from any of the elements in the set.

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

C++/set

// Author: Huahua, 296 ms, 59.7MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

set<int> seen{0};

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

if (s[i] != '0') continue;

while (!seen.empty() && (*seen.begin()) + maxJump < i)

seen.erase(seen.begin());

auto it = seen.upper_bound(i - minJump);

if (it != seen.begin() && *prev(it) + minJump <= i)

seen.insert(i);

}

return seen.count(n - 1);

}

};

C++/deque

// Author: Huahua, 280 ms, 19MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

deque<int> seen{0};

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

if (s[i] != '0') continue;

while (!seen.empty() && (seen.front()) + maxJump < i)

seen.pop_front();

auto it = upper_bound(begin(seen), end(seen), i - minJump);

if (it != seen.begin() && *prev(it) + minJump <= i)

seen.push_back(i);

}

return seen.back() == n - 1;

}

};

Solution 2: Queue

Same idea, we can replace the deque in sol1 with a queue, and only check the smallest element in the queue.

C++/set

// Author: Huahua, 56ms, 19.2MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

queue<int> q{{0}};

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

if (s[i] != '0') continue;

while (!q.empty() && q.front() + maxJump < i)

q.pop();

if (!q.empty() && q.front() + minJump <= i)

q.push(i);

}

return q.back() == n - 1;

}

};

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

花花酱 LeetCode 1855. Maximum Distance Between a Pair of Values

By zxi on May 8, 2021

You are given two non-increasing 0-indexed integer arrays nums1 and nums2.

A pair of indices (i, j), where 0 <= i < nums1.length and 0 <= j < nums2.length, is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i.

Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

An array arr is non-increasing if arr[i-1] >= arr[i] for every 1 <= i < arr.length.

Example 1:

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
Output: 2
Explanation: The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4).
The maximum distance is 2 with pair (2,4).

Example 2:

Input: nums1 = [2,2,2], nums2 = [10,10,1]
Output: 1
Explanation: The valid pairs are (0,0), (0,1), and (1,1).
The maximum distance is 1 with pair (0,1).

Example 3:

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
Output: 2
Explanation: The valid pairs are (2,2), (2,3), (2,4), (3,3), and (3,4).
The maximum distance is 2 with pair (2,4).

Example 4:

Input: nums1 = [5,4], nums2 = [3,2]
Output: 0
Explanation: There are no valid pairs, so return 0.

Constraints:

1 <= nums1.length <= 10⁵
1 <= nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁵
Both nums1 and nums2 are non-increasing.

Solution: Two Pointers

For each i, find the largest j such that nums[j] >= nums[i].

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

C++

// Author: Huahua

class Solution {

public:

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

int ans = 0;

for (int i = 0, j = -1; i < nums1.size(); ++i) {

while (j + 1 < nums2.size() && nums2[j + 1] >= nums1[i]) ++j;

if (j >= i) ans = max(ans, j - i);

}

return ans;

}

};

花花酱 LeetCode 1793. Maximum Score of a Good Subarray

By zxi on March 18, 2021

You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

Example 1:

Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.

Example 2:

Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Constraints:

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

Solutions: Two Pointers

maintain a window [i, j], m = min(nums[i~j]), expend to the left if nums[i – 1] >= nums[j + 1], otherwise expend to the right.

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

C++

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, int k) {

const int n = nums.size();

int ans = 0;

for (int i = k, j = k, m = nums[k];;) {

ans = max(ans, m * (j - i + 1));

if (j - i + 1 == n) break;

int l = i ? nums[i - 1] : -1;

int r = j + 1 < n ? nums[j + 1] : -1;

if (l >= r)

m = min(m, nums[--i]);

else

m = min(m, nums[++j]);

}

return ans;

}

};

花花酱 LeetCode 1712. Ways to Split Array Into Three Subarrays

By zxi on January 3, 2021

A split of an integer array is good if:

The array is split into three non-empty contiguous subarrays – named left, mid, right respectively from left to right.
The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁴

Solution 1: Prefix Sum + Binary Search

We split the array into [0 … i] [i + 1… j] [j + 1 … n – 1]
we can use binary search to find the min and max of j for each i.
s.t. sum(0 ~ i) <= sums(i + 1 ~j) <= sums(j + 1 ~ n – 1)
min is lower_bound(2 * sums(0 ~ i))
max is upper_bound(sums(0 ~ i) + (total – sums(0 ~ i)) / 2)

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

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

// [0 .. i] [i + 1 ... j] [j + 1 ... n - 1]

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

auto it1 = lower_bound(begin(nums) + i + 1, end(nums), 2 * nums[i]);

auto it2 = upper_bound(begin(nums), end(nums) - 1, nums[i] + (total - nums[i]) / 2);

if (it2 <= it1) continue;

ans += it2 - it1;

}

return ans % kMod;

}

};

Solution 2: Prefix Sum + Two Pointers

The right end of the middle array is in range [j, k – 1] and there are k – j choices.
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

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

j = max(j, i + 1);

while (j < n - 1 && nums[j] < 2 * nums[i]) ++j;

k = max(k, j);

while (k < n - 1 && 2 * nums[k] <= nums[i] + total) ++k;

ans += (k - j);

}

return ans % kMod;

}

};