单序列相向双指针 One Sequence Two Pointers Opposite Direction¶

Table of Contents¶

344. Reverse String¶

LeetCode | 力扣
Tags: Two Pointers, String

PythonCPP

from typing import List


def reverseString(s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    left, right = 0, len(s) - 1

    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1


s = ["h", "e", "l", "l", "o"]
reverseString(s)
print(s)  # ['o', 'l', 'l', 'e', 'h']

#include <cassert>
#include <vector>
using namespace std;

class Solution {
   public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);

            left++;
            right--;
        }
    }
};

int main() {
    Solution solution;
    vector<char> s = {'h', 'e', 'l', 'l', 'o'};
    solution.reverseString(s);
    assert(s == vector<char>({'o', 'l', 'l', 'e', 'h'}));
    return 0;
}

541. Reverse String II¶

LeetCode | 力扣
Tags: Two Pointers, String

Python

def reverseStr(s: str, k: int) -> str:
    def reverse_substring(text):
        left, right = 0, len(text) - 1
        while left < right:
            text[left], text[right] = text[right], text[left]
            left += 1
            right -= 1
        return text

    result = list(s)

    for i in range(0, len(s), 2 * k):
        result[i : i + k] = reverse_substring(result[i : i + k])

    return "".join(result)


s = "abcdefg"
k = 2
print(reverseStr(s, k))  # "bacdfeg"

557. Reverse Words in a String III¶

LeetCode | 力扣
Tags: Two Pointers, String

345. Reverse Vowels of a String¶

LeetCode | 力扣
Tags: Two Pointers, String

917. Reverse Only Letters¶

LeetCode | 力扣
Tags: Two Pointers, String

125. Valid Palindrome¶

LeetCode | 力扣
Tags: Two Pointers, String

Python

# List Comprehension
def isPalindrome(s: str) -> bool:
    s = [char.lower() for char in s if char.isalnum()]
    return s == s[::-1]


# Left Right Pointers
def isPalindromeLR(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True


s = "A man, a plan, a canal: Panama"
print(isPalindrome(s))  # True
print(isPalindromeLR(s))  # True

1750. Minimum Length of String After Deleting Similar Ends¶

LeetCode | 力扣
Tags: Two Pointers, String

Python

# Sliding Window Variable Size
def minimumLength(s: str) -> int:
    left, right = 0, len(s) - 1

    while left < right and s[left] == s[right]:
        val = s[left]

        while left <= right and s[left] == val:
            left += 1
        while left <= right and s[right] == val:
            right -= 1

    return right - left + 1


print(minimumLength("cabaabac"))  # 0
print(minimumLength("aabccabba"))  # 3

2105. Watering Plants II¶

LeetCode | 力扣
Tags: Array, Two Pointers, Simulation

Python

from typing import List


# Right Left Pointers
def minimumRefill(plants: List[int], capacityA: int, capacityB: int) -> int:
    i, j = 0, len(plants) - 1
    a, b = capacityA, capacityB
    res = 0

    while i < j:
        if a < plants[i]:
            res += 1
            a = capacityA
        if b < plants[j]:
            res += 1
            b = capacityB

        a -= plants[i]
        b -= plants[j]
        i += 1
        j -= 1

    if i == j and max(a, b) < plants[i]:
        res += 1

    return res


if __name__ == "__main__":
    assert minimumRefill([2, 2, 3, 3], 5, 5) == 1
    assert minimumRefill([2, 2, 3, 3], 3, 4) == 2
    assert minimumRefill([5, 5], 10, 10) == 0
    assert minimumRefill([1, 2, 4, 4], 4, 4) == 1
    assert minimumRefill([1, 1, 1], 2, 2) == 0

977. Squares of a Sorted Array¶

LeetCode | 力扣
Tags: Array, Two Pointers, Sorting

Python

from typing import List


# Left Right Pointers
def sortedSquares(nums: List[int]) -> List[int]:
    """Returns the squares of the sorted array."""
    n = len(nums)
    result = [0 for _ in range(n)]

    left, right, tail = 0, n - 1, n - 1

    while left <= right:
        if abs(nums[left]) >= abs(nums[right]):
            result[tail] = nums[left] ** 2
            left += 1
        else:
            result[tail] = nums[right] ** 2
            right -= 1
        tail -= 1

    return result


# |---------------------|------|-------|
# | Approach            | Time | Space |
# |---------------------|------|-------|
# | Left Right Pointers | O(n) | O(n)  |
# |---------------------|------|-------|


nums = [-4, -1, 0, 3, 10]
print(sortedSquares(nums))  # [0, 1, 9, 16, 100]

658. Find K Closest Elements¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Sliding Window, Sorting, Heap Priority Queue

1471. The k Strongest Values in an Array¶

LeetCode | 力扣
Tags: Array, Two Pointers, Sorting

167. Two Sum II - Input Array Is Sorted¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search

Python

from typing import List


# Left Right Pointers
def twoSum(numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1

    while left < right:
        total = numbers[left] + numbers[right]

        if total > target:
            right -= 1
        elif total < target:
            left += 1
        else:
            return [left + 1, right + 1]


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# | Left Right |  O(n)  |  O(1)   |
# |------------|--------|---------|


numbers = [2, 7, 11, 15]
target = 9
print(twoSum(numbers, target))  # [1, 2]

633. Sum of Square Numbers¶

LeetCode | 力扣
Tags: Math, Two Pointers, Binary Search

2824. Count Pairs Whose Sum is Less than Target¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Sorting

2563. Count the Number of Fair Pairs¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Sorting

15. 3Sum¶

LeetCode | 力扣
Tags: Array, Two Pointers, Sorting

PythonCPP

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """Two Pointers: O(n^2) time, O(1) space.
        Sort, fix one element, then two-pointer scan for complement.
        """
        n = len(nums)
        if n <= 2:
            return []

        res = []
        nums.sort()

        for k in range(n - 2):
            if k > 0 and nums[k] == nums[k - 1]:
                continue

            i, j = k + 1, n - 1

            while i < j:
                total = nums[k] + nums[i] + nums[j]

                if total > 0:
                    j -= 1
                elif total < 0:
                    i += 1
                else:
                    res.append([nums[k], nums[i], nums[j]])

                    while i < j and nums[i] == nums[i + 1]:
                        i += 1
                    while i < j and nums[j] == nums[j - 1]:
                        j -= 1

                    i += 1
                    j -= 1

        return res


def test_three_sum():
    s = Solution()
    for fn in (s.threeSum,):
        assert fn([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
        assert fn([0, 1, 1]) == []
        assert fn([0, 0, 0]) == [[0, 0, 0]]
        assert fn([]) == []

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int left = i + 1, right = n - 1;

        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];

            if (total > 0)
                right--;
            else if (total < 0)
                left++;
            else {
                res.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = threeSum(nums);
    for (auto& v : res) {
        for (int i : v) {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

16. 3Sum Closest¶

LeetCode | 力扣
Tags: Array, Two Pointers, Sorting

PythonCPP

from typing import List


# Left Right Pointers
def threeSumClosest(nums: List[int], target: int) -> int:
    nums.sort()
    n = len(nums)
    res = 0
    minDiff = float("inf")

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total > target:
                if total - target < minDiff:
                    minDiff = total - target
                    res = total
                right -= 1

            elif total < target:
                if target - total < minDiff:
                    minDiff = target - total
                    res = total
                left += 1

            else:
                return total

    return res


nums = [-1, 2, 1, -4]
target = 1
assert threeSumClosest(nums, target) == 2

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int res = 0;
    int minDiff = INT_MAX;

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = n - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];

            int diff = abs(total - target);
            if (diff < minDiff) {
                minDiff = diff;
                res = total;
            }

            if (total > target)
                right--;
            else if (total < target)
                left++;
            else
                return total;
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1, 2, 1, -4};
    int target = 1;
    cout << threeSumClosest(nums, target) << endl;
    return 0;
}

18. 4Sum¶

LeetCode | 力扣
Tags: Array, Two Pointers, Sorting

Python

from typing import List


# Left Right Pointers
def fourSum(nums: List[int], target: int) -> List[List[int]]:
    """Returns all unique quadruplets that sum up to the target."""
    nums.sort()
    result = []

    for i in range(len(nums) - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, len(nums) - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            left = j + 1
            right = len(nums) - 1

            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]

                if total > target:
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1

    return result


nums = [1, 0, -1, 0, -2, 2]
target = 0
print(fourSum(nums, target))
# [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

611. Valid Triangle Number¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Greedy, Sorting

1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers¶

LeetCode | 力扣
Tags: Array, Hash Table, Math, Two Pointers

923. 3Sum With Multiplicity¶

LeetCode | 力扣
Tags: Array, Hash Table, Two Pointers, Sorting, Counting

948. Bag of Tokens¶

LeetCode | 力扣
Tags: Array, Two Pointers, Greedy, Sorting

11. Container With Most Water¶

LeetCode | 力扣
Tags: Array, Two Pointers, Greedy

PythonCPP

from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        """Two Pointers: O(n) time, O(1) space.
        Move the shorter side inward to potentially find a taller line.
        """
        left, right = 0, len(height) - 1
        res = 0

        while left < right:
            w = right - left
            h = min(height[left], height[right])
            res = max(res, w * h)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return res

    def maxAreaBF(self, height: List[int]) -> int:
        """Brute Force: O(n^2) time, O(1) space.
        Check every pair of lines.
        """
        res = 0
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                res = max(res, min(height[i], height[j]) * (j - i))
        return res


def test_max_area():
    s = Solution()
    for fn in (s.maxArea, s.maxAreaBF):
        assert fn([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
        assert fn([1, 1]) == 1
        assert fn([4, 3, 2, 1, 4]) == 16
        assert fn([1, 2, 1]) == 2

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int res = 0;

    while (left < right) {
        int h = min(height[left], height[right]);
        int w = right - left;
        res = max(res, h * w);

        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return res;
}

int main() {
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << maxArea(height) << endl;  // 49
    return 0;
}

42. Trapping Rain Water¶

LeetCode | 力扣
Tags: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

PythonCPP

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        """Two Pointers: O(n) time, O(1) space.
        Track max from each side; shorter side determines water level.
        """
        left, right = 0, len(height) - 1
        max_l = max_r = res = 0
        while left < right:
            if height[left] < height[right]:
                max_l = max(max_l, height[left])
                res += max_l - height[left]
                left += 1
            else:
                max_r = max(max_r, height[right])
                res += max_r - height[right]
                right -= 1
        return res

    def trapDP(self, height: List[int]) -> int:
        """DP Prefix Max: O(n) time, O(n) space.
        Precompute max heights from left and right.
        """
        n = len(height)
        max_left = [0] * n
        max_right = [0] * n
        for i in range(1, n):
            max_left[i] = max(max_left[i - 1], height[i - 1])
        for i in range(n - 2, -1, -1):
            max_right[i] = max(max_right[i + 1], height[i + 1])
        return sum(max(0, min(max_left[i], max_right[i]) - height[i]) for i in range(n))

    def trapStack(self, height: List[int]) -> int:
        """Monotonic Stack: O(n) time, O(n) space.
        Pop shorter bars and accumulate trapped water by layer.
        """
        stack = []
        res = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                w = i - stack[-1] - 1
                h = min(height[i], height[stack[-1]]) - height[top]
                res += w * h
            stack.append(i)
        return res


def test_trap():
    s = Solution()
    for fn in (s.trap, s.trapDP, s.trapStack):
        assert fn([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
        assert fn([4, 2, 0, 3, 2, 5]) == 9
        assert fn([1, 0, 1]) == 1
        assert fn([]) == 0

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        if (height.empty())
            return 0;

        int res = 0;
        int left = 0, right = height.size() - 1;
        int maxL = height[left], maxR = height[right];

        while (left < right)
        {
            if (maxL < maxR)
            {
                left++;
                maxL = max(maxL, height[left]);
                res += maxL - height[left];
            }
            else
            {
                right--;
                maxR = max(maxR, height[right]);
                res += maxR - height[right];
            }
        }
        return res;
    }
};

int main()
{
    vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    Solution solution;
    cout << solution.trap(height) << endl;
    return 0;
}

1616. Split Two Strings to Make Palindrome¶

LeetCode | 力扣
Tags: Two Pointers, String

1498. Number of Subsequences That Satisfy the Given Sum Condition¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Sorting

1782. Count Pairs Of Nodes¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Graph, Sorting

1099. Two Sum Less Than K 👑¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Sorting

Python

from typing import List


# Left Right Pointers
def twoSumLessThanK(nums: List[int], k: int) -> int:
    nums.sort()
    left, right = 0, len(nums) - 1
    res = float("-inf")

    while left < right:
        total = nums[left] + nums[right]

        if total >= k:
            right -= 1
        else:
            res = max(res, total)
            left += 1

    return res if res != float("-inf") else -1


nums = [34, 23, 1, 24, 75, 33, 54, 8]
k = 60
print(twoSumLessThanK(nums, k))  # 58

360. Sort Transformed Array 👑¶

LeetCode | 力扣
Tags: Array, Math, Two Pointers, Sorting

2422. Merge Operations to Turn Array Into a Palindrome 👑¶

LeetCode | 力扣
Tags: Array, Two Pointers, Greedy

259. 3Sum Smaller 👑¶

LeetCode | 力扣
Tags: Array, Two Pointers, Binary Search, Sorting