Finding All Contiguous Subarrays: An Algorithmic Approach

Recently, while working on an algorithm assessment, I encountered an interesting problem: writing an algorithm to find all contiguous subarrays from a flat array like [1,2,3,4,5]. This challenge led me to discover a fascinating connection between contiguous subarrays and arithmetic sequences, which I'll explore in this article.

Understanding Contiguous Subarrays

A contiguous subarray is a sequence of elements that appear consecutively in the original array. For example, if we have an array [1,2,3], all possible contiguous subarrays would be:

[[1], [2], [3], [1,2], [2,3], [1,2,3]]

The key insight I discovered is that the count of contiguous subarrays follows an arithmetic sequence pattern.

The Arithmetic Sequence Connection

When I analyzed the pattern of contiguous subarray counts, I noticed something interesting. For an array of length n, the number of subarrays starting at each position follows this pattern:

• Position 1: n subarrays
• Position 2: n-1 subarrays
• Position 3: n-2 subarrays
• ...
• Position n: 1 subarray

This creates the arithmetic sequence: n + (n-1) + (n-2) + ... + 1

We can calculate this sum using the arithmetic sequence formula:

S = (n/2)(first_element + last_element)
S = (n/2)(n + 1)

Testing the Formula

Let's verify this with some examples:

Example 1: Array [1,2,3]

All contiguous subarrays: [[1],[2],[3],[1,2],[2,3],[1,2,3]]
Count: 6

Using the formula with n=3:

S = (3/2)(3 + 1) = (3/2)(4) = 6 ✓

Example 2: Array [1,2,3,4,5]

All contiguous subarrays: [[1],[1,2],[2],[1,2,3],[2,3],[3],[1,2,3,4],[2,3,4],[3,4],[4],[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5]]
Count: 15

Using the formula with n=5:

S = (5/2)(5 + 1) = (5/2)(6) = 15 ✓

The Algorithm Implementation

Here's my Ruby solution for generating all contiguous subarrays with O(n²) time and space complexity:

def all_contiguous_subarrays(nums)
  vault = []
  pointer = 0
  
  nums.each do |num|
    temp_vault = vault.clone
  
    while pointer < temp_vault.length
      arr = temp_vault[pointer]
      vault << arr + [num]
      pointer += 1
    end
  
    vault << [num]
  end

  vault
end

And the corresponding count validation function:

def sub_array_count(num)
  num * ((1 + num) / 2.0)
end

Usage Example

c1 = [1,2,3,4]
result = all_contiguous_subarrays(c1)

# Verify the count matches our formula
puts result.length == sub_array_count(c1.length) # true

Performance Considerations

The algorithm achieves O(n²) time complexity, which is optimal for this problem since we need to generate all possible contiguous subarrays. The space complexity is also O(n²) due to storing all subarrays.

For an array of length n, we generate exactly n(n+1)/2 subarrays, making this the most efficient approach possible for complete subarray generation.

Limitations and Testing Strategy

It's important to note that using the arithmetic sequence formula only validates the count of subarrays, not their actual content. This approach provides a quick sanity check but shouldn't be the sole testing method for correctness.

For comprehensive testing, you'd want to verify:

• The correct count (using our formula)
• Each subarray contains consecutive elements
• No duplicate subarrays exist
• All possible subarrays are included

Conclusion

The connection between contiguous subarrays and arithmetic sequences provides an elegant way to validate our algorithm's completeness. While this mathematical relationship doesn't replace thorough testing, it offers valuable insight into the problem's structure and gives us confidence in our solution's correctness.

This approach demonstrates how understanding mathematical patterns can enhance our algorithmic thinking and provide elegant validation methods for complex problems.