Posts tagged as “sum”

You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the i​​​​​​​​​​​th​​​​ customer has in the j​​​​​​​​​​​th​​​​ bank. Return the wealth that the richest customer has.

A customer’s wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

Example 1:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.


Example 2:

Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation:
1st customer has wealth = 6
2nd customer has wealth = 10
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.

Example 3:

Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17


Constraints:

• m == accounts.length
• n == accounts[i].length
• 1 <= m, n <= 50
• 1 <= accounts[i][j] <= 100

Solution: Sum each row up

Time complexity: O(mn)
Space complexity: O(1)

Python3

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer weirdly values the colored balls. Each colored ball’s value is the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, inventory, where inventory[i] represents the number of balls of the ith color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.


Example 2:

Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.


Example 3:

Input: inventory = [2,8,4,10,6], orders = 20
Output: 110


Example 4:

Input: inventory = [1000000000], orders = 1000000000
Output: 21
Explanation: Sell the 1st color 1000000000 times for a total value of 500000000500000000. 500000000500000000 modulo 109 + 7 = 21.


Constraints:

• 1 <= inventory.length <= 105
• 1 <= inventory[i] <= 109
• 1 <= orders <= min(sum(inventory[i]), 109)

Solution: Greedy

1. Sort the colors by # of balls in descending order.
e.g. 3 7 5 1 => 7 5 3 1
2. Sell the color with largest number of balls until it has the same number of balls of next color
1. 7 5 3 1 => 6 5 3 1 => 5 5 3 1 # value = 7 + 6 = 13
2. 5 5 3 1 => 4 4 3 1 => 3 3 3 1 # value = 13 + (5 + 4) * 2 = 31
3. 3 3 3 1 => 2 2 2 1 => 1 1 1 1 # value = 31 + (3 + 2) * 3 = 46
4. 1 1 1 1 => 0 0 0 0 # value = 46 + 1 * 4 = 50
3. Need to handle the case if orders < total balls…

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

C++

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.


Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.


Constraints:

• 1 <= arr.length <= 10^5
• -10^4 <= arr[i] <= 10^4

Solution: DP

First, handle the special case: all numbers are negative, return the max one.

s0 = max subarray sum ends with a[i]
s1 = max subarray sum ends with a[i] with at most one deletion

whenever s0 or s1 becomes negative, reset them to 0.

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

C++

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.


Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.


Constraints:

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

Solution: Summation

1. compute the total sum
2. compute the sum from s to d, c
3. ans = min(c, sum – c)

Time complexity: O(d-s)
Space complexity: O(1)

Problem

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index].  Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries.  Your answer array should have answer[i] as the answer to the i-th query.

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation:
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.


Note:

1. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. 1 <= queries.length <= 10000
4. -10000 <= queries[i][0] <= 10000
5. 0 <= queries[i][1] < A.length

Solution: Simulation

Time complexity: O(n + |Q|)
Space complexity: O(n)