A. Find Subarrays With Equal Sum (opens new window)

We can use a set S to store the values of each subarray of A, check if any value occurs more than once.

DETAILS

def findSubarrays(self, A: List[int]) -> bool:
        S, n = set(), len(A)
        for i in range(n - 1):
            if A[i] + A[i + 1] in S:
                return True
            S.add(A[i] + A[i + 1])
        return False

B. Strictly Palindromic Number (opens new window)

Return False.

DETAILS

def isStrictlyPalindromic(self, n: int) -> bool:
    return False

C. Maximum Rows Covered by Columns (opens new window)

Since the size of the input array is quite small, we just need to find out all the possible ways to fill columns.

In python, we can use itertools.combinations to iterate all possible unique combinations.

Then find the maximum number of rows filled from these ways.

DETAILS

def maximumRows(self, A: List[List[int]], k: int) -> int:
        ans, m, n = 0, len(A), len(A[0])
        
        for cand in itertools.combinations(list(range(n)), k):
            S, res = set(cand), 0
            for r in range(m):
                cur = 0
                for c in range(n):
                    if A[r][c] == 0 or c in S:
                        cur += 1
                res += (cur == n)
            ans = max(ans, res)
        
        return ans

D. Maximum Number of Robots Within Budget (opens new window)

Solution 1. Binary Search, O(N logN)

Use binary search to locate the largest window that hold the valid range.

DETAILS

def maximumRobots(self, C: List[int], R: List[int], b: int) -> int:
        def helper(k):
            st, tmp = collections.deque(), 0
            for i in range(k):
                while st and C[i] >= C[st[-1]]:
                    st.pop()
                st.append(i)
                tmp += R[i]
            if tmp * k + C[st[0]] <= b: 
                return True
            for i in range(k, len(C)):
                tmp += R[i] - R[i - k]
                while st and C[i] >= C[st[-1]]:
                    st.pop()               
                st.append(i)
                while i - st[0] >= k:
                    st.popleft()
                if tmp * k + C[st[0]] <= b:
                    return True
            return False

        if min(c + r for c, r in zip(C, R)) > b: return 0
        n = len(C)
        left, right = 1, n
        while left < right:
            mid = (left + right + 1) >> 1
            if helper(mid):
                left = mid
            else:
                right = mid - 1
        return left

Solution 2. Monostack, O(N)

Since the value of a window that having one fixed end is monotonically increasing according to length, we used a monostack to store the maximum value within the window. While the current value is larger than the limit, we pop value from left.

DETAILS

def maximumRobots(self, C: List[int], R: List[int], b: int) -> int:
        ans, tmp, n = 0, 0, len(C)
        CC, RR = collections.deque(), collections.deque()
        for i in range(n):
            tmp += R[i]
            while CC and C[CC[-1]] <= C[i]:
                CC.pop()
            CC.append(i)
            RR.append(i)
            
            while RR and C[CC[0]] + (RR[-1] - RR[0] + 1) * tmp > b:
                tmp -= R[RR[0]]
                RR.popleft()
                while (RR and CC[0] < RR[0]) or (not RR and CC):
                    CC.popleft()

            if RR:
                ans = max(ans, RR[-1] - RR[0] + 1)
        
        return ans