23.03.21 Today’s Leetcode

2348. Number of Zero-Filled Subarrays (medium)

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        res = 0
        while i < n:
            j = i
            while j < n and nums[j] == 0:
                j += 1
            p = j - i
            # print(p)
            res += p * (p + 1) // 2
            i = j + 1
            # [0, 0] => 3
            # m + m - 1 + ... 1 = m (m + 1) / 2
        return res

            

319. Bulb Switcher (medium)

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return (int)(n ** 0.5)

318. Maximum Product of Word Lengths (medium)

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        d = [set(i) for i in words]
        res = 0
        for i in range(n):
            for j in range(i + 1, n):
                n3 = len(d[i] & d[j])
                if n3 == 0:
                    res = max(res, len(words[i]) * len(words[j]))
        return res    

327. Count of Range Sum (hard)

TLE : 58/67 testcases passed
Naive Approach

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        arr = []
        cur = 0
        n = len(nums)
        for num in nums:
            cur += num
            arr.append(cur)

        def between(k):
            return lower <= k and k <= upper
        
        res = 0
        for i in range(n):
            if between(arr[i]):
                res += 1
            for j in range(i):
                if between(arr[i] - arr[j]):
                    res += 1
        
        return res

Merge Sort Approach

public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] sums = new long[n + 1];
    for (int i = 0; i < n; ++i)
        sums[i + 1] = sums[i] + nums[i];
    return countWhileMergeSort(sums, 0, n + 1, lower, upper);
}

private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
    if (end - start <= 1) return 0;
    int mid = (start + end) / 2;
    int count = countWhileMergeSort(sums, start, mid, lower, upper) 
              + countWhileMergeSort(sums, mid, end, lower, upper);
    int j = mid, k = mid, t = mid;
    long[] cache = new long[end - start];
    for (int i = start, r = 0; i < mid; ++i, ++r) {
        while (k < end && sums[k] - sums[i] < lower) k++;
        while (j < end && sums[j] - sums[i] <= upper) j++;
        while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
        cache[r] = sums[i];
        count += j - k;
    }
    System.arraycopy(cache, 0, sums, start, t - start);
    return count;
}

338. Counting Bits (easy)

DP Approach

class Solution(object):
    def countBits(self, num):
        if num == 0: 
            return [0]
        dp = [0] * (num + 1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2, num + 1):
            if i % 2 == 0:
                dp[i] = dp[i // 2]
            else:
                dp[i] = 1 + dp[(i - 1) // 2]
                
        return dp