Scale Engineer

Continuous Subarrays

Med
#2479Time: O(n^3). Three nested loops are used. The outer two loops select the subarray (`O(n^2)` pairs), and the inner loop finds the min/max in `O(n)` time.Space: O(1). We only use a few variables to store the count, indices, min, and max.
Patterns
Sliding Window
Data structures
ArrayHeap (Priority Queue)Ordered SetQueueMonotonic Queue

Prompt

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, 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.

 

Example 1:

Input: nums = [5,4,2,4]
Output: 8
Explanation: 
Continuous subarray of size 1: [5], [4], [2], [4].
Continuous subarray of size 2: [5,4], [4,2], [2,4].
Continuous subarray of size 3: [4,2,4].
There are no subarrys of size 4.
Total continuous subarrays = 4 + 3 + 1 = 8.
It can be shown that there are no more continuous subarrays.

 

Example 2:

Input: nums = [1,2,3]
Output: 6
Explanation: 
Continuous subarray of size 1: [1], [2], [3].
Continuous subarray of size 2: [1,2], [2,3].
Continuous subarray of size 3: [1,2,3].
Total continuous subarrays = 3 + 2 + 1 = 6.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Approaches

4 approaches with complexity analysis and trade-offs.

This approach involves generating every possible subarray, and for each one, checking if it meets the 'continuous' criteria. The criteria is that the difference between the maximum and minimum element in the subarray must be less than or equal to 2.

Algorithm

  • Initialize a counter count to 0.
  • Iterate through each possible start index i from 0 to n-1.
  • For each i, iterate through each possible end index j from i to n-1.
  • For the subarray nums[i...j], find the minimum (minVal) and maximum (maxVal) elements by iterating from i to j.
  • If maxVal - minVal <= 2, increment count.
  • After all subarrays are checked, return count.

Walkthrough

We use two nested loops to define the start (i) and end (j) indices of all possible subarrays. For each subarray nums[i...j], we iterate through it a third time to find its minimum and maximum values. If max - min <= 2, we increment a counter. This method is simple to understand but highly inefficient due to the triple nested loops.

public class Solution {    public long continuousSubarrays(int[] nums) {        long count = 0;        int n = nums.length;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                int minVal = Integer.MAX_VALUE;                int maxVal = Integer.MIN_VALUE;                // Find min and max in subarray nums[i..j]                for (int k = i; k <= j; k++) {                    minVal = Math.min(minVal, nums[k]);                    maxVal = Math.max(maxVal, nums[k]);                }                if (maxVal - minVal <= 2) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(n^3). Three nested loops are used. The outer two loops select the subarray (`O(n^2)` pairs), and the inner loop finds the min/max in `O(n)` time.

Space

O(1). We only use a few variables to store the count, indices, min, and max.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Requires no extra data structures.

Cons

  • Extremely inefficient, with a cubic time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.

Solutions

class Solution {public  long continuousSubarrays(int[] nums) {    long ans = 0;    int i = 0, n = nums.length;    TreeMap<Integer, Integer> tm = new TreeMap<>();    for (int j = 0; j < n; ++j) {      tm.merge(nums[j], 1, Integer : : sum);      while (tm.lastEntry().getKey() - tm.firstEntry().getKey() > 2) {        tm.merge(nums[i], -1, Integer : : sum);        if (tm.get(nums[i]) == 0) {          tm.remove(nums[i]);        }        ++i;      }      ans += j - i + 1;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem