BinarySearch 0191 Make Lists Same with Sublist Sum Operations

Problem statement

https://binarysearch.com/problems/Make-Lists-Same-with-Sublist-Sum-Operations/

Solution 1

Let us evaluate cumulative sums for arrays, then what is asked to find is the longest common subsequene. Also values are different in cumulative sums, so we can use problem Leetcode 1713 Minimum Operations to Make a Subsequence, which uses LIS problem.

Complexity

It is O(n log n) for time and space.

Code

class Solution:
    def solve(self, l0, l1):
        A0 = list(accumulate(l0))
        A1 = list(accumulate(l1))
        if A0[-1] != A1[-1]: return -1

        d = {x:i for i, x in enumerate(A0)}
        A = [d[x] for x in A1 if x in d]

        dp = [10**10] * (len(A) + 1)
        for elem in A: 
            dp[bisect_left(dp, elem)] = elem  
        
        return dp.index(10**10)

Solution 2

In fact, after we evaluate cumulative sums, we can check the length of intersection.

Complexity

It is O(n) for time and O(n) for space.

Code

class Solution:
    def solve(self, l0, l1):
        acc0 = list(accumulate(l0))
        acc1 = list(accumulate(l1))
        if acc0[-1] != acc1[-1]:return -1
        return len(set(acc0) & set(acc1))