Continuous Subarrays
Continuous Subarrays is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.
Problem statement
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
Topics and companies
Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue.
How to practise Continuous Subarrays on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the length of nums. Each element is pushed and popped at most once from each deque. time and O(n), for the deques used to maintain the min and max values in the current window. space.
Open Continuous Subarrays in the code editor, or read the Continuous Subarrays editorial for a worked solution with its approach and complexity analysis.
Where Continuous Subarrays sits in the DSA pattern sheet
- Sliding Window pattern guide
- Variable Size (Condition-Based) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Continuous Subarrays
Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:
- Contains Duplicate II — Easy, same subpattern
- Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
- Frequency of the Most Frequent Element — Medium, same subpattern
- Fruit Into Baskets — Medium, same subpattern
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — Medium, same subpattern
- Longest Repeating Character Replacement — Medium, same subpattern