LeetCode 3366: Minimum Array Sum Solution

Master LeetCode problem 3366 (Minimum Array Sum), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3366. Minimum Array Sum

Medium

Array Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use a dynamic programming approach. We will iterate over all possible combinations of applying Operation 1 and Operation 2 to each element in the array. For each element, we will keep track of the minimum sum achievable by applying the operations. We will use a 2D dp array to store this information.

Initialize a 2D dp array of size nums.length x op1 + 1 x op2 + 1. dp[i][j][k] will represent the minimum sum achievable considering the first i elements of nums, applying Op1 j times, and applying Op2 k times.
Initialize the dp array with values representing an impossible state (e.g., a large number).
Set dp[0][0][0] = nums[0] as the base case.
Iterate over all elements of nums from 0 to n-1 and for each element, iterate over possible values of j and k from 0 to op1 and op2, respectively.
For each element, update the dp array based on the current element, the previous states, and the operations.
The answer will be the minimum sum achievable considering all elements of nums and applying Op1 and Op2 at most op1 and op2 times, respectively.

Time Complexity: O(n * op1 * op2) Space Complexity: O(n * op1 * op2)

Solution Code

class Solution {
    public int minSum(int[] nums, int k, int op1, int op2) {
        int n = nums.length;
        int[][][] dp = new int[n][op1 + 1][op2 + 1];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= op1; j++) {
                for (int l = 0; l <= op2; l++) {
                    dp[i][j][l] = Integer.MAX_VALUE;
                }
            }
        }
        
        dp[0][0][0] = nums[0];
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= op1; j++) {
                for (int l = 0; l <= op2; l++) {
                    for (int m = 0; m <= Math.min(j, i); m++) {
                        if (nums[i] >= k) {
                            dp[i][j][l] = Math.min(dp[i][j][l], nums[i] - k + dp[i-1][j-m][l]);
                        }
                        dp[i][j][l] = Math.min(dp[i][j][l], (nums[i] + 1) / 2 + dp[i-1][j-m][l]);
                    }
                }
            }
        }
        
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j <= op1; j++) {
            for (int l = 0; l <= op2; l++) {
                minSum = Math.min(minSum, dp[n-1][j][l]);
            }
        }
        
        return minSum;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3366 (Minimum Array Sum)?

This page provides optimized solutions for LeetCode problem 3366 (Minimum Array Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3366 (Minimum Array Sum)?

The time complexity for LeetCode 3366 (Minimum Array Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3366 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3366 in Java, C++, or Python.

Back to LeetCode Solutions