Leetcode 2762: Continuous Subarrays
You are given a 0-indexed integer array ’nums’. A subarray of ’nums’ is called continuous if the absolute difference between any two elements in the subarray is less than or equal to 2. Return the total number of continuous subarrays.
Problem
Approach
Steps
Complexity
Input: The input consists of a single integer array 'nums'.
Example: nums = [3, 5, 4, 2]
Constraints:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
Output: Return the total number of continuous subarrays.
Example: For nums = [3, 5, 4, 2], the output is 10.
Constraints:
• The output should be a single integer representing the count of continuous subarrays.
Goal: Find the total number of continuous subarrays where the absolute difference between any two elements is less than or equal to 2.
Steps:
• Use a sliding window approach with two pointers, i and j.
• Track the frequency of elements within the window using a map.
• Adjust the window to ensure the condition |nums[i] - nums[j]| <= 2 is met.
Goal: The array size is between 1 and 10^5, and elements are between 1 and 10^9.
Steps:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
Assumptions:
• The input array will always have at least one element.
• Input: For nums = [3, 5, 4, 2]
• Explanation: The valid subarrays are of size 1, 2, and 3, totaling 10 continuous subarrays.
• Input: For nums = [7, 8, 9, 10]
• Explanation: The valid subarrays are of size 1, 2, 3, and 4, totaling 10 continuous subarrays.
Approach: The solution involves using a sliding window to count continuous subarrays that satisfy the condition.
Observations:
• We need to ensure that the absolute difference between any two elements in the subarray is less than or equal to 2.
• Using a sliding window approach will allow us to count valid subarrays efficiently by adjusting the window as we iterate through the array.
Steps:
• Initialize two pointers, i and j, and a map to store the frequencies of elements in the current window.
• Expand the window by moving the j pointer and update the frequencies.
• If the condition |nums[i] - nums[j]| > 2 is violated, move the i pointer to shrink the window.
• For each valid window, calculate the number of subarrays and accumulate the result.
Empty Inputs:
• The input array will always contain at least one element, so no need to handle empty arrays.
Large Inputs:
• For large arrays (up to 10^5 elements), ensure that the solution runs efficiently.
Special Values:
• When all elements are the same, the entire array is valid.
Constraints:
• Ensure that the solution handles arrays with large values (up to 10^9) efficiently.
long long continuousSubarrays(vector<int>& nums) {
long long res = 0;
int i = 0, j = 0,n=nums.size();
map<int,int> mp;
while(j<n) {
mp[nums[j]]++;
while(mp.size()>3 || abs(mp.begin()->first - mp.rbegin()->first) > 2) {
mp[nums[i]]--;
if(mp[nums[i]] == 0)
mp.erase(nums[i]);
i++;
}
long long temp = j-i+1;
res = res + temp;
j++;
}
return res;
}
1 : Function Definition
long long continuousSubarrays(vector<int>& nums) {
Defines the function `continuousSubarrays`, which takes a vector `nums` and returns the total count of valid continuous subarrays that satisfy the given conditions.
2 : Variable Initialization
long long res = 0;
Initializes a variable `res` to store the result, which will hold the total number of valid subarrays.
3 : Index Initialization
int i = 0, j = 0, n = nums.size();
Initializes the indices `i` and `j` to 0, and `n` to the size of the `nums` vector. These indices will define the current window of subarray being considered.
4 : Map Initialization
map<int, int> mp;
Initializes a map `mp` to track the frequency of elements in the current window. The key is the element, and the value is its count.
5 : Outer While Loop
while(j < n) {
Starts a while loop that iterates as long as `j` is within the bounds of the vector. This loop expands the window by incrementing `j`.
6 : Map Update
mp[nums[j]]++;
Increments the count of the current element `nums[j]` in the map `mp`.
7 : Inner While Loop (Check Validity)
while(mp.size() > 3 || abs(mp.begin()->first - mp.rbegin()->first) > 2) {
Checks if the current subarray has more than 3 distinct elements or if the difference between the max and min elements exceeds 2. If so, reduces the window size by moving `i` forward.
8 : Adjust Map (Remove Element)
mp[nums[i]]--;
Decrements the count of the element at index `i` in the map `mp`.
9 : Erase Element from Map
if(mp[nums[i]] == 0)
Checks if the count of the element `nums[i]` is 0, and if so, removes it from the map `mp`.
10 : Increment Index i
mp.erase(nums[i]);
Erases the element `nums[i]` from the map `mp`.
11 : Increment Index i
i++;
Increments the index `i` to shrink the window from the left side.
12 : Calculate Subarray Length
long long temp = j - i + 1;
Calculates the length of the current valid subarray, which is `j - i + 1`, and stores it in `temp`.
13 : Update Result
res = res + temp;
Adds the length of the current valid subarray (`temp`) to the total result `res`.
14 : Increment Index j
j++;
Increments the index `j` to expand the window to the next element.
15 : Return Result
return res;
Returns the total number of valid subarrays stored in `res`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the array. We iterate through the array with two pointers.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the map storing the frequencies of elements in the window.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus