<commit_before>// Time:  O(k * (m + n + k)) ~ O(k * (m + n + k^2))
// Space: O(m + n + k^2)

// DP + Greedy solution. (48ms)
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res(k);
        const int m = nums1.size(), n = nums2.size();
        vector<vector<int>> max_digits1(k + 1), max_digits2(k + 1);
        getMaxDigits(nums1, max(0, k - n), min(k, m), &max_digits1);  // O(k * m) time, O(m + k^2) space.
        getMaxDigits(nums2, max(0, k - m), min(k, n), &max_digits2);  // O(k * n) time, O(n + k^2) space.
        for (int i = max(0, k - n); i <= min(k, m); ++i) {  // k * O(k) ~ k * O(k^2) time.
            int j = k - i;
            vector<int> tmp(k);
            merge(max_digits1[i], max_digits2[j], &tmp);
            if (tmp > res) {
                res = tmp;
            }
        }<commit_msg>Update create-maximum-number.cpp<commit_after>// Time:  O(k * (m + n + k)) ~ O(k * (m + n + k^2))
// Space: O(m + n + k^2)

// DP + Greedy solution. (48ms)
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> res(k);
        const int m = nums1.size(), n = nums2.size();
        vector<vector<int>> max_digits1(k + 1), max_digits2(k + 1);
        getMaxDigits(nums1, max(0, k - n), min(k, m), &max_digits1);  // O(k * m) time, O(m + k^2) space.
        getMaxDigits(nums2, max(0, k - m), min(k, n), &max_digits2);  // O(k * n) time, O(n + k^2) space.
        for (int i = max(0, k - n); i <= min(k, m); ++i) {  // k * O(k) ~ k * O(k^2) time.
            int j = k - i;
            vector<int> tmp(k);
            merge(max_digits1[i], max_digits2[j], &tmp);
            if (tmp > res) {
                res = move(tmp);
            }
        }
{'fraction_non_alphanumeric': 0.20557103064066853, 'fraction_numerical': 0.026740947075208913, 'mean_word_length': 1.978441127694859, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5259662', 'n_tokens_mistral': 765, 'n_tokens_neox': 750, 'n_words': 193}