Practice #031: Leetcode Biweekly Contest 86

Leetcode: 2395. Find Subarrays With Equal Sum

from typing import List


class Solution:
    def findSubarrays(self, nums: List[int]) -> bool:
        c = {}
        for i in range(len(nums) - 1):
            s = nums[i] + nums[i + 1]
            c.setdefault(s, 0)
            c[s] += 1
            if c[s] >= 2:
                return True
        return False

Leetcode: 2396. Strictly Palindromic Number

Problem Statement

class Solution:
    def isStrictlyPalindromic(self, n: int) -> bool:
        def isp(x):
            i = 0
            j = len(x) - 1
            while i < j:
                if x[i] != x[j]:
                    return False
                i += 1
                j -= 1
            return False

        def convert(n, b):
            if n < b:
                return [n]

            ans = []
            while n > 0:
                ans.append(n % b)
                n = n // b

            ans.reverse()
            return ans

        ans = True
        for b in range(2, n - 1):
            ans = ans and isp(convert(n, b))

        return ans

Leetcode: 2397. Maximum Rows Covered by Columns

Problem Statement

from typing import List


class Solution:
    def maximumRows(self, mat: List[List[int]], cols: int) -> int:
        N = len(mat)
        M = len(mat[0])

        ans = float("-inf")
        for s in range(2**M):
            if s.bit_count() != cols:
                continue
            cur = 0
            for i in range(N):
                if all(mat[i][j] == 0 or s & (1 << j) for j in range(M)):
                    cur += 1
            ans = max(ans, cur)

        return ans

Leetcode: 2398. Maximum Number of Robots Within Budget

Problem Statement

Can we break-down the problem in small and easily to solve parts? We can use a sorted list to query the max element in the interval and Prefix Sum to compute the sum. With this info, we can use a Sliding Window to go over all valid intervals and find the bigger one. Time complexity is \(O(n \log n)\) and space is \(O(n)\).

from sortedcontainers import SortedList
from typing import List


class Solution:
    def maximumRobots(
        self, chargeTimes: List[int], runningCosts: List[int], budget: int
    ) -> int:
        N = len(chargeTimes)
        ans = 0
        start = 0

        pref = list(accumulate(runningCosts))
        maxq = SortedList([])

        def cost():
            sumv = pref[end] - (pref[start - 1] if start - 1 >= 0 else 0)
            return maxq[-1] + (end - start + 1) * sumv

        for end in range(N):
            maxq.add(chargeTimes[end])
            while maxq and cost() > budget:
                maxq.remove(chargeTimes[start])
                start += 1
            if maxq:
                ans = max(ans, end - start + 1)
        return ans