Posts published in “Array”

花花酱 LeetCode 1749. Maximum Absolute Sum of Any Subarray

By zxi on February 6, 2021

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

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴

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++

// Author: Huahua

class Solution {

public:

int maxAbsoluteSum(vector<int>& nums) {

int lo = 0;

int hi = 0;

int s = 0;

int ans = 0;

for (int x : nums) {

s += x;

ans = max({ans, abs(s - lo), abs(s - hi)});

hi = max(hi, s);

lo = min(lo, s);

}

return ans;

}

};

花花酱 LeetCode1732. Find the Highest Altitude

By zxi on January 23, 2021

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

Solution: Running Max

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

C++

// Author: Huahua

class Solution {

public:

int largestAltitude(vector<int>& gain) {

int ans = 0;

int cur = 0;

for (int diff : gain)

ans = max(ans, cur += diff);

return ans;

}

};

花花酱 LeetCode 1672. Richest Customer Wealth

By zxi on November 29, 2020

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)

C++

// Author: Huahua

class Solution {

public:

int maximumWealth(vector<vector<int>>& accounts) {

int ans = 0;

for (const vector<int>& row : accounts)

ans = max(ans, accumulate(begin(row), end(row), 0));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def maximumWealth(self, accounts: List[List[int]]) -> int:

return max(sum(account) for account in accounts)

花花酱 LeetCode 1664. Ways to Make a Fair Array

By zxi on November 22, 2020

You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.

For example, if nums = [6,1,7,4,1]:

Choosing to remove index 1 results in nums = [6,7,4,1].
Choosing to remove index 2 results in nums = [6,1,4,1].
Choosing to remove index 4 results in nums = [6,1,7,4].

An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.

Return the number of indices that you could choose such that after the removal, numsis fair.

Example 1:

Input: nums = [2,1,6,4]
Output: 1
Explanation:
Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.

Example 2:

Input: nums = [1,1,1]
Output: 3
Explanation: You can remove any index and the remaining array is fair.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: You cannot make a fair array after removing any index.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

Solution: Prefix Sum

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

C++

// Author: Huahua

class Solution {

public:

int waysToMakeFair(vector<int>& nums) {

int n = nums.size();

vector<int> odds(n + 1);

vector<int> evens(n + 1);

for (int i = 0; i < n; ++i) {

odds[i + 1] = odds[i] + (i % 2 == 1) * nums[i];

evens[i + 1] = evens[i] + (i % 2 == 0) * nums[i];

}

int ans = 0;

for (int i = 0; i < n; ++i) {

const int odd = odds[i] + (evens[n] - evens[i + 1]);

const int even = evens[i] + (odds[n] - odds[i + 1]);

ans += odd == even;

}

return ans;

}

};

花花酱 LeetCode 1652. Defuse the Bomb

By zxi on November 14, 2020

You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length of n and a key k.

To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.

If k > 0, replace the i^th number with the sum of the next k numbers.
If k < 0, replace the i^th number with the sum of the previous k numbers.
If k == 0, replace the i^th number with 0.

As code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

Given the circular array code and an integer key k, return the decrypted code to defuse the bomb!

Example 1:

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Example 2:

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is zero, the numbers are replaced by 0.

Example 3:

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the previous numbers.

Constraints:

n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1

Solution 1: Simulation

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

C++

class Solution {

public:

vector<int> decrypt(vector<int>& code, int k) {

const int n = code.size();

vector<int> ans(n);

int sign = k > 0 ? 1 : -1;

for (int i = 0; i < n; ++i)

for (int j = 1; j <= abs(k); ++j)

ans[i] += code[(i + j * sign + n) % n];

return ans;

}

};