Leetcode 2012: Sum of Beauty in the Array
You are given an integer array ’nums’. For each index i (1 <= i <= nums.length - 2), calculate the beauty of nums[i] based on the following conditions:
- The beauty of nums[i] is 2 if for all indices j before i and for all indices k after i, nums[j] < nums[i] < nums[k].
- The beauty of nums[i] is 1 if nums[i-1] < nums[i] < nums[i+1] but the previous condition is not met.
- The beauty of nums[i] is 0 if neither of the above conditions holds.
Return the sum of beauty values for all nums[i] where 1 <= i <= nums.length - 2.
Problem
Approach
Steps
Complexity
Input: You are given a list of integers, nums, representing the array.
Example: nums = [1, 5, 3, 6, 2]
Constraints:
• 3 <= nums.length <= 100000
• 1 <= nums[i] <= 100000
Output: Return the sum of beauty of all nums[i] where 1 <= i <= nums.length - 2.
Example: Output: 3
Constraints:
• The result will be a non-negative integer.
Goal: The goal is to efficiently calculate the sum of beauties for all indices i where 1 <= i <= nums.length - 2.
Steps:
• Precompute the 'left' and 'right' arrays that hold the smallest and largest values for each index i respectively.
• Iterate over the array and calculate the beauty for each index based on the given conditions.
• Sum the beauties and return the total.
Goal: The array length can range from 3 to 100,000 elements, and each element in the array is between 1 and 100,000.
Steps:
• The length of nums is at least 3.
• Each element of nums is between 1 and 100,000.
Assumptions:
• You are assuming the array has at least 3 elements.
• There will be no invalid indices; the index range for beauty calculation is between 1 and nums.length - 2.
• Input: Example 1: Input: nums = [1, 5, 3, 6, 2]
• Explanation: For each index i in the range 1 <= i <= 3: The beauty of nums[1] is 2 (because nums[0] < nums[1] < nums[2], nums[3], nums[4]). The beauty of nums[2] is 1 (because nums[1] < nums[2] < nums[3] but doesn't meet the first condition). The beauty of nums[3] is 0 (it doesn't satisfy any condition). Sum = 2 + 1 + 0 = 3.
• Input: Example 2: Input: nums = [4, 2, 7]
• Explanation: For each index i in the range 1 <= i <= 1: The beauty of nums[1] is 1 (because nums[0] < nums[1] < nums[2] but doesn't meet the first condition). Sum = 1.
• Input: Example 3: Input: nums = [10, 5, 2]
• Explanation: For each index i in the range 1 <= i <= 1: The beauty of nums[1] is 0 (it doesn't satisfy any condition). Sum = 0.
Approach: To solve this problem, we need to identify the beauty conditions for each index i and efficiently compute the beauty values using a sliding window approach.
Observations:
• The conditions involve comparing nums[i] with both its neighbors and all previous and future elements.
• The sliding window approach can help precompute left and right bounds efficiently.
• We can optimize the calculation by precomputing two arrays, 'left' and 'right', to store the necessary values for each index, thus avoiding nested loops.
Steps:
• Step 1: Create two arrays 'left' and 'right' that store the smallest element seen up to each index and the largest element seen from each index.
• Step 2: Traverse the array and for each index, check the conditions for beauty based on the precomputed left and right arrays.
• Step 3: Sum the beauties and return the result.
Empty Inputs:
• The input array will never be empty due to the constraint of nums.length being at least 3.
Large Inputs:
• For large arrays with up to 100,000 elements, we ensure the algorithm runs efficiently in O(n) time.
Special Values:
• When all elements are the same, the beauty of all indices will be 0.
Constraints:
• Ensure that the input array follows the constraint of having at least 3 elements.
int sumOfBeauties(vector<int>& nums) {
int n = nums.size();
vector<pair<int,int>> left(n), right(n);
left[0] = make_pair(nums[0], 0);
for(int i = 1; i < n; i++)
if(nums[i] >= left[i - 1].first) {
left[i] = make_pair(nums[i], i);
} else left[i] = left[i - 1];
right[n-1] = make_pair(nums[n - 1], n - 1);
for(int i = n - 2; i >= 0; i--)
if(nums[i] <= right[i + 1].first) {
right[i] = make_pair(nums[i], i);
} else right[i] = right[i + 1];
int sum = 0;
for(int i = 1; i < n - 1; i++) {
if(left[i - 1].first < nums[i] && right[i + 1].first > nums[i])
sum += 2;
else if(nums[i-1] < nums[i] && nums[i + 1] > nums[i])
sum += 1;
else sum += 0;
}
return sum;
}
1 : Function Definition
int sumOfBeauties(vector<int>& nums) {
Defines the function `sumOfBeauties`, which takes a vector of integers `nums` and calculates the sum of beauties for each element based on specific rules.
2 : Variable Initialization
int n = nums.size();
Initializes the variable `n` to store the size of the `nums` vector, which is used in subsequent iterations.
3 : Variable Initialization
vector<pair<int,int>> left(n), right(n);
Creates two vectors of pairs `left` and `right` to store the largest element and its index for each element, from left and right directions respectively.
4 : Left Array Initialization
left[0] = make_pair(nums[0], 0);
Initializes the first element of the `left` array with the first element of `nums` and its index.
5 : Loop Initialization
for(int i = 1; i < n; i++)
Begins a for loop to iterate through the `nums` vector, starting from the second element.
6 : Conditional Check
if(nums[i] >= left[i - 1].first) {
Checks if the current element `nums[i]` is greater than or equal to the largest element seen so far from the left (i.e., `left[i - 1]`), which would update the `left` array.
7 : Update Left Array
left[i] = make_pair(nums[i], i);
Updates the `left` array with the current element `nums[i]` and its index.
8 : Left Array Continuation
} else left[i] = left[i - 1];
If the current element `nums[i]` is smaller than the previous largest element from the left, the current `left[i]` is set to the previous value.
9 : Right Array Initialization
right[n-1] = make_pair(nums[n - 1], n - 1);
Initializes the last element of the `right` array with the last element of `nums` and its index.
10 : Loop Initialization
for(int i = n - 2; i >= 0; i--)
Begins a reverse loop from the second-to-last element of `nums` to the first element.
11 : Conditional Check
if(nums[i] <= right[i + 1].first) {
Checks if the current element `nums[i]` is less than or equal to the smallest element seen so far from the right (i.e., `right[i + 1]`).
12 : Update Right Array
right[i] = make_pair(nums[i], i);
Updates the `right` array with the current element `nums[i]` and its index.
13 : Right Array Continuation
} else right[i] = right[i + 1];
If the current element `nums[i]` is greater than the smallest element from the right, the current `right[i]` is set to the previous value.
14 : Sum Initialization
int sum = 0;
Initializes the variable `sum` to 0, which will hold the final beauty sum.
15 : Loop Initialization
for(int i = 1; i < n - 1; i++) {
Begins a loop to iterate over the middle elements of the `nums` array, excluding the first and last elements.
16 : Conditional Check
if(left[i - 1].first < nums[i] && right[i + 1].first > nums[i])
Checks if the current element `nums[i]` is greater than the previous element in the `left` array and smaller than the next element in the `right` array.
17 : Update Sum
sum += 2;
If the condition is true, adds 2 to the `sum`, indicating a higher beauty for `nums[i]`.
18 : Conditional Check
else if(nums[i-1] < nums[i] && nums[i + 1] > nums[i])
Checks if `nums[i]` is greater than the previous element and smaller than the next element, indicating a lower beauty.
19 : Update Sum
sum += 1;
If the condition is true, adds 1 to the `sum`, indicating a lower beauty for `nums[i]`.
20 : Sum Continuation
else sum += 0;
If neither condition is true, adds 0 to the `sum`.
21 : Return Statement
return sum;
Returns the final value of `sum`, which is the sum of beauties of the elements.
Best Case: O(n), where n is the length of the input array.
Average Case: O(n), where n is the length of the input array.
Worst Case: O(n), where n is the length of the input array.
Description: The time complexity is linear since we only traverse the array a constant number of times.
Best Case: O(n), as the space complexity remains the same even in the best case.
Worst Case: O(n), where n is the length of the input array, due to the space used by the left and right arrays.
Description: The space complexity is linear due to the extra space used for the left and right arrays.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus