Solve stock and banana problems

Solve both coding problems below.

1. Maximum single-transaction stock profit: Given an array prices where prices[i] is the stock price on day i, return the maximum profit obtainable by choosing one day to buy and a later day to sell. If no profit is possible, return 0.

2. Minimum banana-eating speed: Given an array piles where piles[i] is the number of bananas in pile i, and an integer h representing the total number of hours available, find the minimum integer eating speed k such that a monkey can finish all piles within h hours. In one hour, the monkey chooses one pile and eats up to k bananas from that pile.

For each problem, explain your algorithm and analyze time and space complexity.

Part 1: Maximum Single-Transaction Stock Profit

You are given an array prices where prices[i] is the stock price on day i. Choose one day to buy the stock and a later day to sell it. Return the maximum profit you can achieve from this single transaction. If no profitable transaction is possible, return 0.

A good algorithm scans the array once, keeping track of the minimum price seen so far and the best profit seen so far.

Constraints

• 0 <= len(prices) <= 100000
• 0 <= prices[i] <= 100000

Examples

Example 1

Input: ([7, 1, 5, 3, 6, 4],)
Output: 5

Explanation: Buy at 1 and sell later at 6 for a profit of 5.

Example 2

Input: ([7, 6, 4, 3, 1],)
Output: 0

Explanation: Prices keep decreasing, so no profitable sell is possible.

Hints

1. As you move from left to right, what is the only information you need from previous days to evaluate selling today?
2. Keep track of the lowest price seen so far, then compare each current price against it.

Part 2: Minimum Banana-Eating Speed

You are given an array piles where piles[i] is the number of bananas in the ith pile, and an integer h representing the number of hours available. In one hour, the monkey chooses exactly one pile and eats up to k bananas from that pile. Find the minimum integer eating speed k such that all bananas can be eaten within h hours.

A strong approach uses binary search on the answer: if a given speed works, then any faster speed also works.

Constraints

• 1 <= len(piles) <= 10000
• 1 <= piles[i] <= 1000000000
• len(piles) <= h <= 1000000000

Examples

Example 1

Input: ([3, 6, 7, 11], 8)
Output: 4

Explanation: At speed 4, the hours needed are 1 + 2 + 2 + 3 = 8, which fits exactly.

Example 2

Input: ([30, 11, 23, 4, 20], 5)
Output: 30

Explanation: There are 5 piles and only 5 hours, so each pile must be finished in one hour. The largest pile requires speed 30.

Hints

1. For a fixed speed k, compute the total hours by summing the ceiling of pile / k for each pile.
2. If speed k is fast enough, then any speed greater than k is also fast enough. That monotonic property suggests binary search.