Introduction

For a permutation of 1..n, a contiguous block is "valid" when the values inside it are consecutive numbers, even if they are not arranged in increasing order. The useful trick is that in a permutation with distinct values, you can test this property by comparing the block's minimum and maximum values to its length.

The Core Property of a Valid Block

Suppose A[left:right+1] is a contiguous block of a permutation. Because all values are distinct, the block contains consecutive numbers exactly when:

max(block) - min(block) == len(block) - 1

Why does that work?

• if the values are consecutive, their range must cover exactly the block length minus one
• if the values are distinct and the range has exactly that size, there is no room for gaps

For example, in:

[7, 3, 4, 1, 2, 6, 5, 8]

the block [3, 4, 1, 2] is valid because the minimum is 1, the maximum is 4, and 4 - 1 == 3, which equals len(block) - 1.

A Simple O(n^2) Counting Algorithm

You can count all valid blocks by fixing a left boundary, extending the right boundary one step at a time, and maintaining the running minimum and maximum.

1def count_valid_blocks(perm):
2    n = len(perm)
3    count = 0
4
5    for left in range(n):
6        current_min = perm[left]
7        current_max = perm[left]
8
9        for right in range(left, n):
10            current_min = min(current_min, perm[right])
11            current_max = max(current_max, perm[right])
12
13            if current_max - current_min == right - left:
14                count += 1
15
16    return count
17
18
19data = [7, 3, 4, 1, 2, 6, 5, 8]
20print(count_valid_blocks(data))

This runs in O(n^2) time and O(1) extra space. It is easy to implement and often good enough for moderate input sizes.

You can also list the blocks instead of only counting them:

1def list_valid_blocks(perm):
2    result = []
3    n = len(perm)
4
5    for left in range(n):
6        current_min = perm[left]
7        current_max = perm[left]
8
9        for right in range(left, n):
10            current_min = min(current_min, perm[right])
11            current_max = max(current_max, perm[right])
12
13            if current_max - current_min == right - left:
14                result.append(perm[left:right + 1])
15
16    return result
17
18
19print(list_valid_blocks([3, 4, 1, 2]))

Why the Permutation Assumption Matters

The formula relies on distinctness. In an arbitrary array with duplicates, max - min == length - 1 is not enough by itself.

For example, [1, 1, 3] has minimum 1, maximum 3, and length 3, but the values are not consecutive because 2 is missing and 1 is repeated. In a permutation, duplicates cannot occur, which is what makes the min-max test correct.

That is why the problem becomes much cleaner when the array is guaranteed to be a permutation of 1..n.

Faster Approaches Exist, but They Are More Complex

If you need to count valid blocks in O(n log n), there are divide-and-conquer approaches that count blocks crossing a midpoint while recursively solving left and right halves. Those methods are much harder to implement correctly than the quadratic scan.

For interview work, coursework, or medium-sized inputs, the O(n^2) solution is often the best tradeoff between correctness and code clarity. The divide-and-conquer version is mainly worth the extra complexity when n is large enough for quadratic time to become a problem.

Common Pitfalls

• Confusing arbitrary subsequences with contiguous blocks. This problem is about subarrays, not about skipping elements freely.
• Forgetting that the min-max test depends on all values being distinct.
• Recomputing the minimum and maximum from scratch for every block instead of updating them incrementally.
• Describing the problem as longest increasing subsequence or longest sorted subsequence, which is a different task.

Summary

• A contiguous block in a permutation is valid when its values form a consecutive range.
• In a permutation, that is equivalent to max(block) - min(block) == len(block) - 1.
• You can count all valid blocks in O(n^2) time by expanding each left boundary and tracking min and max.
• The permutation assumption is what makes the simple test correct.
• Faster O(n log n) methods exist, but they are significantly more complex.