Tömb alapok | Interview Tudásbázis

A tömb az algoritmikus gondolkodás egyik legfontosabb belépőpontja: fix méretű, összefüggő memóriában él, indexvezérelt, és rengeteg LeetCode-minta erre épül rá.

1. Definíció

Mi az a tömb?

A tömb egy fix méretű elemsorozat, ahol az elemek egymás mellett helyezkednek el a memóriában. Ez az elrendezés teszi gyorssá az indexelést, kiszámíthatóvá a bejárást, és drágává a középre történő beszúrást.

Miért létezik?

A tömb azért hasznos, mert sok problémánál kompakt tárolásra és közvetlen pozíció alapú elérésre van szükség. Ha a gép ki tudja számolni az $i$-edik elem helyét, akkor nem kell végigmennie az előző elemeken.

Hová illeszkedik a nagyobb képbe?

A tömb szinte mindig jó első jelölt, ha:

a bemenet eleve lista vagy számsor,
számít a sorrend,
számítanak a pozíciók,
megengedett az in-place módosítás,
vagy a későbbi megoldás two pointers, sliding window, prefix sum, bináris keresés vagy DP irányba nyit.

Intuíció

Képzeld el úgy, mint sorszámozott szekrényeket egy folyosón. Ha a 17-es szekrény kell, nem kell végignézni a 0-tól 16-ig mindent. Oda lehet ugrani közvetlenül, mert a helye kiszámítható. Ezért O(1) az indexelés.

Java kontextus

Java-ban a tömb objektum. A heapen él, fix length értéke van, ismeri a runtime komponens típusát, és minden hozzáférésnél bounds check fut. Vagyis alacsonyabb szintű, mint a legtöbb collection, de még mindig biztonságosabb, mint a nyers memóriahasználat.

2. Alapfogalmak

2.1 Összefüggő memória

A tömb lényege az összefüggő tárolás. Elméletben, ha az első elem egy ismert helyen kezdődik és az elemek mérete ismert, akkor az i indexű elem helye így írható le:

$$ \text{address}(i) = \text{base} + i \cdot \text{elementSize} $$

Java-ban nem címekkel dolgozol, de ez a modell jól magyarázza a teljesítményt.

2.2 Fix méret

A tömb mérete létrehozás után nem változtatható.

int[] scores = new int[5];
System.out.println(scores.length); // 5

Ha nagyobb kapacitás kell, új tömböt kell létrehozni és az adatokat át kell másolni. Ez a fő oka annak, hogy létezik például az ArrayList.

2.3 Zero-based indexing

A tömb indexelése nulla alapú:

első elem → 0
második elem → 1
utolsó elem → length - 1

Ez egyszerű szabály, mégis rengeteg interjúhiba off-by-one probléma.

2.4 Időkomplexitás

Művelet	Komplexitás	Miért
Olvasás index alapján	`O(1)`	Direkt ugrás
Írás index alapján	`O(1)`	Direkt felülírás
Teljes bejárás	`O(n)`	Minden elemet nézni kell
Keresés rendezetlen tömbben	`O(n)`	Lehet, hogy minden elemet nézni kell
Középre beszúrás	`O(n)`	Az utána jövő elemek tolódnak
Középről törlés	`O(n)`	Az utána jövő elemek tolódnak

2.5 Térkomplexitás

Ha a bemeneti tömb már adott és csak néhány segédváltozót használsz, az extra space O(1). Ha létrehozol egy új, n méretű tömböt, az extra space O(n). Interjúkon ez fontos, mert két hasonló időkomplexitású megoldás memóriaigénye nagyon eltérő lehet.

2.6 In-place módosítás

Az in-place megoldás a meglévő tömbön dolgozik, és nem allokál egy másik teljes struktúrát.

import java.util.Arrays;

int[] nums = {1, 2, 3};
nums[1] = 99;
System.out.println(Arrays.toString(nums)); // [1, 99, 3]

Ennek előnyei:

kisebb memóriahasználat,
kevesebb allokáció,
gyakran jobb cache behavior,
interjún tisztább complexity-kép.

A veszélye pedig az, hogy felülírhatsz olyan adatot, amire később még szükség lenne.

2.7 Gyakori iterációs minták

A tömbök néhány visszatérő mozgásmintában jelennek meg:

balról jobbra scan,
jobbról balra scan,
két pointer befelé mozog,
fast/slow pointer,
read pointer + write pointer,
nested loop párokhoz,
prefix accumulation,
window bővítés és szűkítés.

Ez a téma az alapoknál marad, de minden későbbi minta innen indul.

2.8 Java tömbök alapértelmezett értékei

Java automatikusan inicializálja a tömb elemeit.

Típus	Alapérték
`int[]`	`0`
`long[]`	`0L`
`double[]`	`0.0`
`boolean[]`	`false`
`char[]`	`\u0000`
`String[]`	`null`
`Object[]`	`null`

Ez kényelmes, de hibaforrás is lehet. A 0 jelentheti azt is, hogy „nincs beállítva”, és azt is, hogy tényleges érték.

2.9 Tömb vs `ArrayList`

Interjúkon sokszor keveredik a nyers tömb és az ArrayList.

Tulajdonság	Tömb	`ArrayList`
Méret	Fix	Méretezhető
Primitívek tárolása	Igen	Nem
Indexelés	`O(1)`	`O(1)`
Memória overhead	Alacsonyabb	Magasabb
Generics	Nincs	Van
Algoritmus sablonokhoz	Gyakran	Néha

2.10 Felismerési jelek

A „tömbgondolkodásnak” gyorsan be kell kapcsolnia, ha:

a bemenet értéklista,
számítanak a pozíciók,
fontos a sorrend,
szerepel a feladatban: subarray, range, adjacent, prefix, sorted,
vagy valószínűnek tűnik egy egy- vagy kétpasszos megoldás.

2.11 Az invariáns korai szerepe

Egy jó tömbös megoldás ritkán „csak egy ciklus”. Többnyire van benne valamilyen invariáns, például:

left és right közé esik a még megoldatlan tartomány,
a write a következő megtartott pozíciót jelöli,
a prefix[i] az első i elemről hordoz információt,
vagy a currentMax az eddig látott részt foglalja össze.

Ha az invariánst ki tudod mondani, sokkal könnyebb helyesen gondolkodni és review-zni.

3. Gyakorlati használat

Mikor használd?

A tömb jó választás, ha:

előre ismert a méret,
fontos a teljesítmény,
indexvezérelt a logika,
kicsi overhead kell,
fontosak a primitív értékek,
vagy interjúmegoldásként tömör, jól átadható kódot szeretnél.

Tipikus példák:

összegzés,
minimum vagy maximum keresése,
in-place megfordítás,
nullák mozgatása,
duplikátumok eltávolítása rendezett inputból,
forgatás,
gyakoriságszámlálás kis fix tartományban.

Mikor különösen jó LeetCode-ban?

Nagy constraintnél a tömb nagyon erős. Ha n mérete 10^5 vagy 10^6, már egyetlen lineáris bejárás is kifejezetten jó megoldás lehet. Ez pont az a gondolkodás, amit interjún is szeretnek hallani.

Mikor ne nyers tömböt használj?

Gyengébb választás, ha:

folyamatosan változik a méret,
kulcs alapú lookup kell,
gyakran kell középre beszúrni,
rendezett kulcsnavigáció kell,
vagy a collection API annyival tisztább, hogy megéri a plusz overheadet.

Ilyenkor inkább szóba jöhet ArrayList, HashMap, Deque, TreeMap vagy más struktúra.

Java-specifikus iránymutatás

A tömböt válaszd inkább, ha:

algoritmusfeladatot oldasz,
primitívekkel dolgozol,
segédtömböt építesz, például prefix, visited, dp vagy count célra,
fontos a tömör és gyors megoldás.

Az ArrayList jobb lehet, ha:

nem ismert a végleges elemszám,
kell a méretezhetőség,
vagy a collection API olvashatóbb megoldást ad.

Pair-programming nézőpont

A tömbös megoldások jól verbalizálhatók. Jó mondatok például:

„Balról jobbra scannelek.”
„Fenntartok egy futó maximumot.”
„Lesz egy read pointer és egy write pointer.”
„Ez in-place marad, tehát az extra space O(1).”

Ez a fajta narráció pair programmingban és interjún is azt mutatja, hogy nem csak kódolsz, hanem vezeted is a megoldást.

Gyakorlati checklist kódolás előtt

Mielőtt véglegesítesz egy tömbös megoldást, kérdezd meg:

Fontos az eredeti sorrend?
Módosítható az input?
Belefér plusz memória?
Rendezett az input?
Ez valóban scan-probléma?
Mi az az invariáns, amit végig fent tudok tartani?

Gyakori kezdeti transzformációk

Sok erősebb megoldás ilyen lépéssel indul:

előbb rendezés,
prefix tömb építése,
értékszámlálás,
in-place tömörítés,
suffix megfordítás,
bal/jobb oldali információk előfeldolgozása.

Ezek nem teljesen külön világok, hanem a stabil tömbalapok természetes folytatásai.

4. Kódpéldák

Alap példa — bejárás és aggregáció

import java.util.Arrays;

public class ArraySumExample {
    public static int sum(int[] nums) {
        int total = 0;
        for (int value : nums) {
            total += value;
        }
        return total;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 7, 2};
        System.out.println(sum(nums)); // 14
        System.out.println(Arrays.toString(nums)); // [4, 1, 7, 2]
    }
}

Ez a legalapvetőbb és leggyakrabban újrahasznosítható tömbös minta: egy bejárás, O(n) idő, O(1) extra space.

Alap példa — közvetlen módosítás

import java.util.Arrays;

public class ArrayUpdateExample {
    public static void main(String[] args) {
        int[] scores = {10, 20, 30, 40};
        scores[2] = 99;
        System.out.println(Arrays.toString(scores));
    }
}

Ez rövid példa, de jól mutatja a tömb közvetlen írási erejét.

Haladó példa — megfordítás in-place

import java.util.Arrays;

public class ReverseArrayExample {
    public static void reverse(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        reverse(nums);
        System.out.println(Arrays.toString(nums)); // [5, 4, 3, 2, 1]
    }
}

Mit tanít ez?

a tömb jól működik pointer-alapú mozgással,
nem kell második tömb,
az extra space O(1) marad.

Haladó példa — duplikátumok eltávolítása rendezett tömbből

import java.util.Arrays;

public class RemoveDuplicatesExample {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int write = 1;
        for (int read = 1; read < nums.length; read++) {
            if (nums[read] != nums[read - 1]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 2, 3, 4, 4};
        int length = removeDuplicates(nums);
        System.out.println(length); // 4
        System.out.println(Arrays.toString(Arrays.copyOf(nums, length))); // [1, 2, 3, 4]
    }
}

Ez klasszikus interjúpélda, mert a „tömb alapok” témát read/write pointer fegyelemmé emeli.

Gyakori hiba — off-by-one

public class OffByOneExample {
    public static int lastElement(int[] nums) {
        return nums[nums.length - 1];
    }
}

Gyakori rossz verzió:

// ❌ Out of bounds
int value = nums[nums.length];

Ennek oka egyszerű:

a length az elemszám,
az utolsó érvényes index length - 1.

Gyakori hiba — nem biztonságos szomszédelérés

public class NeighborCheckExample {
    public static boolean hasEqualNeighbors(int[] nums, int index) {
        if (index < 0 || index >= nums.length - 1) {
            return false;
        }
        return nums[index] == nums[index + 1];
    }
}

Kicsi példa, de valóságos: jól mutatja, miért fontos a boundary-gondolkodás.

Review-szintű magyarázat

A removeDuplicates példánál egy erős magyarázat így hangzik:

a tömb rendezett,
a read végignézi az elemeket,
a write mutatja, hová kerül a következő megtartott érték,
write előtt mindig a már letisztított prefix áll,
és a visszaadott hossz mondja meg, meddig érvényes az eredmény.

Ez egyszerre algoritmikus gondolkodás és jó pair-programming kommunikáció.

5. Trade-offok

Szempont	Részletek
⚡ Performance	Indexeléshez és lineáris bejáráshoz kiváló, de gyakori középső beszúrásra és törlésre gyenge az elemtolás miatt.
💾 Memory	Primitíveknél nagyon kompakt, általában leanebb, mint a collection-alapú alternatívák.
🔧 Maintainability	Egyszerű modell, de az indexintenzív logika gyorsan törékennyé válik, ha az invariáns nincs jól kimondva.
🔄 Flexibility	Kicsi rugalmasság, mert fix méretű; bővítéshez új allokáció és másolás kell.

Performance trade-off egyszerűen

A tömb akkor gyors, ha kiszámíthatóan haladsz rajta végig. Nem csodafegyver. Akkor lesz rossz választás, ha a workload a közepe körül állandóan át akarja rendezni az adatot.

Memória trade-off

Egy int[] jellemzően olcsóbb, mint egy List<Integer>, mert a lista boxingot és objektum overheadet hozhat be. Algoritmusfeladatoknál ez komoly különbség lehet.

Egyszerűség trade-off

A tömb elsőre egyszerű, de a több pointeres megoldások könnyen törékenyek lesznek. A jó változónevek, például left, right, read, write, prefix vagy currentMax, sokat segítenek.

Biztonsági trade-off

A Java tömb bounds checkkel védett, ezért biztonságosabb, mint a nyers memóriahasználat. Ez jó a korrektségnek, de azt is jelenti, hogy a pontatlan indexelés gyorsan hibára fut.

Interjús trade-off

Néha egy nem tömbös megoldás elméletben szebb, mégis a tömb nyer, mert:

egyszerűbb elmagyarázni,
kevesebb memóriát kér,
és átláthatóbb a teljesítménymodellje.

Egy erős jelölt ezt a trade-offot is ki tudja mondani.

6. Gyakori hibák

A length összekeverése az utolsó indexszel
A jelölt nums[nums.length] formát ír nums[nums.length - 1] helyett. A jó mentális modell az, hogy az érvényes indexek 0-tól length - 1-ig tartanak.
Az üres tömb kihagyása mint edge case
Ha a kód feltételezi, hogy létezik nums[0], az üres input rögtön hibát okozhat.
Szükséges adat felülírása in-place módosításnál
Az in-place memóriahatékony, de rossz pointerstratégiával túl korán elveszhet egy még szükséges érték.
Túl korai nested loop használat
Sok kezdő rögtön O(n^2) megoldáshoz nyúl, mielőtt megvizsgálná, hogy elég-e egy scan vagy egy egyszerű transzformáció.
Gyenge névadás indexelt logikánál
Ha minden változó csak i, j, k, az invariáns könnyen elveszik. A szerepalapú nevek stabilabb gondolkodást adnak.
A rendezett input előnyének ignorálása
A rendezett tömb sokszor jelzés a jobb minták felé: two pointers, bináris keresés, duplikátumtömörítés.
A tömb és az ArrayList viselkedésének összekeverése
A tömb nem méreteződik automatikusan. Ha nagyobb kapacitás kell, új tömböt kell létrehozni.
Az invariáns ki nem mondása
A kód még működhet, de ha nem tudod megfogalmazni, mi marad igaz minden lépés után, akkor a debug és a review is sokkal nehezebb.

7. Mélyebb összefüggések

Hogyan gondolkodik erről egy tapasztalt fejlesztő?

A senior szemlélet nem áll meg ott, hogy „a tömb O(1) indexelésű”. Fontos még a memóriaelrendezés, a cache locality, a mutáció költsége, a boxing overhead, és az, hogy milyen későbbi optimalizációs utak nyílnak meg.

A cache locality tényleg számít

A tömb nemcsak aszimptotikusan jó. Valódi futás közben is gyakran gyors, mert a szekvenciális hozzáférés jól illeszkedik a CPU cache működéséhez. Ezért tudnak sokszor az array-alapú struktúrák pointer-heavy alternatívák fölé nőni.

Bounds checking Java-ban

Minden tömbhozzáférés ellenőrzött. Ez a nyelv biztonsági modelljének része. Interjú szempontból ez azt jelenti, hogy a boundary-logikának különösen megbízhatónak kell lennie, főleg left + 1, right - 1 vagy mid jellegű kifejezéseknél.

Primitív tömb vs boxed típus

Az int[] és az Integer[] nagyon eltérő viselkedést ad. A primitív tömb nyers értékeket tárol, a boxed verzió referenciákat objektumokra. Ez hat:

a memóriaigényre,
a cache viselkedésre,
a null lehetőségére,
a futási költségre.

A legtöbb algoritmusfeladatnál a primitív tömb a jobb baseline.

Miért alapoz meg későbbi mintákat?

Szinte minden korai DSA-minta három tömbös készségre épít:

indextudatosság,
invariáns-tudatosság,
edge case tudatosság.

Ha ezek gyengék, a későbbi minták véletlenszerűnek érződnek. Ha erősek, a haladóbb témák természetes folytatásnak tűnnek.

Interjús magyarázatminta

Egy jó magyarázat például így hangzik:

„Az adat az eredeti tömbben marad.”
„Egy passzban oldom meg, ezért az idő O(n).”
„Csak néhány változót használok, így az extra space O(1).”
„A kockázatos rész az első és utolsó index kezelése.”
„Ha rendezett lenne az input, a következő gondolatom a two pointers lenne.”

Ez az a nyugodt, explicit kommunikáció, ami pair programmingban és interjún is erős.

Miért fontos ez a téma önmagán túl?

A tömb nem csak külön témaként fontos. Ez az alapja többek között:

a two pointersnek,
a sliding window-nak,
a prefix sum gondolkodásnak,
a pozíció alapú bináris keresésnek,
sok DP táblának,
és rengeteg frequency helpernek.

Ha a tömbalapok bizonytalanok, sok későbbi téma nehezebbnek tűnik, mint amilyen valójában.

8. Interjúkérdések

Q: Miért O(1) a tömb indexelése?
A: Mert az elem helye közvetlenül kiszámítható a kezdőpozícióból és az indexből, ezért nem kell végigjárni a korábbi elemeket.

Q: Miért O(n) jellemzően a tömb közepére beszúrni?
A: Mert a beszúrás helye utáni elemeket el kell tolni, és ez a mozgás dominálja a költséget.

Q: Mit jelent az, hogy egy megoldás in-place?
A: Azt, hogy az eredeti struktúrán dolgozik, és nem allokál egy másik teljes méretű struktúrát; gyakran O(1) extra space a cél.

Q: Mikor választanál tömböt ArrayList helyett Java-ban?
A: Ha ismert a méret, fontos a primitív teljesítmény, és az indexalapú logika a megoldás központi része.

Q: Melyek az első edge case-ek tömbfeladatnál?
A: Üres input, egyetlen elem, első index, utolsó index, duplikátumok, már rendezett input, minden elem azonos.

Q: Mi egy jó invariáns egy tömörítő tömbalgoritmusnál?
A: Gyakori válasz, hogy write előtt minden elem már a végleges, megtartott formában van, míg read-től jobbra még feldolgozatlan az input.

9. Fogalomtár

Fogalom	Definíció
contiguous memory	Az elemek egymás mellett, kompakt blokkban vannak tárolva.
index	Zero-based pozíció, amellyel elérsz egy elemet.
in-place	Az eredeti struktúra módosítása egy másik teljes méretű struktúra nélkül.
bounds checking	Futásidejű ellenőrzés, hogy az index érvényes tartományban marad-e.
boxing	Primitív érték objektummá csomagolása, például `int` → `Integer`.
cache locality	Teljesítményelőny abból, hogy közeli memóriahelyeket együtt ér el a CPU.
read pointer	Az az index, amelyből éppen olvasol.
write pointer	Az az index, ahová a következő megtartott vagy átalakított értéket írod.
invariant	Olyan feltétel, amely a futás során végig igaz marad és segít a helyesség bizonyításában.

10. Cheatsheet

A tömb fix méretű, összefüggő, indexelhető struktúra.
Index alapú olvasás és írás jellemzően O(1).
A teljes bejárás O(n).
Középre beszúrás és törlés jellemzően O(n) az elemtolás miatt.
Az utolsó érvényes index mindig length - 1.
Az in-place megközelítés gyakran O(1) extra space-et jelent.
Az üres tömb kezelése legyen az első review pontok egyike.
A primitív tömb sokszor jobb, mint a boxed alternatíva algoritmusmunkára.
A rendezett tömb gyakran jobb minták felé nyit utat.
Az invariáns kimondása gyorsítja a review-t, a debugot és az interjús magyarázatot.
A stabil tömbalapok megkönnyítik a későbbi DSA témákat.