Press "Enter" to skip to content

Posts tagged as “two pointers”

花花酱 LeetCode 885. Boats to Save People


The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.  (It is guaranteed each person can be carried by a boat.)

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)


  • 1 <= people.length <= 50000
  • 1 <= people[i] <= limit <= 30000

Solution: Greedy + Two Pointers

Time complexity: O(nlogn)

Space complexity: O(1)

Put one heaviest guy and put the lightest guy if not full.


花花酱 LeetCode 345. Reverse Vowels of a String


Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = “hello”, return “holle”.

Example 2:
Given s = “leetcode”, return “leotcede”.

The vowels does not include the letter “y”.



花花酱 LeetCode 15. 3Sum



Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Solution 1: Hashtable

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

Solution 2: Sorting + Two pointers

Time complexity: O(nlogn + n^2)

Space complexity: O(1)


Related Problems:

花花酱 LeetCode 11. Container With Most Water


Given n non-negative integers a1a2, …, an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.


input: [1 3 2 4]
output: 6
explanation: use 3, 4, we have the following, which contains (4th-2nd) * min(3, 4) = 2 * 3 = 6 unit of water.


Two pointers

Time complexity: O(n)

Space complexity: O(1)


C++ two pointers