LeetCode, Hard, last two problems: 2809. Min Time to Make Array Sum At Most x & 2813. Max Elegance of a K-Length Subseq

2809. Min Time to Make Array Sum: Efficient Swift solution, using dynamic programming, for minimizing time to reach a sum in arrays A and B. Time: O(n²), Space: O(n).

2813. Max Elegance of K-Length Subseq: Swift code for elegantly selecting unique k-length subsequences with profit and categories. Solution uses sorting and iteration. Time: O(nlogn), Space: O(n).

Github: https://github.com/sergeyleschev/leetcode-swift

2809. Minimum Time to Make Array Sum At Most x

Description

LeetCode

Approach

We begin by calculating the total sum of the arrays A and B as sa and sb respectively.

If no actions are taken, at i seconds, we would have a total of sb * i + sa.

During the t seconds, we select t elements. When we consider these selected elements, A[i] would be removed. The sum for these selected elements would be b1 * (t — 1) + b2 * (t — 2) + … + bt * 0, where b1, b2, b3, …, bt are arranged in increasing order.

To solve this problem, we sort all the pairs (B[i], A[i]) based on the value of B[i].

We then utilize dynamic programming (dp) with the following logic:
dp[j][i] represents the maximum value we can reduce within i seconds, using j + 1 step-smallest integers.

The dp equation is as follows:
dp[j][i] = max(dp[j][i], dp[j — 1][i — 1] + i * b + a)

In the end, we return the value of i seconds if sb * i + sa — dp[n — 1][i] is less than or equal to x. If not, we return -1.

It is possible to optimize the space complexity by storing only the first dimension of the dp array.

Complexity

Time complexity: O(n^2)
Space complexity: O(n)

Code (Swift)

class Solution {
    func minimumTime(_ nums1: [Int], _ nums2: [Int], _ x: Int) -> Int {
        let n = nums1.count
        var dp = [Int](repeating: 0, count: n + 1)
        let sortedPairs = zip(nums2, nums1).sorted { $0.0 < $1.0 }
        for (j, (b, a)) in sortedPairs.enumerated() {
            for i in stride(from: j + 1, through: 1, by: -1) {
                dp[i] = max(dp[i], dp[i - 1] + i * b + a)
            }
        }
        let sa = nums1.reduce(0, +)
        let sb = nums2.reduce(0, +)
        for i in 0...n {
            if sb * i + sa - dp[i] <= x {
                return i
            }
        }
        return -1
    }
}

Source: Github

2813. Maximum Elegance of a K-Length Subsequence

Description

LeetCode

Intuition

The approach involves sorting the “items” array in descending order based on the “profiti”. By selecting the first “k” items, we ensure that we attain the highest possible “total_profit”.

Approach

Upon the selection of the initial “k” items, attention turns to the remaining “n — k” items. The viability of adding these items depends on whether they belong to an unexplored category (not yet in the “seen” set).

Given the restriction of maintaining a subsequence size of “k”, a pivotal decision arises. To optimize the elegance metric, the algorithm strategically replaces an existing item with the lowest profit when that item shares its category with another.

This iterative refinement process continually adjusts the subsequence while upholding the imperative of category distinctiveness.

The final output of the function encapsulates the pinnacle of elegance attained through this intricate process — a union of the cumulative impact of total profit and the singularity of categories.

Complexity

Time complexity: O(nlogn)
Space complexity: O(n)

Code (Swift)

class Solution {
    func findMaximumElegance(_ items: [[Int]], _ k: Int) -> Int {
        var items = items.sorted(by: { $0[0] > $1[0] })
        var res: Int64 = 0
        var cur: Int64 = 0
        var dup = [Int]()
        var seen = Set<Int>()
        for i in 0..<items.count {
            if i < k {
                if seen.contains(items[i][1]) {
                    dup.append(items[i][0])
                }
                cur += Int64(items[i][0])
            } else if !seen.contains(items[i][1]) {
                if dup.isEmpty {
                    break
                }
                cur += Int64(items[i][0] - dup.removeLast())
            }
            seen.insert(items[i][1])
            res = max(res, cur + Int64(seen.count) * Int64(seen.count))
        }
        return Int(res)
    }
}

Source: Github