Why is this DFS + Memoization solution for selecting indices in two arrays too slow while a similar approach is more efficient?

Question

I was solving LeetCode problem 3290. Maximum Multiplication Score:

You are given an integer array a of size 4 and another integer array b of size at least 4.

You need to choose 4 indices i₀, i₁, i₂, and i₃ from the array b such that i₀ < i₁ < i₂ < i₃. Your score will be equal to the value a[0] * b[i₀] + a[1] * b[i₁] + a[2] * b[i₂] + a[3] * b[i₃].

Return the maximum score you can achieve.

Example:

Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]

Output: 26

Explanation: Choose indices 0, 1, 2, and 5 from b.

My Attempt:

I wrote two recursive + memoization solutions, but one of them exceeds the given time limit ("Time Limit Exceeded" TLE) for larger n. Here are the two approaches:

Solution 1 (TLE)

class Solution:
    def maxScore(self, a, b):
        def dfs(i, j):
            if i == len(a):  # All elements in `a` processed
                return 0
            if (i, j) in memo:  # Return memoized result
                return memo[(i, j)]

            max_result = float("-inf")
            for index in range(j, len(b)):
                if len(b) - index < len(a) - i:  # Not enough elements left in `b`
                    break
                max_result = max(max_result, a[i] * b[index] + dfs(i + 1, index + 1))

            memo[(i, j)] = max_result
            return max_result

        memo = {}
        return dfs(0, 0)

Solution 2 (Works)

class Solution:
    def maxScore(self, a, b):
        def dfs(i, picked):
            if picked == 4:  # All elements in `a` processed
                return 0
            if len(b) - i + picked < 4:  # Not enough elements left in `b`
                return float("-inf")
            if (i, picked) in memo:  # Return memoized result
                return memo[(i, picked)]

            pick = a[picked] * b[i] + dfs(i + 1, picked + 1)  # Pick this index
            skip = dfs(i + 1, picked)  # Skip this index

            memo[(i, picked)] = max(pick, skip)
            return memo[(i, picked)]

        memo = {}
        return dfs(0, 0)

Question:

Why does Solution 1 lead to TLE while Solution 2 works efficiently? I think without the memoization both the solutions will have the same time complexity of O(2^n) of pick or not pick, but I can't pinpoint why the pruning or memoization doesn't seem to help as much as in Solution 2. Could someone provide a detailed explanation?

EuanG · Accepted Answer · 2024-11-25 12:11:24Z

0

Solution 1:

Time Complexity: O(m * n^2)
- dfs(i, j) explores all valid indices j in b for every index i in a.
- Total states in memoization: O(m * n).
- Each state performs O(n) work (looping through indices in b).
- Total complexity: O(m * n^2).

Solution 2:

Time Complexity: O(m * n)
- dfs(i, picked) makes two choices at each step: pick or skip.
- Total states in memoization: O(m * n).
- Each state does O(1) work (binary decision).
- Total complexity: O(m * n).

Key Difference:

Solution 1 loops over remaining indices in b for every state.
Solution 2 only makes a binary choice per state.

TLDR: Both do not have O(n^2) time complexity.

Also, I believe solution one also has worse-case of O(n^4) (fails to prune invalid paths)

answered Nov 25, 2024 at 12:11

EuanG

1,5551 gold badge14 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Why is this DFS + Memoization solution for selecting indices in two arrays too slow while a similar approach is more efficient?

Example:

My Attempt:

Solution 1 (TLE)

Solution 2 (Works)

Question:

1 Answer 1

Solution 1:

Solution 2:

Key Difference:

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Example:

My Attempt:

Solution 1 (TLE)

Solution 2 (Works)

Question:

1 Answer 1

Solution 1:

Solution 2:

Key Difference:

Comments

Your Answer

Sign up or log in

Post as a guest

Related