You are given an integer arrayContinue reading “[Leetcode]33. Search in Rotated Sorted Array”`nums`

sorted in ascending order, and an integer`target`

. Suppose that`nums`

is rotated at some pivot unknown to you beforehand (i.e.,`[0,1,2,4,5,6,7]`

might become`[4,5,6,7,0,1,2]`

).If`target`

is found in the array return its index, otherwise, return`-1`

.

## Binary Search – Find Upper and Lower Bound

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**.

## [Leetcode]1508. Range Sum of Sorted Subarray Sums

Given the arrayContinue reading “[Leetcode]1508. Range Sum of Sorted Subarray Sums”`nums`

consisting of`n`

positive 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) / 2`

numbers.Return the sum of the numbers from index`left`

to index`right`

(indexed from 1), inclusive, in the new array.Since the answer can be a huge number return it modulo 10^9 + 7.

## [Leetcode]287. Find the Duplicate Number

Given an arrayContinue reading “[Leetcode]287. Find the Duplicate Number”numscontainingn+ 1 integers where each integer is between 1 andn(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:`[1,3,4,2,2]`

Output:2Note:1. Youmust notmodify 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 thanO(n^{2}). 4. There is only one duplicate number in the array, but it could be repeated more than once.

## [Leetcode problems]1482. Minimum Number of Days to Make m Bouquets

Given an integer arrayContinue reading “[Leetcode problems]1482. Minimum Number of Days to Make m Bouquets”`bloomDay`

, an integer`m`

and an integer`k`

. We need to make`m`

bouquets. To make a bouquet, you need to use`k`

adjacent flowersfrom the garden. The garden consists of`n`

flowers, the`ith`

flower will bloom in the`bloomDay[i]`

and then can be used inexactly onebouquet. Returnthe minimum number of daysyou need to wait to be able to make`m`

bouquets from the garden. If it is impossible to make`m`

bouquets return-1.Example 1:Input:bloomDay = [1,10,3,10,2], m = 3, k = 1Output:3Explanation: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.