Jobs

Interviews

Discussions

Continuous Subarrays

Medium

Asked by:

More companies

21 views

Topics:

ArraysSliding Windows

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

Let i, i + 1, ..., jbe the indices in the subarray. Then, for each pair of indices i <= i₁, i₂ <= j, 0 <= |nums[i₁] - nums[i₂]| <= 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 <= 10⁵
1 <= nums[i] <= 10⁹

Try coding it in LeetCode

Continuous Subarrays

Medium

Asked by:

21 views

Topics:

ArraysSliding Windows

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

Let i, i + 1, ..., jbe the indices in the subarray. Then, for each pair of indices i <= i₁, i₂ <= j, 0 <= |nums[i₁] - nums[i₂]| <= 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 <= 10⁵
1 <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain negative numbers, zero, or only positive integers?
What defines 'continuous'? Does it mean the absolute difference between any two adjacent numbers in the subarray must be less than or equal to 2?
What should I return if there are no continuous subarrays that meet the criteria?
If multiple continuous subarrays satisfy the conditions, should I return any one, the shortest, the longest, or all of them?
What are the upper and lower bounds on the size of the input array?

Brute Force Solution

Approach

The brute force approach to finding continuous subarrays considers every possible subarray within the given data. We systematically look at each possible starting point and then extend it to every possible ending point to form different subarrays. We then evaluate each of these subarrays.

Here's how the algorithm would work step-by-step:

Start at the very beginning of the list of numbers.
Consider the first number by itself as a possible subarray.
Then, add the next number to it, creating a subarray of two numbers.
Continue adding numbers one by one to the subarray, each time making a larger subarray that starts at the beginning.
After you've made the subarray that includes all numbers starting from the beginning, shift your focus.
Now, start at the second number in the list.
Repeat the same process: consider the second number alone, then the second and third, then the second, third, and fourth, and so on, until you've made all possible subarrays that start with the second number.
Keep doing this, each time shifting the starting point one number further down the list, and creating all possible subarrays that begin at that point.
For each subarray you create, check if it meets the specified condition (e.g., whether its range is within a limit).
Keep track of all the subarrays that meet the condition, and ultimately choose the best one according to the problem's requirements.

Code Implementation

def find_continuous_subarrays_brute_force(data):
    number_of_continuous_subarrays = 0

    for starting_index in range(len(data)): 
        # Iterate through each possible start index

        for ending_index in range(starting_index, len(data)): 
            # For each start, iterate through each possible end

            sub_array = data[starting_index:ending_index + 1]
            
            if len(sub_array) > 0:
                maximum_value = max(sub_array)
                minimum_value = min(sub_array)

                # Only count if range condition is met
                if (maximum_value - minimum_value) <= 2:
                    number_of_continuous_subarrays += 1

    return number_of_continuous_subarrays

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible starting positions of subarrays. For each starting position, it iterates through all possible ending positions, creating and evaluating each subarray. With 'n' being the size of the input array, the outer loop runs 'n' times, and the inner loop, on average, runs 'n/2' times. Therefore, the total number of operations is proportional to n * n/2, which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach, as described, iterates through all possible subarrays using nested loops. It doesn't explicitly use any auxiliary data structures like lists, hash maps, or sets to store intermediate results or subarray elements. It only uses a constant number of variables to keep track of the starting and ending indices of the subarrays being considered and potentially a variable to store the result if there is an aggregate that must be stored and returned. Therefore, the auxiliary space complexity is O(1), indicating constant space usage regardless of the input size N.

Optimal Solution

Approach

The goal is to efficiently count special groups of numbers within a larger list. Instead of checking every possible group, we'll focus on expanding groups that meet our condition by sliding along the list, keeping track of the largest and smallest number in the group.

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
Consider the first number as the start of a potential group.
Extend the group by adding the next number in the list.
Check if the difference between the largest and smallest number in the current group is no more than 2.
If it is, the group is 'special', so count it and keep extending the group by one more number.
If the difference is more than 2, the group is no longer 'special'. Stop extending the group.
Move to the next number in the list and consider it as the start of a new potential group and repeat the process from step 3.
Keep doing this until you've checked every number as a potential start for a group.
The total number of 'special' groups found is the answer.

Code Implementation

def count_continuous_subarrays(numbers):
    subarray_count = 0
    list_length = len(numbers)

    for start_index in range(list_length):
        current_subarray = []

        for end_index in range(start_index, list_length):
            current_subarray.append(numbers[end_index])

            # Find the min and max values of current subarray.
            minimum_value = min(current_subarray)
            maximum_value = max(current_subarray)

            # Check if the range is within the limit.
            if (maximum_value - minimum_value) <= 2:
                subarray_count += 1
            else:
                # Stop extending subarray if it's invalid.
                break

    return subarray_count

Big(O) Analysis

Time Complexity

O(n²) – The outer loop iterates through each of the n elements of the input array, considering each element as a potential starting point for a continuous subarray. The inner loop extends the subarray from each starting point, checking elements until the condition (max - min <= 2) is violated. In the worst case, for each starting element, the inner loop might iterate through a significant portion of the remaining elements. This nested structure results in a quadratic time complexity, approximately proportional to n * (n/2) operations, which simplifies to O(n²).

Space Complexity

O(1) – The algorithm uses a sliding window approach, where it maintains the start and end indices of the current subarray. The key operation is to track the maximum and minimum values within the window to check if their difference is within the limit (<=2). While computing the min/max value within a window requires auxiliary space to store the min/max variables, the number of such variables is constant and does not depend on the size of the input list. Therefore, the auxiliary space remains constant, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there are no subarrays.
Array with one element	Return 0 as a continuous subarray must have at least two elements.
Array with all elements identical	If the continuous subarray constraint is that elements are strictly increasing or strictly decreasing, the result will be 0; otherwise the total number of subarrays.
Array with consecutive duplicate values	Ensure the solution correctly identifies the boundaries of the valid subarrays when duplicates exist contiguously.
Array with integer overflow potential when calculating min/max	Use appropriate data types or modular arithmetic to prevent integer overflow during min/max calculations.
Array is sorted in ascending or descending order	A sorted array may have a high or low number of continuous subarrays depending on the precise continuous subarray definition, so ensure the algorithm handles these boundary sorted cases.
Large array size	Optimize for time complexity, potentially using sliding window or other efficient algorithms.
Input array contains negative numbers	The min/max calculation logic should correctly handle negative numbers in the array.

Empty input array

How to Handle:

Return 0 immediately as there are no subarrays.

Array with one element

How to Handle:

Return 0 as a continuous subarray must have at least two elements.

Array with all elements identical

How to Handle:

If the continuous subarray constraint is that elements are strictly increasing or strictly decreasing, the result will be 0; otherwise the total number of subarrays.

Array with consecutive duplicate values

How to Handle:

Ensure the solution correctly identifies the boundaries of the valid subarrays when duplicates exist contiguously.

Array with integer overflow potential when calculating min/max

How to Handle:

Use appropriate data types or modular arithmetic to prevent integer overflow during min/max calculations.

Array is sorted in ascending or descending order

How to Handle:

A sorted array may have a high or low number of continuous subarrays depending on the precise continuous subarray definition, so ensure the algorithm handles these boundary sorted cases.

Large array size

How to Handle:

Optimize for time complexity, potentially using sliding window or other efficient algorithms.

Input array contains negative numbers

How to Handle:

The min/max calculation logic should correctly handle negative numbers in the array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain negative numbers, zero, or only positive integers?
What defines 'continuous'? Does it mean the absolute difference between any two adjacent numbers in the subarray must be less than or equal to 2?
What should I return if there are no continuous subarrays that meet the criteria?
If multiple continuous subarrays satisfy the conditions, should I return any one, the shortest, the longest, or all of them?
What are the upper and lower bounds on the size of the input array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very beginning of the list of numbers.
Consider the first number by itself as a possible subarray.
Then, add the next number to it, creating a subarray of two numbers.
Continue adding numbers one by one to the subarray, each time making a larger subarray that starts at the beginning.
After you've made the subarray that includes all numbers starting from the beginning, shift your focus.
Now, start at the second number in the list.
Repeat the same process: consider the second number alone, then the second and third, then the second, third, and fourth, and so on, until you've made all possible subarrays that start with the second number.
Keep doing this, each time shifting the starting point one number further down the list, and creating all possible subarrays that begin at that point.
For each subarray you create, check if it meets the specified condition (e.g., whether its range is within a limit).
Keep track of all the subarrays that meet the condition, and ultimately choose the best one according to the problem's requirements.

Code Implementation

def find_continuous_subarrays_brute_force(data):
    number_of_continuous_subarrays = 0

    for starting_index in range(len(data)): 
        # Iterate through each possible start index

        for ending_index in range(starting_index, len(data)): 
            # For each start, iterate through each possible end

            sub_array = data[starting_index:ending_index + 1]
            
            if len(sub_array) > 0:
                maximum_value = max(sub_array)
                minimum_value = min(sub_array)

                # Only count if range condition is met
                if (maximum_value - minimum_value) <= 2:
                    number_of_continuous_subarrays += 1

    return number_of_continuous_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the list.
Consider the first number as the start of a potential group.
Extend the group by adding the next number in the list.
Check if the difference between the largest and smallest number in the current group is no more than 2.
If it is, the group is 'special', so count it and keep extending the group by one more number.
If the difference is more than 2, the group is no longer 'special'. Stop extending the group.
Move to the next number in the list and consider it as the start of a new potential group and repeat the process from step 3.
Keep doing this until you've checked every number as a potential start for a group.
The total number of 'special' groups found is the answer.

Code Implementation

def count_continuous_subarrays(numbers):
    subarray_count = 0
    list_length = len(numbers)

    for start_index in range(list_length):
        current_subarray = []

        for end_index in range(start_index, list_length):
            current_subarray.append(numbers[end_index])

            # Find the min and max values of current subarray.
            minimum_value = min(current_subarray)
            maximum_value = max(current_subarray)

            # Check if the range is within the limit.
            if (maximum_value - minimum_value) <= 2:
                subarray_count += 1
            else:
                # Stop extending subarray if it's invalid.
                break

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there are no subarrays.
Array with one element	Return 0 as a continuous subarray must have at least two elements.
Array with all elements identical	If the continuous subarray constraint is that elements are strictly increasing or strictly decreasing, the result will be 0; otherwise the total number of subarrays.
Array with consecutive duplicate values	Ensure the solution correctly identifies the boundaries of the valid subarrays when duplicates exist contiguously.
Array with integer overflow potential when calculating min/max	Use appropriate data types or modular arithmetic to prevent integer overflow during min/max calculations.
Array is sorted in ascending or descending order	A sorted array may have a high or low number of continuous subarrays depending on the precise continuous subarray definition, so ensure the algorithm handles these boundary sorted cases.
Large array size	Optimize for time complexity, potentially using sliding window or other efficient algorithms.
Input array contains negative numbers	The min/max calculation logic should correctly handle negative numbers in the array.

Empty input array

How to Handle:

Return 0 immediately as there are no subarrays.

Array with one element

How to Handle:

Return 0 as a continuous subarray must have at least two elements.

Array with all elements identical

How to Handle:

If the continuous subarray constraint is that elements are strictly increasing or strictly decreasing, the result will be 0; otherwise the total number of subarrays.

Array with consecutive duplicate values

How to Handle:

Ensure the solution correctly identifies the boundaries of the valid subarrays when duplicates exist contiguously.

Array with integer overflow potential when calculating min/max

How to Handle:

Use appropriate data types or modular arithmetic to prevent integer overflow during min/max calculations.

Array is sorted in ascending or descending order

How to Handle:

A sorted array may have a high or low number of continuous subarrays depending on the precise continuous subarray definition, so ensure the algorithm handles these boundary sorted cases.

Large array size

How to Handle:

Optimize for time complexity, potentially using sliding window or other efficient algorithms.

Input array contains negative numbers

How to Handle:

The min/max calculation logic should correctly handle negative numbers in the array.