Jumlah permen yang udah cukup dibanding anak di kiri masih bisa melanggar aturan dengan anak di kanan. Aku pakai dua pass untuk mengecek kedua sisi dan menyimpan kebutuhan yang lebih besar di setiap posisi.
Batasannya
Setiap anak dari n anak dalam barisan punya rating. Jumlah permennya harus mengikuti dua aturan:
- Setiap anak harus dapat minimal satu permen
- Anak dengan rating lebih tinggi harus dapat permen lebih banyak daripada tetangganya
Tujuannya adalah mencari jumlah permen minimum yang dibutuhkan.
Baseline satu arah melakukan scan sekali dan membandingkan setiap anak dengan anak di sebelah kirinya:
function candyNaive(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1);
// Only checking left neighbor
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
return candies.reduce((a, b) => a + b, 0);
}
Cara ini nggak bisa menyelesaikan [1, 0, 2] karena anak pertama tetap butuh permen lebih banyak daripada anak yang di tengah.
Karena itu, aku pakai dua pass. Pass pertama mengecek setiap anak terhadap tetangga kirinya. Pass kedua mengecek setiap anak terhadap tetangga kanannya. Pass kedua memakai Math.max untuk mempertahankan jumlah yang lebih besar dari pass pertama.
function candy(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1); // Everyone starts with 1 candy
// First pass: left to right
// If current child has higher rating than left neighbor, give more candy
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Second pass: right to left
// If current child has higher rating than right neighbor,
// make sure they have at least one more candy
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
// Use Math.max to preserve what we did in first pass
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
return candies.reduce((a, b) => a + b, 0);
}
// Example usage:
const ratings = [1, 0, 2];
console.log(candy(ratings)); // Output: 5
Untuk [1, 0, 2], jumlah permennya berubah seperti ini:
- Awal:
[1, 1, 1] - Setelah pass pertama:
[1, 1, 2](anak 2 punya rating lebih tinggi daripada anak 1) - Setelah pass kedua:
[2, 1, 2](anak 0 punya rating lebih tinggi daripada anak 1, jadi butuh minimal 2)
Total minimumnya 2 + 1 + 2 = 5.
Pemanggilan Math.max mencegah pass kedua mengurangi jumlah yang udah memenuhi batasan sisi kiri. Kalau pass pertama memberi 3 dan kebutuhan dari sisi kanan adalah 2, anak itu tetap dapat 3.
Dua pass yang sama di Java:
import java.util.Arrays;
public class Candy {
public static int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
// Pass from left to right
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Pass from right to left
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
int totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
public static void main(String[] args) {
int[] ratings = {1, 0, 2};
System.out.println(candy(ratings)); // Output: 5
}
}
Kenapa dua pass ini cukup
Setiap pass mengunjungi semua anak sekali, jadi algoritmanya butuh O(n) waktu. Array candies memakai O(n) extra space.
Di setiap posisi, kedua pass menghitung jumlah minimum yang dibutuhkan oleh rangkaian rating yang naik dari masing-masing sisi. Mengambil jumlah yang lebih besar memenuhi keduanya tanpa menambah permen yang nggak perlu.

Memuat komentar...