Press "Enter" to skip to content

Posts published in “Two pointers”

花花酱 LeetCode 786. K-th Smallest Prime Fraction


A sorted list A contains 1, plus some number of primes.  Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered?  Return your answer as an array of ints, where answer[0] = p and answer[1] = q.


  • A will have length between 2 and 2000.
  • Each A[i] will be between 1 and 30000.
  • K will be between 1 and A.length * (A.length + 1) / 2.

Solution 1: Binary Search

Binary search m, 0 < m < 1, such that there are exact k pairs of (i, j) that A[i] / A[j] < m

Time complexity: O(n*C) C <= 31




Related Problems:

花花酱 LeetCode 167. Two Sum II – Input array is sorted


Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2


C++ / two pointers

Time complexity: O(n)

Space complexity: O(1)


C++ / Binary search

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