Continuous Subarrays - Practice Coding Problems

Continuous Subarrays - Problem

Array Queue Sliding Window Heap (Priority Queue) Ordered Set Monotonic Queue Medium

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

Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, we have 0 <= |nums[i1] - nums[i2]| <= 2.

Return the total number of continuous subarrays.

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

Input & Output

Example 1 — Basic Case

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

› Output: 10

💡 Note: All valid subarrays: [5], [4], [2], [4], [5,4], [4,2], [2,4], [4,2,4], [5,4,2] (invalid: |5-2|=3>2), so 10 total

Example 2 — Small Array

$ Input: nums = [1,2,3]

› Output: 6

💡 Note: All subarrays are continuous: [1], [2], [3], [1,2], [2,3], [1,2,3] → 6 total

Example 3 — Large Differences

$ Input: nums = [1,10,2]

› Output: 4

💡 Note: Valid subarrays: [1], [10], [2], [2,10] (invalid: [1,10] since |1-10|=9>2) → 4 total

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [5,4,2,4] - find continuous subarrays

Process

Check each subarray: max - min ≤ 2

Output

Count: 10 valid continuous subarrays

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently maintain subarrays where max-min ≤ 2

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is using sliding window technique with deque data structures to efficiently track minimum and maximum values in the current window. Best approach is sliding window with monotonic deques. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible subarrays and validate each one
Sliding Window with Min/Max Tracking	O(n)	O(n)	Use sliding window technique with deque to track min/max efficiently

Brute Force — Algorithm Steps

Step 1: For each starting index i
Step 2: For each ending index j >= i
Step 3: Check all pairs in subarray[i:j+1]
Step 4: Count valid subarrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Try all possible start-end pairs

Validate

Check all element pairs in subarray

Count

Count valid continuous subarrays

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int n) {
    long long count = 0;
    
    // Try all possible subarrays
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Check if subarray[i:j+1] is continuous
            int isContinuous = 1;
            for (int k1 = i; k1 <= j && isContinuous; k1++) {
                for (int k2 = k1; k2 <= j; k2++) {
                    int diff = nums[k1] - nums[k2];
                    if (diff < 0) diff = -diff;
                    if (diff > 2) {
                        isContinuous = 0;
                        break;
                    }
                }
            }
            
            if (isContinuous) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: n choices for start, n for end, n² to check all pairs

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler