Posts published in “Algorithms”

花花酱 LeetCode 1712. Ways to Split Array Into Three Subarrays

By zxi on January 3, 2021

A split of an integer array is good if:

The array is split into three non-empty contiguous subarrays – named left, mid, right respectively from left to right.
The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁴

Solution 1: Prefix Sum + Binary Search

We split the array into [0 … i] [i + 1… j] [j + 1 … n – 1]
we can use binary search to find the min and max of j for each i.
s.t. sum(0 ~ i) <= sums(i + 1 ~j) <= sums(j + 1 ~ n – 1)
min is lower_bound(2 * sums(0 ~ i))
max is upper_bound(sums(0 ~ i) + (total – sums(0 ~ i)) / 2)

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

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

// [0 .. i] [i + 1 ... j] [j + 1 ... n - 1]

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

auto it1 = lower_bound(begin(nums) + i + 1, end(nums), 2 * nums[i]);

auto it2 = upper_bound(begin(nums), end(nums) - 1, nums[i] + (total - nums[i]) / 2);

if (it2 <= it1) continue;

ans += it2 - it1;

}

return ans % kMod;

}

};

Solution 2: Prefix Sum + Two Pointers

The right end of the middle array is in range [j, k – 1] and there are k – j choices.
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

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

j = max(j, i + 1);

while (j < n - 1 && nums[j] < 2 * nums[i]) ++j;

k = max(k, j);

while (k < n - 1 && 2 * nums[k] <= nums[i] + total) ++k;

ans += (k - j);

}

return ans % kMod;

}

};

花花酱 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;

}

};

花花酱 1095. Find in Mountain Array – EP369

By zxi on November 13, 2020

(This problem is an interactive problem.)

You may recall that an array A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
- A[0] < A[1] < ... A[i-1] < A[i]
- A[i] > A[i+1] > ... > A[A.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index doesn’t exist, return -1.

You can’t access the mountain array directly. You may only access the array using a MountainArray interface:

MountainArray.get(k) returns the element of the array at index k (0-indexed).
MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

Constraints:

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9

Solution: Binary Search

Find the peak index of the mountain array using binary search.
Perform two binary searches in two sorted subarrays (ascending one and descending one)

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

C++

class Solution {

public:

int findInMountainArray(int target, MountainArray &mountainArr) {

const int n = mountainArr.length();

auto binary_search = [&](int l, int r, function<bool(int)> cond) {

while (l < r) {

int m = l + (r - l) / 2;

if (cond(m)) r = m;

else l = m + 1;

}

return l;

};

int p = binary_search(0, n - 1, [&](int i) -> bool {

return mountainArr.get(i) > mountainArr.get(i + 1);

});

// if (target > mountainArr.get(p)) return -1;

// if (target == mountainArr.get(p)) return p;

int l = binary_search(0, p, [&](int i) -> bool {

return mountainArr.get(i) >= target;

});

if (mountainArr.get(l) == target) return l;

int r = binary_search(p, n - 1, [&](int i) -> bool {

return mountainArr.get(i) <= target;

});

if (mountainArr.get(r) == target) return r;

return -1;

}

};

python3

class Solution:

def findInMountainArray(self, target: int, arr: 'MountainArray') -> int:

def binary_search(l, r, cond):

while l < r:

m = l + (r - l) // 2

if cond(m): r = m

else: l = m + 1

return l

n = arr.length()

p = binary_search(0, n - 1, lambda i: arr.get(i) > arr.get(i + 1))

l = binary_search(0, p, lambda i: arr.get(i) >= target)

if arr.get(l) == target: return l

r = binary_search(p, n - 1, lambda i: arr.get(i) <= target)

if arr.get(r) == target: return r

return -1