Leetcode 2586: Count the Number of Vowel Strings in Range

Input: The input consists of an integer array `nums`.

Example: For example, `nums = [3, -1, 4, 2, -3, 1, -2]`.

Constraints:

• 1 <= nums.length <= 10^5

• -10^6 <= nums[i] <= 10^6

Output: The output is an integer that represents the maximum score achieved by rearranging the elements of `nums`.

Example: For `nums = [3, -1, 4, 2, -3, 1, -2]`, the output is `5`.

Constraints:

• The result will always be a valid integer.

Goal: The goal is to rearrange the array `nums` to maximize the number of positive integers in the prefix sum array.

Steps:

• 1. Rearrange the array `nums` to maximize positive prefix sums.

• 2. Calculate the prefix sum array and count the number of positive values.

• 3. Return the count as the maximum score.

Goal: The array contains between 1 and 10^5 integers, and each integer is between -10^6 and 10^6.

Steps:

• 1 <= nums.length <= 10^5

• -10^6 <= nums[i] <= 10^6

Assumptions:

• The input array contains valid integers within the given range.

• Input: For `nums = [3, -1, 4, 2, -3, 1, -2]`

• Explanation: The optimal rearrangement is `nums = [3, 4, 2, 1, -1, -2, -3]`. The prefix sum array becomes `prefix = [3, 7, 9, 10, 9, 7, 4]`, giving a score of 5.

Approach: To solve this problem, we need to rearrange the array `nums` to maximize the number of positive prefix sums. A good strategy is to place the positive numbers at the beginning of the array and the negative numbers towards the end.

Observations:

• By placing the positive numbers first, we maximize the possibility of obtaining positive prefix sums.

• This approach helps ensure that the sum remains positive as we calculate the prefix sums.

Steps:

• 1. Separate the positive numbers and negative numbers from the array `nums`.

• 2. Place the positive numbers first in the rearranged array.

• 3. Calculate the prefix sum array and count how many positive numbers appear.

• 4. Return the count as the result.

Empty Inputs:

• The problem guarantees that the array will not be empty.

Large Inputs:

• The solution should be efficient enough to handle up to 10^5 elements in the array.

Special Values:

• If the array contains only negative values, the score will always be 0.

Constraints:

• The length of the array is guaranteed to be within the specified limits.

bool check(char s)
{
    return (s=='a' || s=='e'|| s=='o'|| s=='i' || s=='u');
}
int vowelStrings(vector<string>& words, int left, int right) {
    int ans=0;
    for(int i=left;i<=right;i++)
    {
        if(check(words[i].front()) && check(words[i].back())) ans++;
    }
    return ans;
}

1 : Function Declaration

bool check(char s)

This function checks whether the given character 's' is a vowel (either 'a', 'e', 'i', 'o', or 'u').

2 : Return Statement

    return (s=='a' || s=='e'|| s=='o'|| s=='i' || s=='u');

This line returns true if the character 's' is a vowel; otherwise, false.

3 : Function Declaration

int vowelStrings(vector<string>& words, int left, int right) {

This function counts the number of words in the 'words' vector from index 'left' to 'right' where both the first and last characters are vowels.

4 : Variable Declaration

    int ans=0;

This declares and initializes a variable 'ans' to zero, which will be used to count the words with vowels at both ends.

5 : For Loop

    for(int i=left;i<=right;i++)

This loop iterates over the 'words' vector from index 'left' to 'right'.

6 : If Condition

        if(check(words[i].front()) && check(words[i].back())) ans++;

This condition checks if both the first and last characters of the current word are vowels. If true, it increments the 'ans' counter.

7 : Return Statement

    return ans;

This returns the count of words where both the first and last characters are vowels.

Best Case: O(n)

Average Case: O(n log n)

Worst Case: O(n log n)

Description: The best case occurs when the array is already arranged optimally. The worst case is when we need to sort the array, which takes O(n log n).

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the additional storage required for separating positive and negative numbers.

Leetcode 2586: Count the Number of Vowel Strings in Range

Explore →