【LeetCode #2918】 Minimum Equal Sum of Two Arrays After Replacing Zeros
はじめに
今日の LeetCode Daily は medium 問題でした．パッと見で「難しいな...」と思うような内容でしたが，考え方を整理してみると，意外とスッと解けます．
本記事ではその流れを解説します．
問題概要
2つの配列 nums1・nums2 が与えられます．それぞれの配列には一部 0 が含まれており，この 0 を 1 以上の値に変更することで，2つの配列の総和を一致させることができるかを判定します．
- 一致が可能であれば，そのときの変更後の配列の合計値の最小値を返します
- 一致できない場合は -1 を返します
例
入力： nums1 = [3, 2, 0, 1, 0], nums2 = [6, 5, 0]
出力： 12
説明： nums1 = [3, 2, 2, 1, 4], nums2 = [6, 5, 1] のとき一致する
入力： nums1 = [2, 0, 2, 0], nums2 = [1, 4]
出力： -1
説明： どんな値を入れても一致しないので，-1 を返す
カテゴリ
問題難易度：medium
タグ：Array, Greedy
解法
まずはこの問題で 「一致させることが不可能になる条件」 を明確にしておきます．不可能になるパターンは，nums1・nums2 内の 0 を 1 以上の任意の値に変更しても総和が一致しないときです．このとき，1 以上の任意の値は無限と考えられるので，下限を考えます．つまり，配列内の 0 を全て 1 にしても 2 つの配列の総和が一致しないときです．これは例の#2が参考になります．
再掲
入力： nums1 = [2, 0, 2, 0], nums2 = [1, 4]
出力： -1
説明： どんな値を入れても一致しないので，-1 を返す
以下に nums1・nums2 の総和，0 の数，0 -> 1 としたときの最小値を整理します．
| 総和 | 0 の数 | 0 -> 1 としたときの最小値 | |
|---|---|---|---|
| nums1 | 4 | 2 | 6 |
| nums2 | 5 | 0 | 5 |
つまり，片方の配列内の 0 の数が 0 かつ，0 -> 1 としたときの最小値がもう一方の配列よりも小さいとき，どう頑張っても一致させることはできません．これが不可能なパターンになります．
逆に言えば，上記の不可能条件に該当しなければ一致させることは可能です．その場合，配列内の 0 をすべて 1 に変えたときの 最小合計値の大きい方 が答えになります．
まとめると...
まず，0 をすべて最小値である 1 に置き換えたときの合計（=minv1, minv2）を考えます．もし一方の配列に 0 が含まれておらず，どう足しても，もう一方の min 合計に追いつけない場合は，合計を一致させることは不可能です．それ以外の場合は，一方を必要に応じて膨らませることで一致させることができ，最小合計は max(minv1, minv2) になります．
class Solution:
def minSum(self, nums1: List[int], nums2: List[int]) -> int:
sum1 = sum(nums1)
sum2 = sum(nums2)
zero1 = nums1.count(0)
zero2 = nums2.count(0)
minv1 = sum1 + zero1
minv2 = sum2 + zero2
if (zero1 == 0 and minv2 > minv1) or (zero2 == 0 and minv1 > minv2):
return -1
return max(minv1, minv2)
まとめ
今日は配列内の値を変更して総和を一致させる問題を解説しました．
初めこの問題を見たときは「組み合わせたくさんありそう...」と思いましたが，落ち着いて幾つかの例を考えてみると，割と簡単に解ける問題だと分かりました．medium レベルの問題は一見難しそうに見えても，実はロジックを丁寧に整理すれば簡単に解けるケースも多そうですね...．
今後も Daily や類題を中心に，解法の整理やアイデアを投稿していこうと思います．
おまけ
TypeScript はこちら
function minSum(nums1: number[], nums2: number[]): number {
const sum1: number = nums1.reduce((curr, val) => curr+val, 0);
const sum2: number = nums2.reduce((curr, val) => curr+val, 0);
const zero1: number = nums1.filter((x) => x == 0).length;
const zero2: number = nums2.filter((x) => x == 0).length;
const minv1: number = sum1 + zero1;
const minv2: number = sum2 + zero2;
if ((zero1 === 0 && minv2 > minv1) || (zero2 === 0 && minv1 > minv2)) {
return -1;
}
return Math.max(minv1, minv2);
};