Teaching Kids Programming – Number of Sublists with Max in Interval

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers nums and integers lo and hi. Return the number of sublists A such that lo ≤ max(A) ≤ hi.

Constraints
0 ≤ n ≤ 100,000 where n is the length of nums

Example 1
Input
nums = [1, 5, 3, 2]
lo = 1
hi = 4
Output
4

Explanation
We have the following sublists where 1 ≤ max(A) ≤ 4
[1]
[3]
[3, 2]
[2]

Bruteforce Each SubList – Number of Sublists with Max in Interval

There are sublists i.e. if there are N elements in the list: Teaching Kids Programming – Compute the Number of Sublists by Combination in Math. Therefore we can easily bruteforce them. And for each sublist, it takes O(N) time to check if the maximum is in the interval, and thus overall the time complexity is .

We are using constant number of space and hence space complexity is O(1).

1
2
3
4
5
6
7
8
9

class Solution:
    def numberOfSubListsWithMaxInInterval(self, A, L, R):
        n = len(A)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                if L <= max(A[i:j+1]) <= R:
                    ans += 1
        return ans

class Solution:
    def numberOfSubListsWithMaxInInterval(self, A, L, R):
        n = len(A)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                if L <= max(A[i:j+1]) <= R:
                    ans += 1
        return ans

Count SubLists with Math

We can count the number of sublists that has maximum less than a upperbound R, e.g. f(R), and we also count the number of sublists with max less or equal than L-1 i.e. f(L-1) and the answer would be aka the number of sublists with maximum i.e. max(A) between intervals [L, R] inclusive.

To implement the count function, we can accumulate the list of sublists so far as long as it is valid, or otherwise reset the length of the current longest sublist.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def numberOfSubListsWithMaxInInterval(self, A, L, R):
        def count(upperBound):
            ans = cur = 0
            for x in A :
                if x <= upperBound:
                    cur += 1
                else:
                    cur = 0
                ans += cur
            return ans
        return count(R) - count(L - 1) 

class Solution:
    def numberOfSubListsWithMaxInInterval(self, A, L, R):
        def count(upperBound):
            ans = cur = 0
            for x in A :
                if x <= upperBound:
                    cur += 1
                else:
                    cur = 0
                ans += cur
            return ans
        return count(R) - count(L - 1) 

Time complexity is O(N) as we need to call the function twice. The space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —