LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Candy

Pakai dua pass untuk membagi permen sambil memenuhi perbandingan rating setiap anak dengan tetangganya.

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:

  1. Setiap anak harus dapat minimal satu permen
  2. 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:

javascript
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.

javascript
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:

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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan