Press "Enter" to skip to content

Posts tagged as “two pointers”

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

花花酱 LeetCode 42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution 1: Brute Force

r[i] = min(max(h[0:i+1]), max(h[i:n]))
ans = sum(r[i])

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

C++

Solution 2: DP

l[i] := max(h[0:i+1])
r[i] := max(h[i:n])
ans = sum(min(l[i], r[i]) – h[i])

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

C++

Solution 3: Two Pointers

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

C++

花花酱 LeetCode 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguoussubarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n). 

Solution 1: Two Pointers (Sliding Window)

Maintain a sliding window [l, r) such that sum(nums[l:r)) >= s, then move l to l + 1, and move r accordingly to make the window valid.

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

C++

花花酱 LeetCode 125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Solution: Two pointers

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

C++