Press "Enter" to skip to content

Posts tagged as “binary search”

花花酱 LeetCode 1014. Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i].  Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Example 2:

Example 3:

Note:

  1. 1 <= D <= weights.length <= 50000
  2. 1 <= weights[i] <= 500

Solution: Binary Search

Find the smallest capacity such that can finish in D days.

Time complexity: O(n * log(sum(weights))
Space complexity: O(1)

C++

花花酱 LeetCode 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

Example 2:

Solution: Binary Search

Treat the 2D array as a 1D array. matrix[index / cols][index % cols]

Time complexity: O(log(m*n))
Space complexity: O(1)

C++

花花酱 LeetCode 981. Time Based Key-Value Store

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

  • Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

  • Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
  • If there are multiple such values, it returns the one with the largest timestamp_prev.
  • If there are no values, it returns the empty string ("").

Example 1:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"   

Example 2:

Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]

Note:

  1. All key/value strings are lowercase.
  2. All key/value strings have length in the range [1, 100]
  3. The timestamps for all TimeMap.set operations are strictly increasing.
  4. 1 <= timestamp <= 10^7
  5. TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

Solution: HashTable + Map

C++

花花酱 LeetCode 975. Odd Even Jump

You are given an integer array A.  From some starting index, you can make a series of jumps.  The (1st, 3rd, 5th, …) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:

  • During odd numbered jumps (ie. jumps 1, 3, 5, …), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value.  If there are multiple such indexes j, you can only jump to the smallest such index j.
  • During even numbered jumps (ie. jumps 2, 4, 6, …), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value.  If there are multiple such indexes j, you can only jump to the smallest such index j.
  • (It may be the case that for some index i, there are no legal jumps.)

A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

Example 1:

Input: [10,13,12,14,15] 
Output: 2

Example 2:

Input: [2,3,1,1,4] 
Output: 3

Example 3:

Input: [5,1,3,4,2] 
Output: 3

Note:

  1. 1 <= A.length <= 20000
  2. 0 <= A[i] < 100000

Solution: Binary Search + DP

Time complexity: O(nlogn)
Space complexity: O(n)

C++