Press "Enter" to skip to content

Posts published in “Two pointers”

花花酱 LeetCode 2825. Make String a Subsequence Using Cyclic Increments

You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b''b' becomes 'c', and so on, and 'z' becomes 'a'.

Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most onceand false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Example 1:

Input: str1 = "abc", str2 = "ad"
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become 'd'. 
Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.

Example 2:

Input: str1 = "zc", str2 = "ad"
Output: true
Explanation: Select indices 0 and 1 in str1. 
Increment str1[0] to become 'a'. 
Increment str1[1] to become 'd'. 
Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.

Example 3:

Input: str1 = "ab", str2 = "d"
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. 
Therefore, false is returned.

Constraints:

  • 1 <= str1.length <= 105
  • 1 <= str2.length <= 105
  • str1 and str2 consist of only lowercase English letters.

Solution: Two pointers

s1[i] and s2[j] can match if
s1[i] == s2[j] or inc(s1[i]) == s2[j]

If matched: ++i; ++j else ++i.

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

C++

Iterator version

C++

花花酱 2570. Merge Two 2D Arrays by Summing Values

You are given two 2D integer arrays nums1 and nums2.

  • nums1[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.
  • nums2[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

  • Only ids that appear in at least one of the two arrays should be included in the resulting array.
  • Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays then its value in that array is considered to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

Example 1:

Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Output: [[1,6],[2,3],[3,2],[4,6]]
Explanation: The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.

Example 2:

Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.

Constraints:

  • 1 <= nums1.length, nums2.length <= 200
  • nums1[i].length == nums2[j].length == 2
  • 1 <= idi, vali <= 1000
  • Both arrays contain unique ids.
  • Both arrays are in strictly ascending order by id.

Solution: Two Pointers

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

C++

花花酱 LeetCode 2563. Count the Number of Fair Pairs

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

  • 0 <= i < j < n, and
  • lower <= nums[i] + nums[j] <= upper

Example 1:

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6
Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

Example 2:

Input: nums = [1,7,9,2,5], lower = 11, upper = 11
Output: 1
Explanation: There is a single fair pair: (2,3).

Constraints:

  • 1 <= nums.length <= 105
  • nums.length == n
  • -109 <= nums[i] <= 109
  • -109 <= lower <= upper <= 109

Solution: Two Pointers

Sort the array, use two pointers to find how # of pairs (i, j) s.t. nums[i] + nums[j] <= limit.
Ans = count(upper) – count(lower – 1)

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

C++

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