Posts tagged as “array”

LeetCode 1422. Maximum Score After Splitting a String

By zxi on April 25, 2020

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

2 <= s.length <= 500
The string s consists of characters ‘0’ and ‘1’ only.

Solution 1: Brute Force

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

Solution 2: Counting

2.1 Two passes,
1st, count the number of ones of the entire string
2nd, inc zeros or dec ones according to s[i]
ans = max(zeros + ones)

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(string s) {

int ones = 0;

for (char c : s)

if (c == '1') ++ones;

int zeros = 0;

int ans = 0;

for (int i = 0; i < s.length() - 1; ++i) {

if (s[i] == '0') ++zeros;

else --ones;

ans = max(ans, zeros + ones);

}

return ans;

}

};

花花酱 LeetCode 1403. Minimum Subsequence in Non-Increasing Order

By zxi on April 4, 2020

Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.

If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.

Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.

Example 1:

Input: nums = [4,3,10,9,8]
Output: [10,9] 
Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included, however, the subsequence [10,9] has the maximum total sum of its elements.

Example 2:

Input: nums = [4,4,7,6,7]
Output: [7,7,6] 
Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to returned in non-decreasing order.

Example 3:

Input: nums = [6]
Output: [6]

Constraints:

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

Solution: Greedy

Sort the elements in reverse order, pick the largest elements until their sum is greater than the sum of the left elements or total / 2.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> minSubsequence(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

int total = accumulate(begin(nums), end(nums), 0);

vector<int> ans;

int sum = 0;

for (int v : nums) {

sum += v;

ans.push_back(v);

if (sum > total / 2) break;

}

return ans;

}

};

花花酱 LeetCode 1402. Reducing Dishes

By zxi on April 4, 2020

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i]*satisfaction[i]

Return the maximum sum of Like-time coefficient that the chef can obtain after dishes preparation.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

Example 1:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total Like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.

Example 2:

Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People don't like the dishes. No dish is prepared.

Example 4:

Input: satisfaction = [-2,5,-1,0,3,-3]
Output: 35

Constraints:

n == satisfaction.length
1 <= n <= 500
-10^3 <= satisfaction[i] <= 10^3

Solution 1: Sort + Brute Force

Time complexity: O(nlogn + n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxSatisfaction(vector<int>& s) {

const int n = s.size();

sort(begin(s), end(s));

int ans = 0;

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

int v = 0;

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

v += s[j] * (j - i + 1);

ans = max(ans, v);

}

return ans;

}

};

Solution 2: Sort + prefix sum

Sort in reverse order, accumulate prefix sum until prefix sum <= 0.

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

[9, 8, 5, 2, 1, -1]
sum = 9 * 4 + 8 * 3 + 2 * 3 + 1 * 2 + -1 * 1
<=>
sum += 9
sum += (9 + 8 = 17)
sum += (17 + 2 = 19)
sum += (19 + 1 = 20)
sum += (20 – 1 = 19)

C++

// Author: Huahua

class Solution {

public:

int maxSatisfaction(vector<int>& s) {

const int n = s.size();

sort(rbegin(s), rend(s));

int ans = 0;

int prefix = 0;

for (int v : s) {

prefix += v;

if (prefix <= 0) break;

ans += prefix;

}

return ans;

}

};

花花酱 LeetCode 1395. Count Number of Teams

By zxi on March 28, 2020

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

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

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

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

if (rating[i] < rating[j] && rating[j] < rating[k]

|| rating[i] > rating[j] && rating[j] > rating[k])

++ans;

return ans;

}

};

Solution 2: Math

For each soldier j, count how many soldiers on his left has smaller ratings as left[j], count how many soldiers his right side has larger ratings as right[j]

ans = sum(left[j] * right[j] + (j – left[j]) * (n – j – 1 * right[j])

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

C++

// Author: Huahua, 4 ms

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

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

int l = 0;

int r = 0;

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

if (rating[i] < rating[j]) ++l;

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

if (rating[j] < rating[k]) ++r;

ans += (l * r) + (j - l) * (n - j - 1 - r);

}

return ans;

}

};

花花酱 LeetCode 1375. Bulb Switcher III

By zxi on March 8, 2020

There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.

At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.

Return the number of moments in which all turned on bulbs are blue.

Example 1:

Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

Example 2:

Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).

Example 3:

Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.

Example 4:

Input: light = [2,1,4,3,6,5]
Output: 3

Example 5:

Input: light = [1,2,3,4,5,6]
Output: 6

Constraints:

n == light.length
1 <= n <= 5 * 10^4
light is a permutation of [1, 2, ..., n]

Solution

Track the right most light l_k, all turned-on lights are blue if and only if the right most one is k, and there are exact k lights on right now.

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

C++

// Author: Huahua

class Solution {

public:

int numTimesAllBlue(vector<int>& light) {

int ans = 0;

int right = 0;

for (int i = 0; i < light.size(); ++i) {

right = max(right, light[i]);

ans += right == i + 1;

}

return ans;

}

};