two pointers Archives - Page 5 of 7

花花酱 LeetCode 42. Trapping Rain Water

By zxi on January 15, 2020

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

// Author: Huahua

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

int ans = 0;

auto sit = cbegin(height);

auto eit = cend(height);

for (int i = 0; i < n; ++i) {

int l = *max_element(sit, sit + i + 1);

int r = *max_element(sit + i, eit);

ans += min(l, r) - height[i];

}

return ans;

}

};

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

// Author: Huahua

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

vector<int> l(n);

vector<int> r(n);

int ans = 0;

for (int i = 0; i < n; ++i)

l[i] = i == 0 ? height[i] : max(l[i - 1], height[i]);

for (int i = n - 1; i >= 0; --i)

r[i] = i == n - 1 ? height[i] : max(r[i + 1], height[i]);

for (int i = 0; i < n; ++i)

ans += min(l[i], r[i]) - height[i];

return ans;

}

};

Solution 3: Two Pointers

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

C++

// Author: Huahua, 4 ms, 9.1 MB

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

if (n == 0) return 0;

int l = 0;

int r = n - 1;

int max_l = height[l];

int max_r = height[r];

int ans = 0;

while (l < r) {

if (max_l < max_r) {

ans += max_l - height[l];

max_l = max(max_l, height[++l]);

} else {

ans += max_r - height[r];

max_r = max(max_r, height[--r]);

}

return ans;

}

};

花花酱 LeetCode 209. Minimum Size Subarray Sum

By zxi on April 13, 2019

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

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) {

int l = 0;

int r = 0;

int t = 0;

int ans = INT_MAX;

while (l < nums.size()) {

while (t < s && r < nums.size()) t += nums[r++];

if (t < s) break;

ans = min(ans, r - l);

t -= nums[l++];

}

return ans == INT_MAX ? 0 : ans;

}

};

花花酱 LeetCode 125. Valid Palindrome

By zxi on April 10, 2019

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

class Solution {

public:

bool isPalindrome(string s) {

int i = 0;

int j = s.length() - 1;

while (i < j) {

while (i < j && !isalnum(s[i])) ++i;

while (i < j && !isalnum(s[j])) --j;

if (tolower(s[i++]) != tolower(s[j--]))

return false;

}

return true;

}

};

花花酱 LeetCode 992. Subarrays with K Different Integers

By zxi on February 10, 2019

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

Solution: Two pointers + indirection

Let f(x) denote the number of subarrays with x or less distinct numbers.
ans = f(K) – f(K-1)
It takes O(n) Time and O(n) Space to compute f(x)

C++

// Author: Huahua

// vector: 56 ms, 10.1 MB

// Hashtable: 126 ms, 25 MB

class Solution {

public:

int subarraysWithKDistinct(vector<int>& A, int K) {

// Returns the number of subarrays with k or less distinct numbers.

auto subarrys = [&A](int k) {

vector<int> count(A.size() + 1);

int ans = 0;

int i = 0;

for (int j = 0; j < A.size(); ++j) {

if (count[A[j]]++ == 0)

--k;

while (k < 0)

if (--count[A[i++]] == 0) ++k;

ans += j - i + 1;

}

return ans;

};

return subarrys(K) - subarrys(K - 1);

}

};

花花酱 LeetCode 986. Interval List Intersections

By zxi on February 2, 2019

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Solution: Two pointers

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

C++

// Author: Huahua, running time: 36 ms, 925.7 KB

class Solution {

public:

vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {

size_t i = 0;

size_t j = 0;

vector<Interval> ans;

while (i < A.size() && j < B.size()) {

const int s = max(A[i].start, B[j].start);

const int e = min(A[i].end, B[j].end);

if (s <= e) ans.emplace_back(s, e);

if (A[i].end < B[j].end)

++i;

else

++j;

}

return ans;

}

};

Python3

# Author: Huahua, running time: 96 ms, 7.6 MB

class Solution:

def intervalIntersection(self, A: 'List[Interval]', B: 'List[Interval]') -> 'List[Interval]':

i, j, ans = 0, 0, []

while i < len(A) and j < len(B):

s = max(A[i].start, B[j].start)

e = min(A[i].end, B[j].end)

if s <= e:

ans.append(Interval(s, e))

if A[i].end < B[j].end:

i += 1

else:

j += 1

return ans

Posts tagged as “two pointers”

花花酱 LeetCode 42. Trapping Rain Water

Solution 1: Brute Force

C++

Solution 2: DP

C++

Solution 3: Two Pointers

C++

花花酱 LeetCode 209. Minimum Size Subarray Sum

C++

花花酱 LeetCode 125. Valid Palindrome

C++

花花酱 LeetCode 992. Subarrays with K Different Integers

Solution: Two pointers + indirection

C++

Related Problems

花花酱 LeetCode 986. Interval List Intersections

Solution: Two pointers

C++

Python3