Continuous Subarrays

Difficulty: Medium

Topics: Arrays, Sliding Window

---

Problem Description:

You are given a 0-indexed integer array nums. A subarray of nums is called continuous if it satisfies the following condition:

• Let i, i + 1, ..., j be the indices of the subarray. Then, for each pair of indices i1 and i2 such that i <= i1, i2 <= j, the absolute difference between the elements at those indices is at most 2:
  0 <= |nums[i1] - nums[i2]| <= 2.

Your task is to return the total number of continuous subarrays present in nums.

Key Notes:

• A subarray is a contiguous, non-empty sequence of elements within the array.
• Continuous subarrays can have varying sizes ranging from 1 to the length of the array.
• The result is the sum of all valid continuous subarrays for all possible subarray sizes.

---

Examples

Example 1:

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

Explanation:
Continuous subarrays are:

1. Subarrays of size 1:
   • [5], [4], [2], [4] (4 subarrays).
2. Subarrays of size 2:
   • [5, 4], [4, 2], [2, 4] (3 subarrays).
   • These satisfy the condition since the absolute difference between any two elements in the subarray is at most 2.
3. Subarray of size 3:
   • [4, 2, 4] (1 subarray).

There are no valid subarrays of size 4.

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

---

Example 2:

Input:
nums = [1, 2, 3]

Output:
6

Explanation:
Continuous subarrays are:

1. Subarrays of size 1:
   • [1], [2], [3] (3 subarrays).
2. Subarrays of size 2:
   • [1, 2], [2, 3] (2 subarrays).
3. Subarray of size 3:
   • [1, 2, 3] (1 subarray).

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

---

Constraints:

• 1 <= nums.length <= 10^5
  • The array can be very large, so an efficient solution is necessary.
• 1 <= nums[i] <= 10^9
  • The values in the array can be extremely large, so the algorithm must account for this.

---

Approach to Solve:

1. Brute Force:

• Iterate over all possible subarrays of nums.
• For each subarray, check if the condition 0 <= |nums[i1] - nums[i2]| <= 2 is satisfied for all pairs within the subarray.
• This approach is computationally expensive with time complexity O(n^3) or O(n^2) (with optimizations).
• Not feasible for large arrays.

2. Sliding Window or Two Pointers Technique:

1. Sliding Window Approach:
   The code uses a sliding window technique to efficiently scan through the array and identify valid continuous subarrays. The window expands as long as the subarray remains "continuous" and shrinks when it becomes invalid.

2. Tracking Frequency of Elements:

A HashMap is used to track the frequency of elements in the current window. This helps verify whether the window is valid (i.e., the difference condition is satisfied).

3. Validation of Subarrays:

For each new element added to the window:

• The code checks if the current subarray (from p1 to i) is valid.
• Validity is determined by ensuring that all numbers within the window differ by at most 2.

4. Counting Valid Subarrays:

For each valid subarray ending at index i, the code calculates the total number of subarrays that can be formed starting between p1 (start of the window) and i:

• The number of such subarrays is (i - p1 + 1).

5. Shrinking the Window:

If the subarray becomes invalid, the start of the window (p1) is moved forward until the subarray becomes valid again.

6. Summing Up:

The total count of valid subarrays is accumulated as the window slides through the entire array.

---

This problem requires careful handling of large inputs while ensuring efficiency. An efficient implementation with the sliding window approach is most suitable.

— Written by Saurabh Patil • B.Tech CSE • Software Developer