Press "Enter" to skip to content

Posts published in “Two pointers”

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

花花酱 LeetCode 1537. Get the Maximum Score

You are given two sorted arrays of distinct integers nums1 and nums2.

validpath is defined as follows:

  • Choose array nums1 or nums2 to traverse (from index-0).
  • Traverse the current array from left to right.
  • If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

  • 1 <= nums1.length <= 10^5
  • 1 <= nums2.length <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^7
  • nums1 and nums2 are strictly increasing.

Solution: Two Pointers + DP

Since numbers are strictly increasing, we can always traverse the smaller one using two pointers.
Traversing ([2,4,5,8,10], [4,6,8,10])
will be like [2, 4/4, 5, 6, 8, 10/10]
It two nodes have the same value, we have two choices and pick the larger one, then both move nodes one step forward. Otherwise, the smaller node moves one step forward.
dp1[i] := max path sum ends with nums1[i-1]
dp2[j] := max path sum ends with nums2[j-1]
if nums[i -1] == nums[j – 1]:
dp1[i] = dp2[j] = max(dp[i-1], dp[j-1]) + nums[i -1]
i += 1, j += 1
else if nums[i – 1] < nums[j – 1]:
dp[i] = dp[i-1] + nums[i -1]
i += 1
else if nums[j – 1] < nums[i – 1]:
dp[j] = dp[j-1] + nums[j -1]
j += 1
return max(dp1[-1], dp2[-1])

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

C++

Java

python3

花花酱 LeetCode 1498. Number of Subsequences That Satisfy the Given Sum Condition

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= target <= 10^6

Solution: Two Pointers

Since order of the elements in the subsequence doesn’t matter, we can sort the input array.
Very similar to two sum, we use two pointers (i, j) to maintain a window, s.t. nums[i] +nums[j] <= target.
Then fix nums[i], any subset of (nums[i+1~j]) gives us a valid subsequence, thus we have 2^(j-(i+1)+1) = 2^(j-i) valid subsequence for window (i, j).

Time complexity: O(nlogn) // Sort
Space complexity: O(n) // need to precompute 2^n % kMod.

C++

花花酱 LeetCode 1385. Find the Distance Value Between Two Arrays

Given two integer arrays arr1 and arr2, and the integer dreturn the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1:

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1

Constraints:

  • 1 <= arr1.length, arr2.length <= 500
  • -10^3 <= arr1[i], arr2[j] <= 10^3
  • 0 <= d <= 100

Solution 1: All pairs

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

C++

Python3

Solution 2: Two Pointers

Sort arr1 in ascending order and sort arr2 in descending order.
Time complexity: O(mlogm + nlogn + m + n)
Space complexity: O(1)

C++

Solution 3: Binary Search

Sort arr2 in ascending order. and do two binary searches for each element to determine the range of [a-d, a+d], if that range is empty we increase the counter

Time complexity: O(mlogm + nlogm)
Space complexity: O(1)

C++

花花酱 LeetCode 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Solution 1: Two Pointers

Start from first row + last column, if the current value is larger than target, –column; if smaller then ++row.

e.g.
1. r = 0, c = 4, v = 15, 15 > 5 => –c
2. r = 0, c = 3, v = 11, 11 > 5 => –c
3. r = 0, c = 2, v = 7, 7 > 5 => –c
4. r = 0, c = 1, v = 4, 4 < 5 => ++r
5. r = 1, c = 1, v = 5, 5 = 5, found it!

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

C++