Posts tagged as “two pointers”

花花酱 LeetCode 2130. Maximum Twin Sum of a Linked List

By zxi on January 9, 2022

In a linked list of size n, where n is even, the i^th node (0-indexed) of the linked list is known as the twin of the (n-1-i)^th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

The number of nodes in the list is an even integer in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Solution: Two Pointers + Reverse List

Use fast slow pointers to find the middle point and reverse the second half.

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

C++

// Author: Huahua

class Solution {

public:

int pairSum(ListNode* head) {

auto reverse = [](ListNode* head, ListNode* prev = nullptr) {

while (head) {

swap(head->next, prev);

swap(head, prev);

}

return prev;

};

ListNode* fast = head;

ListNode* slow = head;

while (fast) {

fast = fast->next->next;

slow = slow->next;

}

slow = reverse(slow);

int ans = 0;

while (slow) {

ans = max(ans, head->val + slow->val);

head = head->next;

slow = slow->next;

}

return ans;

}

};

花花酱 LeetCode 2105. Watering Plants II

By zxi on December 12, 2021

Problem

Solution: Simulation w/ Two Pointers

Simulate the watering process.

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

C++

// Author: Huahua

class Solution {

public:

int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {

const int n = plants.size();

int ans = 0;

for (int l = 0, r = n - 1, A = capacityA, B = capacityB; l <= r; ++l, --r) {

if (l == r)

return ans += max(A, B) < plants[l];

if ((A -= plants[l]) < 0)

A = capacityA - plants[l], ++ans;

if ((B -= plants[r]) < 0)

B = capacityB - plants[r], ++ans;

}

return ans;

}

};

花花酱 LeetCode 76. Minimum Window Substring

By zxi on November 29, 2021

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

m == s.length
n == t.length
1 <= m, n <= 10⁵
s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

Solution: Hashtable + Two Pointers

Use a hashtable to store the freq of characters we need to match for t.

Use (i, j) to track a subarray that contains all the chars in t.

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

C++

// Author: Huahua

class Solution {

public:

string minWindow(string s, string t) {

const int n = s.length();

const int m = t.length();

vector<int> freq(128);

for (char c : t) ++freq[c];

int start = 0;

int l = INT_MAX;

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

if (--freq[s[j]] >= 0) --left;

while (left == 0) {

if (j - i + 1 < l) {

l = j - i + 1;

start = i;

}

if (++freq[s[i++]] == 1) ++left;

}

return l == INT_MAX ? "" : s.substr(start, l);

}

};

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