Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2145.html

2145. Count the Hidden Sequences (Medium)

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i].

You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

  • For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).
    • [3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.
    • [5, 6, 3, 7] is not possible since it contains an element greater than 6.
    • [1, 2, 3, 4] is not possible since the differences are not correct.

Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

 

Example 1:

Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: The possible hidden sequences are:
- [3, 4, 1, 5]
- [4, 5, 2, 6]
Thus, we return 2.

Example 2:

Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4
Explanation: The possible hidden sequences are:
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
Thus, we return 4.

Example 3:

Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0
Explanation: There are no possible hidden sequences. Thus, we return 0.

 

Constraints:

  • n == differences.length
  • 1 <= n <= 105
  • -105 <= differences[i] <= 105
  • -105 <= lower <= upper <= 105

Solution 1.

Assume hidden[0] = 0.

We can get all hidden[i+1] = hidden[i] + diff[i].

The hidden array forms a polyline. Assume the max/min values are max/min.

By changing hidden[0], we can shift this range up or down.

If we snap max to upper, we move up by upper - max steps. Then the number of possible of hidden sequences is min + (upper - max) - lower + 1.

Another way to think about it:

  • // OJ: https://leetcode.com/problems/count-the-hidden-sequences/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int numberOfArrays(vector<int>& A, int lower, int upper) {
            long sum = 0, mn = 0, mx = 0;
            for (int n : A) {
                sum += n;
                mn = min(mn, sum);
                mx = max(mx, sum);
            }
            return max(0L, mn - mx + upper - lower + 1);
        }
    };
    
  • class Solution:
        def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
            num = mi = mx = 0
            for d in differences:
                num += d
                mi = min(mi, num)
                mx = max(mx, num)
            return max(0, upper - lower - (mx - mi) + 1)
    
    ############
    
    # 2145. Count the Hidden Sequences
    # https://leetcode.com/problems/count-the-hidden-sequences/
    
    class Solution:
        def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
            mmax = mmin = s = 0
            
            for x in differences:
                s += x
                
                mmax = max(mmax, s)
                mmin = min(mmin, s)
            
            return max(0, (upper - lower) - (mmax - mmin) + 1)
    
    
  • class Solution {
        public int numberOfArrays(int[] differences, int lower, int upper) {
            long num = 0, mi = 0, mx = 0;
            for (int d : differences) {
                num += d;
                mi = Math.min(mi, num);
                mx = Math.max(mx, num);
            }
            return Math.max(0, (int) (upper - lower - (mx - mi) + 1));
        }
    }
    
  • func numberOfArrays(differences []int, lower int, upper int) int {
    	num, mi, mx := 0, 0, 0
    	for _, d := range differences {
    		num += d
    		mi = min(mi, num)
    		mx = max(mx, num)
    	}
    	return max(0, upper-lower-(mx-mi)+1)
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

Discuss

https://leetcode.com/problems/count-the-hidden-sequences/discuss/1709710/C%2B%2B-One-pass-O(N)-time

All Problems

All Solutions