2762. Continuous Subarrays.md

Difficulty	Source	Tags
Medium	Daily-Question (POTD 14-Dec)	Sliding Window Array Ordered Set Queue Heap (Priority Queue) Monotonic Queue Two Pointers Ordered Map Hash Table Dynamic Programming Counting Math Binary Search Tree Segment Tree Tree Stack Binary Search Monotonic Stack Memoization Iterator Greedy Depth-First Search Recursion

🚀 2762 - Continuous Subarrays 🧠

Problem Link:

LeetCode - Continuous Subarrays

💡 Problem Breakdown:

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:

• For any pair of indices $i \leq i_1, i_2 \leq j$, the condition $0 \leq |nums[i_1] - nums[i_2]| \leq 2$ is satisfied.

Return the total number of continuous subarrays in the given array.

Definitions:

• A subarray is a contiguous, non-empty sequence of elements within an array.

🔍 Example Walkthrough:

Example 1:

Input:
nums = [5, 4, 2, 4]

Output:
8

Explanation:

• Continuous subarrays of size 1: [5], [4], [2], [4]
• Continuous subarrays of size 2: [5, 4], [4, 2], [2, 4]
• Continuous subarrays of size 3: [4, 2, 4]
• No subarrays of size 4 satisfy the condition.

Total continuous subarrays = $4 + 3 + 1 = 8$.

Example 2:

Input:
nums = [1, 2, 3]

Output:
6

Explanation:

• Continuous subarrays of size 1: [1], [2], [3]
• Continuous subarrays of size 2: [1, 2], [2, 3]
• Continuous subarrays of size 3: [1, 2, 3]

Total continuous subarrays = $3 + 2 + 1 = 6$.

⚙️ Constraints:

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$

🎯 My Approach:

Sliding Window with Two Pointers

The problem can be solved efficiently using the Sliding Window technique:

1. Definition of Validity: A subarray is valid if for all elements within the window, the difference between the smallest and largest element is at most 2. This translates to: $$ \text{max(nums[left:right]) - min(nums[left:right]) \leq 2} $$

2. Two-Pointer Technique:

   • Maintain a sliding window using two pointers, left and right, and expand the window by incrementing right.
   • Use a data structure to efficiently maintain the minimum and maximum of the current window (e.g., a balanced deque).

3. Count Valid Subarrays:

   • For each valid right, the number of subarrays ending at right is (right - left + 1).
   • Adjust left if the window becomes invalid (i.e., the difference between the max and min exceeds 2).

4. Efficient Updates:

   • Use a deque to store indices of elements in the window, ensuring efficient updates to the max and min when the window changes.

🕒 Time Complexity:

• O(n): Each element is added to and removed from the deque at most once.
• Space Complexity: O(n): The deque can store up to n elements in the worst case.

📝 Solution Code

📝 Solution Code

Code (C):

long long continuousSubarrays(int* nums, int numsSize) {
    int start = 0;
    long long totalSubarrays = 0;
    int* maxDeque = (int*)malloc(numsSize * sizeof(int));
    int* minDeque = (int*)malloc(numsSize * sizeof(int));
    int maxFront = 0, maxBack = 0;
    int minFront = 0, minBack = 0;

    for (int end = 0; end < numsSize; end++) {
        while (maxBack > maxFront && nums[maxDeque[maxBack - 1]] <= nums[end]) {
            maxBack--;
        }
        maxDeque[maxBack++] = end;
        while (minBack > minFront && nums[minDeque[minBack - 1]] >= nums[end]) {
            minBack--;
        }
        minDeque[minBack++] = end;
        while (nums[maxDeque[maxFront]] - nums[minDeque[minFront]] > 2) {
            if (maxDeque[maxFront] == start) {
                maxFront++;
            }
            if (minDeque[minFront] == start) {
                minFront++;
            }
            start++;
        }
        totalSubarrays += (end - start + 1);
    }

    free(maxDeque);
    free(minDeque);
    return totalSubarrays;
}

Code (C++)

class Solution {
public:
    long long continuousSubarrays(vector<int>& nums) {
        int start = 0;
        long long totalSubarrays = 0;
        deque<int> maxDeque, minDeque;

        for (int end = 0; end < nums.size(); ++end) {
            while (!maxDeque.empty() && nums[maxDeque.back()] <= nums[end]) {
                maxDeque.pop_back();
            }
            maxDeque.push_back(end);
            while (!minDeque.empty() && nums[minDeque.back()] >= nums[end]) {
                minDeque.pop_back();
            }
            minDeque.push_back(end);
            while (nums[maxDeque.front()] - nums[minDeque.front()] > 2) {
                if (maxDeque.front() == start) {
                    maxDeque.pop_front();
                }
                if (minDeque.front() == start) {
                    minDeque.pop_front();
                }
                ++start;
            }
            totalSubarrays += (end - start + 1);
        }

        return totalSubarrays;
    }
};

Code (Java)

class Solution {
    public long continuousSubarrays(int[] nums) {
        int start = 0;
        long totalSubarrays = 0;
        Deque<Integer> maxDeque = new LinkedList<>();
        Deque<Integer> minDeque = new LinkedList<>();

        for (int end = 0; end < nums.length; end++) {
            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[end]) {
                maxDeque.pollLast();
            }
            maxDeque.offerLast(end);
            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[end]) {
                minDeque.pollLast();
            }
            minDeque.offerLast(end);
            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > 2) {
                if (maxDeque.peekFirst() == start) {
                    maxDeque.pollFirst();
                }
                if (minDeque.peekFirst() == start) {
                    minDeque.pollFirst();
                }
                start++;
            }
            totalSubarrays += (end - start + 1);
        }

        return totalSubarrays;
    }
}

Code (Python)

from collections import deque
from typing import List

class Solution:
    def continuousSubarrays(self, nums: List[int]) -> int:
        start = 0
        total_subarrays = 0
        max_deque, min_deque = deque(), deque()
        for end, num in enumerate(nums):
            while max_deque and nums[max_deque[-1]] <= num:
                max_deque.pop()
            max_deque.append(end)
            while min_deque and nums[min_deque[-1]] >= num:
                min_deque.pop()
            min_deque.append(end)
            while nums[max_deque[0]] - nums[min_deque[0]] > 2:
                if max_deque[0] == start:
                    max_deque.popleft()
                if min_deque[0] == start:
                    min_deque.popleft()
                start += 1
            total_subarrays += end - start + 1

        return total_subarrays

Code (Rust)

impl Solution {
    pub fn continuous_subarrays(nums: Vec<i32>) -> i64 {
        let mut start = 0;
        let mut total_subarrays = 0i64;
        let mut max_deque: std::collections::VecDeque<usize> = std::collections::VecDeque::new();
        let mut min_deque: std::collections::VecDeque<usize> = std::collections::VecDeque::new();
        for (end, &num) in nums.iter().enumerate() {
            while let Some(&last) = max_deque.back() {
                if nums[last] <= num {
                    max_deque.pop_back();
                } else {
                    break;
                }
            }
            max_deque.push_back(end);
            while let Some(&last) = min_deque.back() {
                if nums[last] >= num {
                    min_deque.pop_back();
                } else {
                    break;
                }
            }
            min_deque.push_back(end);
            while nums[*max_deque.front().unwrap()] - nums[*min_deque.front().unwrap()] > 2 {
                if *max_deque.front().unwrap() == start {
                    max_deque.pop_front();
                }
                if *min_deque.front().unwrap() == start {
                    min_deque.pop_front();
                }
                start += 1;
            }
            total_subarrays += (end - start + 1) as i64;
        }

        total_subarrays
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!