Press "Enter" to skip to content

Posts tagged as “two pointers”

花花酱 LeetCode 2410. Maximum Matching of Players With Trainers

You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.

The ith player can match with the jth trainer if the player’s ability is less than or equal to the trainer’s training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.

Return the maximum number of matchings between players and trainers that satisfy these conditions.

Example 1:

Input: players = [4,7,9], trainers = [8,2,5,8]
Output: 2
Explanation:
One of the ways we can form two matchings is as follows:
- players[0] can be matched with trainers[0] since 4 <= 8.
- players[1] can be matched with trainers[3] since 7 <= 8.
It can be proven that 2 is the maximum number of matchings that can be formed.

Example 2:

Input: players = [1,1,1], trainers = [10]
Output: 1
Explanation:
The trainer can be matched with any of the 3 players.
Each player can only be matched with one trainer, so the maximum answer is 1.

Constraints:

  • 1 <= players.length, trainers.length <= 105
  • 1 <= players[i], trainers[j] <= 109

Solution: Sort + Two Pointers

Sort players and trainers.

Loop through players, skip trainers until he/she can match the current players.

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

C++

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

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 <= 105
  • 0 <= nums[i] <= 105

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

花花酱 LeetCode 2149. Rearrange Array Elements by Sign

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:

  1. Every consecutive pair of integers have opposite signs.
  2. For all integers with the same sign, the order in which they were present in nums is preserved.
  3. 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 * 105
  • nums.length is even
  • 1 <= |nums[i]| <= 105
  • 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++

Solution 2: Two Pointers

Use two pointers to store the next pos / neg.

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

C++

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

In a linked list of size n, where n is even, the ith 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, 105].
  • 1 <= Node.val <= 105

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

花花酱 LeetCode 2105. Watering Plants II

Problem

Solution: Simulation w/ Two Pointers

Simulate the watering process.

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

C++