1674. Minimum Moves to Make Array Complementary - cocoder39/coco39_LC GitHub Wiki

1674. Minimum Moves to Make Array Complementary

explanation: check post + comments in this page

1 <= nums[i] <= limit

Thinking process:

1. 3 initial situations:

• T < A + B
  • diff = A+B-T and the max reduction we can achieve within 1 operation is max(A,B) - 1
  • max(A,B) - 1 >= diff => max(A,B) - 1 >= A+B-T => T >= A+B-max(A,B) + 1 = min(A,B) + 1
  • so min(A,B) + 1 <= T < A+B => 1 operation
  • max(A,B) - 1 < diff => 2 <= T < min(A,B) + 1 => 2 operations
• T = A + B => 0 operation
• T > A + B
  • max increase we can achieve within 1 operation is limit - min(A,B)
  • limit - min(A,B) >= diff => limit - min(A,B) >= T - A - B => T <= max(A, B) + limit
  • so A+B < T <= max(A, B) + limit => 1 operation
  • limit + min(A,B) < diff => max(A, B) + limit < T <= 2*limit => 2 operations

Summary

• 2 <= T < min(A, B) + 1 => 2 operations and left boundary is 2
• min(A, B) + 1 <= T < A + B => 1 operation and left boundary is min(A, B) + 1
• T = A + B => 0 operation and left boundary is A+B
• A+B < T <= max(A,B) + limit => 1 operation and left boundary is A+B + 1
• max(A,B) + limit + 1 <= target < 2*limit => 2 operations and left boundary is max(A,B) + limit

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        delta = collections.Counter()
        n = len(nums)
        for i in range(n // 2):
            a, b = nums[i], nums[n - 1 - i]
            delta[2] += 2
            delta[min(a, b) + 1] -= 1
            delta[a + b] -= 1
            delta[a + b + 1] += 1
            delta[max(a, b) + limit + 1] += 1
        
        res = float("inf")
        cur = 0
        for i in range(2, 2*limit + 1):
            cur += delta[i]
            res = min(res, cur)
        return res

2 key points:

1. boundary analysis
2. difference array:
   • efficient: delta[i] represents incremental diff between delta[i-1] and delta[i]. This way we don't need to update delta falling into a range (eg, 2 <= T < min(A, B) + 1) because the diff between delta[i-1] and delta[i] is always 0 in the range
   • avoid duplicated boundary eg, 2 can be equal to min(A, B) + 1