Skip to content

2934. Minimum Operations to Maximize Last Elements in Arrays 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int minOperations(vector<int>& nums1, vector<int>& nums2) {
    const int n = nums1.size();
    const int mn = min(nums1.back(), nums2.back());
    const int mx = max(nums1.back(), nums2.back());
    // the number of the minimum operations, where nums1[n - 1] is not swapped
    // with nums2[n - 1]
    int dp1 = 0;
    // the number of the minimum operations, where nums1[n - 1] is swapped with
    // nums2[n - 1]
    int dp2 = 0;

    for (int i = 0; i < n; ++i) {
      const int a = nums1[i];
      const int b = nums2[i];
      if (min(a, b) > mn)
        return -1;
      if (max(a, b) > mx)
        return -1;
      if (a > nums1.back() || b > nums2.back())
        ++dp1;
      if (a > nums2.back() || b > nums1.back())
        ++dp2;
    }

    return min(dp1, dp2);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int minOperations(int[] nums1, int[] nums2) {
    final int n = nums1.length;
    final int mn = Math.min(nums1[n - 1], nums2[n - 1]);
    final int mx = Math.max(nums1[n - 1], nums2[n - 1]);
    // the number of the minimum operations, where nums1[n - 1] is not swapped
    // with nums2[n - 1]
    int dp1 = 0;
    // the number of the minimum operations, where nums1[n - 1] is swapped with
    // nums2[n - 1]
    int dp2 = 0;

    for (int i = 0; i < n; ++i) {
      final int a = nums1[i];
      final int b = nums2[i];
      if (Math.min(a, b) > mn)
        return -1;
      if (Math.max(a, b) > mx)
        return -1;
      if (a > nums1[n - 1] || b > nums2[n - 1])
        ++dp1;
      if (a > nums2[n - 1] || b > nums1[n - 1])
        ++dp2;
    }

    return Math.min(dp1, dp2);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def minOperations(self, nums1: list[int], nums2: list[int]) -> int:
    n = len(nums1)
    mn = min(nums1[-1], nums2[-1])
    mx = max(nums1[-1], nums2[-1])
    # the number of the minimum operations, where nums1[n - 1] is not swapped
    # with nums2[n - 1]
    dp1 = 0
    # the number of the minimum operations, where nums1[n - 1] is swapped with
    # nums2[n - 1]
    dp2 = 0

    for a, b in zip(nums1, nums2):
      if min(a, b) > mn:
        return -1
      if max(a, b) > mx:
        return -1
      if a > nums1[-1] or b > nums2[-1]:
        dp1 += 1
      if a > nums2[-1] or b > nums1[-1]:
        dp2 += 1

    return min(dp1, dp2)