Press "Enter" to skip to content

Posts tagged as “two pointers”

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

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 <= 105
  • 1 <= nums2.length <= 105
  • 1 <= nums1[i], nums2[j] <= 105
  • 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++

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

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 <= 105
  • 1 <= nums[i] <= 2 * 104
  • 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++

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

A split of an integer array is good if:

  • The array is split into three non-empty contiguous subarrays – named leftmidright 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 <= 105
  • 0 <= nums[i] <= 104

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

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

花花酱 LeetCode 1679. Max Number of K-Sum Pairs

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 109

Solution 1: Frequency Map

For each x, check freq[x] and freq[k – x]. Note: there is a special case when x + x == k.

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

C++

Python3

Solution 2: Two Pointers

Sort the number, start from i = 0, j = n – 1, compare s = nums[i] + nums[j] with k and move i, j accordingly.

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

C++

花花酱 LeetCode 1574. Shortest Subarray to be Removed to Make Array Sorted

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

A subarray is a contiguous subsequence of the array.

Return the length of the shortest subarray to remove.

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Example 4:

Input: arr = [1]
Output: 0

Constraints:

  • 1 <= arr.length <= 10^5
  • 0 <= arr[i] <= 10^9

Solution: Two Pointers

Find the right most j such that arr[j – 1] > arr[j], if not found which means the entire array is sorted return 0. Then we have a non-descending subarray arr[j~n-1].

We maintain two pointers i, j, such that arr[0~i] is non-descending and arr[i] <= arr[j] which means we can remove arr[i+1~j-1] to get a non-descending array. Number of elements to remove is j – i – 1 .

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

C++