Posts tagged as “two pointers”

花花酱 LeetCode 2216. Minimum Deletions to Make Array Beautiful

By zxi on March 28, 2022

You are given a 0-indexed integer array nums. The array nums is beautiful if:

nums.length is even.
nums[i] != nums[i + 1] for all i % 2 == 0.

Note that an empty array is considered beautiful.

You can delete any number of elements from nums. When you delete an element, all the elements to the right of the deleted element will be shifted one unit to the left to fill the gap created and all the elements to the left of the deleted element will remain unchanged.

Return the minimum number of elements to delete from nums to make it beautiful.

Example 1:

Input: nums = [1,1,2,3,5]
Output: 1
Explanation: You can delete either nums[0] or nums[1] to make nums = [1,2,3,5] which is beautiful. It can be proven you need at least 1 deletion to make nums beautiful.

Example 2:

Input: nums = [1,1,2,2,3,3]
Output: 2
Explanation: You can delete nums[0] and nums[5] to make nums = [1,2,2,3] which is beautiful. It can be proven you need at least 2 deletions to make nums beautiful.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Solution: Greedy + Two Pointers

If two consecutive numbers are the same, we must remove one. We don’t need to actually remove elements from array, just need to track how many elements have been removed so far.

i is the position in the original array, ans is the number of elements been removed. i – ans is the position in the updated array.

ans += nums[i – ans] == nums[i – ans + 1]

Remove the last element (just increase answer by 1) if the length of the new array is odd.

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

C++

// Author: Huahua

class Solution {

public:

int minDeletion(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

for (int i = 0; i - ans + 1 < n; i += 2)

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

ans += (n - ans) & 1;

return ans;

}

};

花花酱 LeetCode 2149. Rearrange Array Elements by Sign

By zxi on February 4, 2022

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should rearrange the elements of nums such that the modified array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

Constraints:

2 <= nums.length <= 2 * 10⁵
nums.length is even
1 <= |nums[i]| <= 10⁵
nums consists of equal number of positive and negative integers.

Solution 1: Split and merge

Create two arrays to store positive and negative numbers.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rearrangeArray(vector<int>& nums) {

vector<int> pos;

vector<int> neg;

for (int x : nums)

(x > 0 ? pos : neg).push_back(x);

vector<int> ans;

for (int i = 0; i < pos.size(); ++i) {

ans.push_back(pos[i]);

ans.push_back(neg[i]);

}

return ans;

}

};

Solution 2: Two Pointers

Use two pointers to store the next pos / neg.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rearrangeArray(vector<int>& nums) {

vector<int> ans(nums.size());

int pos = 0;

int neg = 1;

for (int x : nums) {

int& index = x > 0 ? pos : neg;

ans[index] = x;

index += 2;

}

return ans;

}

};

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

}

};