Problem statement

https://binarysearch.com/problems/Sublists-Containing-Maximum-and-Minimum/

Solution

The idea is the following: we can either remove nothing or remove smallest or biggest numbers if they are unique. It can be proved that it will be the optimal. Now, if we have array, how to find number of sublists which contain maximum and minimum? We can use two pointers: one will point at last elements so far which is equal to minimum value and another to last element so far which point at maximum value. When we traverse array, we update these pointers. Also for given index i as right element of sublist, number of sublists which contain maximum and minimum will be min(minloc, maxloc) + 1.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        if len(A) < 2: return len(A)

        def check(A):
            mn, mx = min(A), max(A)
            minloc, maxloc, ans = -1, -1, 0
            for i, num in enumerate(A):
                if num == mn: minloc = i
                if num == mx: maxloc = i
                if -1 in [minloc, maxloc]: continue
                ans += min(minloc, maxloc) + 1
            return ans

        ans = check(A)
        for cand in [min(A), max(A)]:
            if A.count(cand) == 1:
                idx = A.index(cand)
                ans = max(ans, check(A[:idx] + A[idx + 1 :]))

        return ans