Langsung ke konten
Brute force dulu

Pelajaran 3.3

Membaca constraint

6 menit · 7 langkah

  1. Langkah 1 dari 7 · Penjelasan

    Constraint diam-diam memberi tahu seberapa cepat solusimu harus jalan. Pakai patokan sekitar 10⁸ langkah sederhana per detik, lalu lihat batas n.

    • n ≤ 10³: O(n²) aman, sekitar 10⁶ langkah.
    • n ≤ 10⁵: butuh O(n) atau O(n log n).
    • n ≤ 10⁹: loop pun terlalu lambat. Cari rumus, atau O(log n).

  2. Langkah 2 dari 7 · Pilih pendekatan

    "Return berapa pasangan yang jumlahnya target." Constraint: 2 ≤ nums.length ≤ 1000.
    Apakah brute force semua pasangan cukup?

    1. Ya, sekitar 5 × 10⁵ cek, jauh di bawah batas
    2. Tidak, loop bersarang selalu terlalu lambat
    3. Tidak, harus pakai hash map supaya aman

  3. Langkah 3 dari 7 · Pilih pendekatan

    "Return berapa pasangan yang jumlahnya target." Constraint: 2 ≤ nums.length ≤ 10⁵.
    Apa yang kamu lakukan?

    1. Cari cara O(n) atau O(n log n), misalnya hash map atau sort dulu
    2. Tetap brute force, lalu berhenti lebih awal kalau ketemu
    3. Brute force dengan j = i + 1 supaya setengahnya

  4. Langkah 4 dari 7 · Pilih pendekatan

    "Return 1 + 2 + ... + n." Constraint: 1 ≤ n ≤ 10⁹. Apa pilihan yang tepat?

    1. Rumus n * (n + 1) / 2, satu langkah
    2. Loop dari 1 sampai n
    3. Simpan semua angka di array, lalu jumlahkan

  5. Langkah 5 dari 7 · Tebak hasilnya

    Apa yang di-return untuk n = 100?

    function solution(n) {  return n * (n + 1) / 2}
    1. 5050
    2. 10100
    3. 5000

  6. Langkah 6 dari 7 · Cari bug-nya

    "Return angka terbesar, atau 0 kalau array kosong." Constraint: 0 ≤ nums.length ≤ 10⁵.
    Untuk [], kode ini me-return undefined. Ketuk baris yang salah.

    function solution(nums) {  let best = nums[0]  for (let i = 1; i < nums.length; i++) {    if (nums[i] > best) best = nums[i]  }  return best}

  7. Langkah 7 dari 7 · Ringkasan

    • Patokan sekitar 10⁸ langkah per detik. Bandingkan dengan jumlah langkah solusimu.
    • n ≤ 10³ boleh O(n²). n ≤ 10⁵ butuh O(n log n) atau O(n). n ≤ 10⁹ butuh rumus atau O(log n).
    • Batas bawah juga penting. 0 ≤ length berarti array kosong pasti dites.

    Kartu pola

    Constraint menentukan kecepatan
    Kapan dipakai: Setelah membaca soal, sebelum memilih cara. Batas atas memberi kecepatan, batas bawah memberi edge case.
    // n ≤ 10³  -> O(n²)// n ≤ 10⁵  -> O(n log n), O(n)// n ≤ 10⁹  -> O(log n), O(1)