Solusi Leetcode - Candy

Setiap anak butuh jumlah permen yang memenuhi perbandingan rating dengan kedua tetangganya. Satu pass dari kiri ke kanan memenuhi perbandingan dengan tetangga kiri. Pass kedua, dari kanan ke kiri, memenuhi perbandingan dengan tetangga kanan.

Batasannya

Ada n anak yang berbaris dalam satu antrean, masing-masing punya rating. Aturannya simpel:

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:

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, saya 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.

Implementasi lengkap dengan dua pass-nya seperti ini:

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

Masing-masing pass mengunjungi setiap anak sekali, jadi time complexity-nya O(n). Array candies memakai O(n) extra space. Update dengan Math.max berjalan dalam waktu konstan. Setiap Math.max cuma membandingkan dua jumlah yang bersebelahan.

Mulai dari state valid yang paling minimum, terapkan batasan dari satu arah, lalu terapkan arah sebaliknya sambil mempertahankan nilai yang lebih kuat. Pola ini juga berlaku untuk soal lain yang kondisi tetangganya mengarah ke dua sisi.