Posts tagged as “prefix sum”

Given an array of positive integers nums, return the maximum possible sum of an ascending subarray in nums.

A subarray is defined as a contiguous sequence of numbers in an array.

A subarray [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i where l <= i < rnumsi < numsi+1. Note that a subarray of size 1 is ascending.

Example 1:

Input: nums = [10,20,30,5,10,50]
Output: 65
Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.


Example 2:

Input: nums = [10,20,30,40,50]
Output: 150
Explanation: [10,20,30,40,50] is the ascending subarray with the maximum sum of 150.


Example 3:

Input: nums = [12,17,15,13,10,11,12]
Output: 33
Explanation: [10,11,12] is the ascending subarray with the maximum sum of 33.


Example 4:

Input: nums = [100,10,1]
Output: 100


Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

Solution: Running sum with resetting

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

Track the running sum and reset it to zero if nums[i] <= nums[i – 1]

C++

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.


Example 2:

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

Constraints:

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] is either '0' or '1'

Solution: Prefix Sum + DP

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

C++

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

• If x is a negative integer, then abs(x) = -x.
• If x is a non-negative integer, then abs(x) = x.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.


Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.


Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Solution: Prefix Sum

ans = max{abs(prefix_sum[i] – max(prefix_sum[0:i])), abs(prefix_sum – min(prefix_sum[0:i])}

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

C++

You are given an integer array, nums, and an integer knums comprises of only 0‘s and 1‘s. In one move, you can choose two adjacent indices and swap their values.

Return the minimum number of moves required so that nums has k consecutive 1‘s.

Example 1:

Input: nums = [1,0,0,1,0,1], k = 2
Output: 1
Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.


Example 2:

Input: nums = [1,0,0,0,0,0,1,1], k = 3
Output: 5
Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].


Example 3:

Input: nums = [1,1,0,1], k = 2
Output: 0
Explanation: nums already has 2 consecutive 1's.


Constraints:

• 1 <= nums.length <= 105
• nums[i] is 0 or 1.
• 1 <= k <= sum(nums)

Solution: Prefix Sum + Sliding Window

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

We only care positions of 1s, we can move one element from position x to y (assuming x + 1 ~ y are all zeros) in y – x steps. e.g. [0 0 1 0 0 0 1] => [0 0 0 0 0 1 1], move first 1 at position 2 to position 5, cost is 5 – 2 = 3.

Given a size k window of indices of ones, the optimal solution it to use the median number as center. We can compute the cost to form consecutive numbers:

e.g. [1 4 7 9 10] => [5 6 7 8 9] cost = (5 – 1) + (6 – 4) + (9 – 8) + (10 – 9) = 8

However, naive solution takes O(n*k) => TLE.

We can use prefix sum to compute the cost of a window in O(1) to reduce time complexity to O(n)

First, in order to use sliding window, we change the target of every number in the window to the median number.
e.g. [1 4 7 9 10] => [7 7 7 7 7] cost = (7 – 1) + (7 – 4) + (7 – 7) + (9 – 7) + (10 – 7) = (9 + 10) – (1 + 4) = right – left.
[5 6 7 8 9] => [7 7 7 7 7] takes extra 2 + 1 + 1 + 2 = 6 steps = (k / 2) * ((k + 1) / 2), these extra steps should be deducted from the final answer.

Python3

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Example 1:

Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.


Example 2:

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]


Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i] <= nums[i + 1] <= 104

Solution: Prefix Sum

Let s[i] denote sum(num[i] – num[j]) 0 <= j <= i
s[i] = s[i – 1] + (num[i] – num[i – 1]) * i
Let l[i] denote sum(nums[j] – nums[i]) i <= j < n
l[i] = l[i + 1] + (nums[i + 1] – num[i]) * (n – i – 1)
ans[i] = s[i] + l[i]

e.g. 1, 3, 7, 9
s[0] = 0
s[1] = 0 + (3 – 1) * 1 = 2
s[2] = 2 + (7 – 3) * 2 = 10
s[3] = 10 + (9 – 7) * 3 = 16
l[3] = 0
l[2] = 0 + (9 – 7) * 1 = 2
l[1] = 2 + (7 – 3) * 2 = 10
l[0] = 10 + (3 – 1) * 3 = 16

ans = [16, 12, 12, 16]

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