2145. Count the Hidden Sequences

Time: O(n)

Space: O(1)

Approach

Compute prefix sum of differences; answer = (upper - lower) - (max_prefix - min_prefix) + 1.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Prefix Sum

A prefix sum array pre-computes cumulative values so any range query is answered in O(1). The classic sum of range [l, r] = prefix[r+1] - prefix[l]. 2D prefix sums extend this to matrix sub-rectangle queries. Combine with a hash map for "subarray sum equals k" problems.

2145.cs

// Approach: Compute prefix sum of differences; answer = (upper - lower) - (max_prefix - min_prefix) + 1.
// Time: O(n) Space: O(1)

public class Solution
{
    public int NumberOfArrays(int[] differences, int lower, int upper)
    {
        long prefix = 0;
        long mn = 0; // Starts from 0.
        long mx = 0; // Starts from 0.

        foreach (var d in differences)
        {
            prefix += d;
            mn = Math.Min(mn, prefix);
            mx = Math.Max(mx, prefix);
        }

        return (int)Math.Max(0L, (upper - lower) - (mx - mn) + 1);
    }
}

Was this solution helpful?