LeetCode 321: Create Maximum Number
LeetCode 321 Solution Explanation
Explanation
To solve this problem, we can divide it into two subproblems:
- Create the maximum number of length x from a single array while preserving the relative order of the digits.
- Merge two maximum numbers created from the two arrays to form the final maximum number of length k.
For the first subproblem, we can use a stack to store the maximum number of length x by popping elements from the stack if a greater element is found. For the second subproblem, we can merge the two maximum numbers by comparing the elements at each position to pick the larger one.
By combining these two subproblems, we can create the maximum number of length k from the two arrays.
Time Complexity: O(k * (m + n)) where m and n are the lengths of the input arrays. Space Complexity: O(k) for storing the final result.
LeetCode 321 Solutions in Java, C++, Python
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length;
int n = nums2.length;
int[] result = new int[k];
for (int i = Math.max(0, k - n); i <= k && i <= m; i++) {
int[] candidate = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
if (isGreater(candidate, 0, result, 0)) {
result = candidate;
}
}
return result;
}
private int[] maxArray(int[] nums, int k) {
int[] result = new int[k];
int len = 0;
for (int i = 0; i < nums.length; i++) {
while (len > 0 && len + nums.length - i > k && result[len - 1] < nums[i]) {
len--;
}
if (len < k) {
result[len++] = nums[i];
}
}
return result;
}
private int[] merge(int[] nums1, int[] nums2, int k) {
int[] result = new int[k];
int i = 0, j = 0, r = 0;
while (r < k) {
if (isGreater(nums1, i, nums2, j)) {
result[r++] = nums1[i++];
} else {
result[r++] = nums2[j++];
}
}
return result;
}
private boolean isGreater(int[] nums1, int i, int[] nums2, int j) {
while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);
}
}Interactive Code Editor for LeetCode 321
Improve Your LeetCode 321 Solution
Use the editor below to refine the provided solution for LeetCode 321. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...