You are given an integer arrayContinue reading “[Leetcode]33. Search in Rotated Sorted Array”
numssorted in ascending order, and an integer
target. Suppose that
numsis rotated at some pivot unknown to you beforehand (i.e.,
targetis found in the array return its index, otherwise, return
This post will introduce one specific application of Binary Search, i.e., when you are asked to find the upper or lower bound, or more precisely, when you need to find the maximum of the smallest value or the minimum of the largest value.Continue reading “Binary Search – Find Upper and Lower Bound”
Given the arrayContinue reading “[Leetcode]1508. Range Sum of Sorted Subarray Sums”
npositive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of
n * (n + 1) / 2numbers. Return the sum of the numbers from index
right(indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Example 1: Input:Continue reading “[Leetcode]287. Find the Duplicate Number”
[1,3,4,2,2]Output: 2 Note: 1. You must not modify the array (assume the array is read only). 2. You must use only constant, O(1) extra space. 3. Your runtime complexity should be less than O(n2). 4. There is only one duplicate number in the array, but it could be repeated more than once.
Given an integer arrayContinue reading “[Leetcode problems]1482. Minimum Number of Days to Make m Bouquets”
bloomDay, an integer
mand an integer
k. We need to make
mbouquets. To make a bouquet, you need to use
kadjacent flowers from the garden. The garden consists of
ithflower will bloom in the
bloomDay[i]and then can be used in exactly one bouquet. Return the minimum number of days you need to wait to be able to make
mbouquets from the garden. If it is impossible to make
mbouquets return -1. Example 1: Input: bloomDay = [1,10,3,10,2], m = 3, k = 1 Output: 3 Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden. We need 3 bouquets each should contain 1 flower. After day 1: [x, _, _, _, _] // we can only make one bouquet. After day 2: [x, _, _, _, x] // we can only make two bouquets. After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.