KK's blog

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

1 <= nums.length <= 10<sup>5</sup> -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

1
2
3
4
5
6
7
8
9
10

# dp[i] = max(dp[i-1] + nums[i], nums[i])
def maxSubArray(self, nums: List[int]) -> int:
	sum, res = -sys.maxsize, -sys.maxsize
	for num in nums:
		if sum > 0:
			sum += num
		else:
			sum = num
		res = max(sum, res)
	return res

There are n gas stations along a circular route, where the amount of gas at the i<sup>th</sup> station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i<sup>th</sup> station to its next (i + 1)<sup>th</sup> station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

Constraints:

gas.length == n cost.length == n
1 <= n <= 10<sup>5</sup> 0 <= gas[i], cost[i] <= 10<sup>4</sup>

1
2
3
4
5
6
7
8
9
10
11
12

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
	if sum(gas) < sum(cost):
		return -1
	sum_gas, sum_cost, pos = 0, 0, 0
	for i in range(len(gas)):
		sum_gas += gas[i]
		sum_cost += cost[i]
		if sum_gas < sum_cost:
			pos = i + 1
			sum_gas = 0
			sum_cost = 0
	return pos

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 400

1
2
3
4
5
6

def rob(self, nums: List[int]) -> int:
	dp = [0] * (len(nums) + 1)
	dp[1] = nums[0]
	for i in range(2, len(dp)):
		dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
	return dp[-1]

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.

Example 2:

Input: nums = [1,3,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[3], range = 3 - 3 = 0
[3], range = 3 - 3 = 0
[1,3], range = 3 - 1 = 2
[3,3], range = 3 - 3 = 0
[1,3,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.

Example 3:

Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: The sum of all subarray ranges of nums is 59.

Constraints:

1 <= nums.length <= 1000 -10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def subArrayRanges(self, nums: List[int]) -> int:
	arr = list(nums)
	arr.insert(0, -sys.maxsize)
	arr.append(-sys.maxsize)
	stack, res, = [], 0
	for i in range(len(arr)):
		while stack and arr[i] < arr[stack[-1]]:
			prev_idx = stack.pop()
			res -= arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
		stack.append(i)

	arr = list(nums)
	arr.insert(0, sys.maxsize)
	arr.append(sys.maxsize)

	for i in range(len(arr)):
		while stack and arr[i] > arr[stack[-1]]:
			prev_idx = stack.pop()
			res += arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
		stack.append(i)
	return res

1
2
3
4
5
6
7
8
9

def subArrayRanges(self, nums: List[int]) -> int:
	sum = 0
	for i in range(len(nums) - 1):
		min_value, max_value = nums[i], nums[i]
		for j in range(i + 1, len(nums)):
			min_value = min(min_value, nums[j])
			max_value = max(max_value, nums[j])
			sum += max_value - min_value
	return sum

Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [position<sub>i</sub>, amount<sub>i</sub>] depicts amount<sub>i</sub> fruits at the position position<sub>i</sub>. fruits is already sorted by position<sub>i</sub> in ascending order, and each position<sub>i</sub> is unique.

You are also given an integer startPos and an integer k. Initially, you are at the position startPos. From any position, you can either walk to the left or right. It takes one step to move one unit on the x-axis, and you can walk at most k steps in total. For every position you reach, you harvest all the fruits at that position, and the fruits will disappear from that position.

Return the maximum total number of fruits you can harvest.

Example 1:

Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
Output: 9
Explanation:
The optimal way is to:
- Move right to position 6 and harvest 3 fruits
- Move right to position 8 and harvest 6 fruits
You moved 3 steps and harvested 3 + 6 = 9 fruits in total.

Example 2:

Input: fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
Output: 14
Explanation:
You can move at most k = 4 steps, so you cannot reach position 0 nor 10.
The optimal way is to:
- Harvest the 7 fruits at the starting position 5
- Move left to position 4 and harvest 1 fruit
- Move right to position 6 and harvest 2 fruits
- Move right to position 7 and harvest 4 fruits
You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.

Example 3:

Input: fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
Output: 0
Explanation:
You can move at most k = 2 steps and cannot reach any position with fruits.

Constraints:

1 <= fruits.length <= 10<sup>5</sup> fruits[i].length == 2
`0 <= startPos, position<sub>i</sub> <= 2 10<sup>5</sup>*position<sub>i-1</sub> < position<sub>i</sub>for anyi > 0(**0-indexed**) *1 <= amount<sub>i</sub> <= 10<sup>4</sup>*0 <= k <= 2 * 10<sup>5</sup>`

1
2
3
4
5
6
7
8
9
10
11
12
13

def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
	pos_to_fruits = collections.defaultdict(int)
	for pair in fruits:
		pos_to_fruits[pair[0]] = pair[1]
	presum = collections.defaultdict(int)
	presum[startPos - k - 1] = pos_to_fruits[startPos - k - 1]
	for i in range(startPos - k, startPos + k + 1):
		presum[i] += presum[i-1] + pos_to_fruits[i]
	res = 0
	for i in range(k//2 + 1):
		res = max(res, presum[startPos + k - i * 2] - presum[startPos - i - 1])
		res = max(res, presum[startPos + i] - presum[startPos - k + i * 2 - 1])
	return res