801. Minimum Swaps To Make Sequences Increasing
We have two integer sequences A
and B
of the same non-zero length.
We are allowed to swap elements A[i]
and B[i]
. Note that both elements are in the same index position in their respective sequences.
At the end of some number of swaps, A
and B
are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1]
.)
Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.
Example: Input: A = [1,3,5,4], B = [1,2,3,7] Output: 1 Explanation: Swap A[3] and B[3]. Then the sequences are: A = [1, 3, 5, 7] and B = [1, 2, 3, 4] which are both strictly increasing.
Note:
A, B
are arrays with the same length, and that length will be in the range[1, 1000]
.A[i], B[i]
are integer values in the range[0, 2000]
.
Rust Solution
struct Solution;
impl Solution {
fn min_swap(a: Vec<i32>, b: Vec<i32>) -> i32 {
let n = a.len();
let mut keep = vec![n; n];
let mut swap = vec![n; n];
keep[0] = 0;
swap[0] = 1;
for i in 1..n {
if a[i - 1] < a[i] && b[i - 1] < b[i] {
keep[i] = keep[i - 1];
swap[i] = swap[i - 1] + 1;
}
if a[i - 1] < b[i] && b[i - 1] < a[i] {
keep[i] = keep[i].min(swap[i - 1]);
swap[i] = swap[i].min(keep[i - 1] + 1);
}
}
swap[n - 1].min(keep[n - 1]) as i32
}
}
#[test]
fn test() {
let a = vec![1, 3, 5, 4];
let b = vec![1, 2, 3, 7];
let res = 1;
assert_eq!(Solution::min_swap(a, b), res);
}
Having problems with this solution? Click here to submit an issue on github.