Specimen 07 · O(n) time, O(n) space

Prefix Sum + Hash Map

Keep one running total while scanning the array once. At each position, ask a hash map: "have I seen running total minus k before?" Every yes marks a subarray that sums to exactly k — found in O(1) per position instead of rechecking the whole history so far.

← Back to the Field Guide
07-namuna · O(n) vaqt, O(n) xotira

Prefix Sum + Hash Map

Array bir marta skanerlanayotganda bitta running total saqlanadi. Har bir pozitsiyada hash map'ga savol beriladi: "running total minus k'ni avval ko'rganmidim?" Har bir "ha" javobi — aynan k'ga teng bo'lgan subarray, va bu javob butun tarixni qayta qidirish o'rniga bitta O(1) lookup orqali topiladi.

← Qo'llanmaga qaytish

Intuition

Watch the bars below: as the scan moves right, every matching stretch that sums to the target gets boxed — no re-measuring, just one lookup per step against everything already seen.

Tushuncha (Intuition)

Quyidagi ustunlarga qarang: skan o'ngga siljigan sari, target'ga teng bo'lgan har bir mos qism ramkaga olinadi — qayta o'lchash yo'q, har qadamda hozirgacha ko'rilganlar orasida bitta lookup, xolos.

How It Works

  1. Start with count = 0 (subarrays found so far) and total = 0 (the running prefix sum).
  2. Seed the hash map before the loop begins: seen = {0: 1}. This records that a prefix sum of 0 — the "empty" total before any elements have been added — has already occurred once.
  3. Walk through the array one number at a time.
  4. Add the current number to total, so total always holds the prefix sum through the current index.
  5. Compute need = total - k — the exact prefix sum an earlier position would need to have had for everything between that position and here to sum to k.
  6. Look up need in seen. If it's there, add its count to count — each occurrence marks a different earlier position where a matching subarray begins.
  7. Only now, after the lookup, record the current total in the map: seen[total] = seen.get(total, 0) + 1. Doing this after the lookup — not before — keeps the current position from ever matching against itself.
  8. After the loop finishes, count holds the total number of subarrays that sum to exactly k.

Qanday Ishlaydi

  1. count = 0 (hozirgacha topilgan subarray'lar soni) va total = 0 (running prefix sum) bilan boshlang.
  2. Loop boshlanishidan oldin hash map'ni urug'lantiring: seen = {0: 1}. Bu hech qanday element qo'shilmagan holatdagi "bo'sh" prefix sum — 0 — allaqachon bir marta uchraganini bildiradi.
  3. Array bo'ylab bir vaqtning o'zida bitta sondan yurib chiqing.
  4. Hozirgi sonni totalga qo'shing, shunda total doimo hozirgi indeksgacha bo'lgan prefix sum'ni saqlaydi.
  5. need = total - kni hisoblang — bu, agar oldingi biror pozitsiya shu qiymatga ega bo'lganida, o'sha pozitsiya bilan hozirgi orasidagi hamma narsa aynan k'ga teng bo'lishi uchun kerak bo'lgan prefix sum.
  6. needni seendan qidiring. Agar u u yerda bo'lsa, uning count'ini countga qo'shing — har bir uchrash mos keluvchi subarray boshlanadigan boshqa-boshqa oldingi pozitsiyani bildiradi.
  7. Faqat shundan keyin, qidiruvdan so'ng, hozirgi totalni map'ga yozing: seen[total] = seen.get(total, 0) + 1. Buni qidiruvdan keyin — oldin emas — bajarish hozirgi pozitsiyaning o'z-o'ziga mos kelib qolishining oldini oladi.
  8. Loop tugagach, count aynan k'ga teng bo'lgan subarray'larning jami sonini saqlaydi.

Complexity

Time: O(n). The array is scanned once, and each iteration does a constant amount of work — one addition, one subtraction, and two hash map operations (a lookup and an insert/update), both O(1) on average for a Python dict. There's no nested loop re-scanning earlier positions, so the total work scales linearly with the length of the array.

Space: O(n). The hash map can end up holding one entry per distinct prefix sum encountered. In the worst case — for example, when every prefix sum along the way is different, which happens whenever the array is all positive numbers — that's up to n+1 entries (n array positions plus the seeded 0), so memory use grows linearly with the size of the input.

Murakkablik

Vaqt: O(n). Array bir marta skanerlanadi, va har bir iteratsiya doimiy miqdordagi ish bajaradi — bitta qo'shish, bitta ayirish, va ikkita hash map amali (bitta lookup va bitta insert/update), Python dict uchun ikkalasi ham o'rtacha O(1). Oldingi pozitsiyalarni qayta skanerlaydigan nested loop yo'q, shuning uchun jami ish array uzunligiga chiziqli proportsional bo'ladi.

Xotira: O(n). Hash map, uchragan har bir alohida prefix sum uchun bitta yozuv saqlashi mumkin. Eng yomon holatda — masalan, yo'l davomidagi barcha prefix sum'lar har xil bo'lsa, bu array to'liq musbat sonlardan iborat bo'lganda sodir bo'ladi — bu n+1 tagacha yozuv bo'lishi mumkin (n ta array pozitsiyasi va urug'langan 0), shuning uchun xotira sarfi kirish o'lchamiga chiziqli proportsional o'sadi.

Common Mistakes

  • Forgetting to seed the map with {0: 1}. Starting seen empty misses every subarray that begins at index 0, because there's no earlier "0" prefix recorded for total - k to match against when the subarray's true starting point is the very beginning of the array. Fix: always initialize seen = {0: 1} before the loop.
  • Updating the map with the current total before doing the lookup, instead of after. Fix: look up need first, then insert the current total — otherwise, whenever k == 0, the current position's freshly-inserted total is already in seen by the time it checks itself, so the position matches against itself and reports a subarray that doesn't actually exist (e.g. nums = [1], k = 0 would wrongly report one match).
  • Storing seen prefix sums in a plain set instead of a count map. Fix: use a dict of counts (or Counter / defaultdict(int)), not a set — with negative numbers in the array, the exact same prefix sum can legitimately occur at several different earlier positions, and each occurrence is a separate valid subarray; a set would only remember that the value was seen, not how many times.
  • Computing need backwards, e.g. k - total instead of total - k. Fix: the earlier prefix sum you're hunting for is total - k, because you want total - earlier == k, which rearranges to earlier == total - k — not the other way around; swapping the subtraction silently returns wrong counts instead of raising any error.

Ko'p Uchraydigan Xatolar

  • Map'ni {0: 1} bilan urug'lantirishni unutish. seenni bo'sh boshlash index 0'dan boshlanadigan har qanday subarray'ni o'tkazib yuboradi, chunki subarray'ning haqiqiy boshlanish nuqtasi array boshi bo'lganda, total - k mos kelishi uchun oldindan yozilgan "0" prefix mavjud emas. Yechim: loop'dan oldin har doim seen = {0: 1} bilan boshlang.
  • Qidiruvni bajarishdan oldin hozirgi totalni map'ga yozish, keyin emas. Yechim: avval needni qidiring, keyin hozirgi totalni qo'shing — aks holda, k == 0 bo'lganda, hozirgi pozitsiyaning yangi yozilgan totali u o'zini tekshirganida allaqachon seenda bo'ladi, shuning uchun pozitsiya o'z-o'ziga mos kelib, aslida mavjud bo'lmagan subarray'ni xabar qiladi (masalan, nums = [1], k = 0 uchun noto'g'ri bitta moslik topiladi).
  • Ko'rilgan prefix sum'larni oddiy set'da saqlash, count map o'rniga. Yechim: set emas, count'lar dict'idan (yoki Counter / defaultdict(int)) foydalaning — array'da manfiy sonlar bo'lsa, aynan bir xil prefix sum bir necha xil oldingi pozitsiyada qonuniy ravishda uchrashi mumkin, va har bir uchrash alohida haqiqiy subarray; set esa faqat qiymat ko'rilganini eslaydi, necha marta ko'rilganini emas.
  • needni teskari hisoblash, masalan total - k o'rniga k - total. Yechim: siz qidirayotgan oldingi prefix sum — total - k, chunki sizga total - earlier == k kerak, bu esa earlier == total - kga aylanadi — aksincha emas; ayirishni almashtirish hech qanday xato chiqarmasdan, shunchaki noto'g'ri sonlarni qaytaradi.

When to Use It

  • The problem talks about contiguous subarrays (not subsequences — order and adjacency matter) and asks for a sum, a count of subarrays hitting a target sum, or some property of the total between two points.
  • The array can contain negative numbers or zero. Sliding window's usual trick — shrink the window whenever the running total gets too big — breaks down when adding an element can make the total go down instead of up; prefix sum plus hash map doesn't care about sign at all.
  • You need to answer many "does some subarray sum to X" questions, or count how many subarrays satisfy a sum condition, faster than the O(n²) of checking every subarray directly.
  • The problem reduces to a running-total lookup even if it isn't phrased as one — e.g. "longest subarray with equal 0s and 1s" (treat every 0 as -1, then look for a repeated prefix sum of 0), or "subarray sum divisible by k" (store prefix sums modulo k instead of raw totals). Same pattern, different bucket.

Qachon Ishlatish Kerak

  • Masala contiguous subarray'lar haqida gapiradi (subsequence emas — tartib va qo'shnilik muhim) va yig'indini, target yig'indiga teng subarray'lar sonini, yoki ikki nuqta orasidagi total haqidagi biror xususiyatni so'raydi.
  • Array manfiy sonlar yoki nolni o'z ichiga olishi mumkin. Sliding window'ning odatdagi hiylasi — running total juda katta bo'lganda window'ni qisqartirish — buzilib qoladi, chunki element qo'shish totalni oshirish o'rniga pasaytirishi ham mumkin; prefix sum + hash map esa ishorani umuman hisobga olmaydi.
  • Sizga "biror subarray X'ga teng yig'indiga egami" degan ko'plab savollarga javob berish, yoki yig'indi shartini qanoatlantiruvchi subarray'lar sonini sanash kerak — har bir subarray'ni to'g'ridan-to'g'ri tekshirishning O(n²) murakkabligidan tezroq.
  • Masala to'g'ridan-to'g'ri shunday aytilmagan bo'lsa ham running-total lookup'ga tushadi: masalan, "0 va 1 soni teng bo'lgan eng uzun subarray" (har bir 0'ni -1 deb hisoblang, keyin takrorlangan prefix sum 0'ni qidiring), yoki "k'ga bo'linadigan subarray sum" (xom totallar o'rniga totallarni k'ga bo'lgandagi qoldiqni saqlang). Bir xil pattern, boshqa bucket.

LeetCode Practice

560. Subarray Sum Equals K ↗

Restated: given an integer array nums and an integer k, return the number of contiguous subarrays whose elements sum to exactly k.

  1. Spot the shape. Brute force checks every one of the O(n²) subarrays and sums each one directly — at least O(n²), or O(n³) if each sum is recomputed from scratch rather than extended from the last. "Count subarrays with sum equal to k," on an array that may contain negative numbers, is exactly the signal for prefix sum.
  2. Build the prefix-sum idea first (even though the final code won't store a whole array of it). Define prefix[i] as the sum of nums[0..i-1]. Any subarray nums[i..j-1] then has sum prefix[j] - prefix[i] — one subtraction instead of re-summing.
  3. Turn the pair search into a lookup. For each ending index j, the number of valid starting points is the number of earlier indices i where prefix[i] == prefix[j] - k. Checking every i for every j is still O(n²); storing counts of prefix values seen so far in a hash map turns that inner search into an O(1) lookup.
  4. Collapse the array into a single running variable. Since only the current prefix sum is ever needed at each step — not the whole history — a single variable total replaces prefix[], updated as the array is scanned.
  5. Handle the edge case. Seed the map with {0: 1} before scanning, so subarrays starting at index 0 are counted correctly, and update the map only after the lookup at each step, so a subarray never matches itself.
def subarraySum(nums, k):
    # count: number of subarrays found so far that sum to exactly k
    # total: running prefix sum -- sum of nums[0..i] at the current index i
    count, total = 0, 0

    # seen maps a prefix-sum value to how many earlier indices produced it
    # seed with {0: 1}: the "empty" prefix (before index 0) sums to 0,
    # so subarrays starting at index 0 can be counted too
    seen = {0: 1}

    for num in nums:
        total += num

        # an earlier prefix sum equal to (total - k) means everything
        # between that earlier position and here sums to exactly k
        need = total - k
        count += seen.get(need, 0)

        # record the current total only AFTER the lookup above, so this
        # position never counts itself as a match when k == 0
        seen[total] = seen.get(total, 0) + 1

    return count

LeetCode Amaliyoti

560. Subarray Sum Equals K ↗

Qayta bayon: butun sonlardan iborat nums array va butun son k berilgan — elementlari yig'indisi aynan kga teng bo'lgan contiguous subarray'lar sonini qaytaring.

  1. Shaklni tanib oling. Brute force O(n²) ta subarray'ning har birini tekshirib, har birini to'g'ridan-to'g'ri yig'adi — bu kamida O(n²) (agar har bir yig'indi oldingisidan davom ettirilmasdan qaytadan hisoblansa, O(n³)). "Yig'indisi k'ga teng subarray'lar sonini sanash", va manfiy sonlar bo'lishi mumkin bo'lgan array — bu aynan prefix sum'ni ishora qiluvchi belgi.
  2. Avval prefix-sum g'oyasini quring (garchi yakuniy kodda uni to'liq array sifatida saqlamasa ham). prefix[i]ni nums[0..i-1]ning yig'indisi deb belgilang. Har qanday subarray nums[i..j-1]ning yig'indisi endi bitta ayirish bo'ladi: prefix[j] - prefix[i].
  3. Juftlik qidiruvini lookup'ga aylantiring. Har bir tugash indeksi j uchun, to'g'ri boshlanish nuqtalari soni — prefix[i] == prefix[j] - k bo'lgan oldingi i indekslarining soni. Har bir j uchun har bir ini tekshirish hali ham O(n²); hozirgacha ko'rilgan prefix qiymatlarning count'ini hash map'da saqlash bu ichki qidiruvni O(1) lookup'ga aylantiradi.
  4. Array'ni bitta running o'zgaruvchiga siqing. Chunki har bir qadamda faqat hozirgi prefix sum kerak (butun tarix array emas), prefix[] o'rniga bitta total o'zgaruvchisi ishlatiladi, array skanerlanayotganda yangilanib boradi.
  5. Chekka holatni hal qiling. Skanerlashdan oldin map'ni {0: 1} bilan urug'lantiring, shunda index 0'dan boshlanadigan subarray'lar to'g'ri sanaladi, va map'ni har bir qadamda faqat lookup'dan keyin yangilang, shunda subarray hech qachon o'z-o'ziga mos kelmaydi.
def subarraySum(nums, k):
    # count: number of subarrays found so far that sum to exactly k
    # total: running prefix sum -- sum of nums[0..i] at the current index i
    count, total = 0, 0

    # seen maps a prefix-sum value to how many earlier indices produced it
    # seed with {0: 1}: the "empty" prefix (before index 0) sums to 0,
    # so subarrays starting at index 0 can be counted too
    seen = {0: 1}

    for num in nums:
        total += num

        # an earlier prefix sum equal to (total - k) means everything
        # between that earlier position and here sums to exactly k
        need = total - k
        count += seen.get(need, 0)

        # record the current total only AFTER the lookup above, so this
        # position never counts itself as a match when k == 0
        seen[total] = seen.get(total, 0) + 1

    return count

Check Yourself

O'zingizni Sinang

© 2026 Davronbek