🚀 Java O(n^2) DP with 💡 explanation and comments
Intuition\nWe are going to use dynamic programming to build up an answer. We sort our pairs by nums2 values ascending, because zeroing out a nums1 value which h
# Intuition\nWe are going to use dynamic programming to build up an answer. We sort our pairs by nums2 values ascending, because zeroing out a nums1 value which has a large nums2 value is best later (the earlier you do it, the more times you add nums2 value, and you don\'t want to do it twice, else why bother the first time).\n\nLet\'s talk about corresponding nums1 and nums2 values as "pairs". This just gives us an easier way to say it than thinking about two separate lists and corrresponding indices. In fact, we can transform the data into an array of pairs to make things easier to work with.\n\nThen we think about the fact that we can compute how much reduction we can do for 0 pairs (0 reduction in sum no matter how many operations), and we can compute how much reduction in sum we can get for i pairs and j operations as follows:\n- we cannot do worse than the reduction in sum we get from i - 1 pairs and j operations, because we are free to choose whether to zero out the i\'th pair or not with one of those j operations\n- but, we could do better if we look at the reduction from i - 1 pairs and j - 1 operations, then use an operation on the i\'th pair\n- so, we check both of these and take the maximum\n- this allows us to build up a two-dimensional `dp` array\n\nOnce we have the ability to know the max reduction for `j` operations on `i` pairs, we can find the minimum number of operations for which the sum reduction is sufficient for the total sum to be at most `x`.\n\n# Approach\nSo, to summarize, we are going to:\n- transform our data to pairs and sort them by their nums2 values ascending\n- create a `dp` array of size `[n + 1][n + 1]` to track the maximum sum reduction for using `j` operations among the first `i` pairs\n- now `dp[n][t]` is the optimal sum reduction in time `t`\n- without operations, the total sum at time `t` is `sum1 + (sum2 * t)`\n- so our answer is the smallest `t` such that `sum1 + (sum2 * t) - dp[n][t]` is less than or equal to `x` (or -1 if there is no such `t`)\n\n# Complexity\n- Time complexity: We have an O(n^2) buildup of the `dp` array.\n\n- Space complexity: Our `dp` array uses O(n^2) space\n\n# Java Code\n\nThis code ran in 18-20ms as of August, 2023 (faster than 100% at the time).\n\n```\nclass Solution {\n\n    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {\n        // We convert to array for faster int math and less clunky get(i)\n        // syntax. This also gives us a single object pairs[i] to represent\n        // each corresponding pair, and lets us sort our pairs easily.\n        // While converting, we compute the sums of the two lists which we\n        // will need later.\n        final int[][] pairs = new int[nums1.size()][2];\n        int sum1 = 0;\n        int sum2 = 0;\n        for (int i = 0; i < nums1.size(); ++i) {\n            final int n1 = nums1.get(i);\n            final int n2 = nums2.get(i);\n            sum1 += n1;\n            sum2 += n2;\n            pairs[i][0] = n1;\n            pairs[i][1] = n2;\n        }\n        // Sort pairs by nums2 value, breaking tie by nums1 value. Note\n        // that the tiebreaker doesn\'t actually matter, but I prefer a\n        // complete ordering (helps predictability if debugging, etc).\n        Arrays.sort(pairs, (a, b) -> {\n            int diff = Integer.compare(a[1], b[1]);\n            if (diff == 0) {\n                diff = Integer.compare(a[0], b[0]);\n            }\n            return diff;\n        });\n        final int n = pairs.length;\n        // We are going to compute how much we reduce the total with j ops\n        // using any combination of the first i elements, working up to\n        // computing j ops using all n elements. Generally, we cannot do\n        // worse by including elements with larger nums2 values for same\n        // number of ops, since we are free to ignore these elements. So,\n        // we start with the sum reduction for i - 1 values and j ops as a\n        // baseline, then compare that baseline with what happens if we\n        // remove one op and replace it with zeroing out the (i - 1)st\n        // pair. This lends itself to dynamic programming. The value\n        // dp[i][j] tracks the best sum reduction for j operations used\n        // among the first i elements.\n        final int[][] dp = new int[n + 1][n + 1];\n        for (int i = 1; i <= n; ++i) {\n            for (int j = 1; j <= i; ++j) {\n                final int withoutIthPair = dp[i - 1][j]; // baseline\n                final int withIthPair = dp[i - 1][j - 1] // one fewer op\n                        + (pairs[i - 1][1] * j) // reduce by j additions of num2\n                        + pairs[i - 1][0];      // reduce by initial num1\n                dp[i][j] = Math.max(withoutIthPair, withIthPair);\n            }\n        }\n        // Now, we just look for the fewest number of ops t which provides\n        // sufficient sum-reduction to get the total sum at or below x.\n        for (int t = 0; t <= n; ++t) {\n            final int sum = sum1 + (sum2 * t) - dp[n][t];\n            if (sum <= x) {\n                return t;\n            }\n        }\n        // And, we didn\'t find any such t, so the answer is -1.\n        return -1;\n    }\n\n}\n```\n\n# Standard Plea\nIf this posting was useful, helped you better understand the problem, or at least wasn\'t a waste of your time, **I would appreciate your upvote**. On the other hand, if you found it less than useful, **any constructive criticism in the comments is appreciated**. Thanks, and happy coding!\n
['Array', 'Dynamic Programming', 'Java']