# Array

## Overview
Array adalah struktur data yang menyimpan elemen-elemen bertipe sama. Tiap elemen dapat diakses menggunakan indeks. Ukuran array konstan, tidak berubah sejak diinisalisasi.

## Visualisasi
Array 1D

// 1D array size 10
T[] arr1d = new T[10];


Array 2D

// 2D array size 3x10
T[][] arr2d = new T[3][10];


Array berdimensi lebih dari 2 agak sulit divisualisasikan seperti tabel. Salah satu cara mudah membayangkannya adalah array berisi array berisi array dst.

Note:
- `T` adalah placeholder untuk sebuah tipe.
- Angka-angka yang ada menunjukkan indeks elemen.

## Terms

### Elemen
Sebuah value yang disimpan pada array

### Indeks
Angka yang digunakan untuk mengakses elemen array

### Referring to element
$a_i$ : elemen pada 1D array $a$ indeks $i$ (`a[i]`)
$a_{ij}$ : elemen pada 2D array $a$ indeks $i,j$ (`a[i][j]`)
$a_{ijk}$ : elemen pada 3D array $a$ indeks $i,j,k$ (`a[i][j][k]`)

### Iterasi
Mengakses elemen-elemen pada array satu per satu, biasanya secara berurutan atau mengikuti pola tertentu.

## Good to Know

### Modulo pada indeks
Pada 1D array $a$ dengan size $n$, mengakses elemen pada indeks $i \bmod n$ ($a_{i \bmod n}$) secara berurutan untuk $i = 0,1,2,...$ akan sama seperti mengakses indeks untuk $i = 0,1,...,n-1,0,1,...,n-1,0,1,...$ Dapat dilihat bahwa mengakses indeks untuk $i$ seperti itu adalah mengakses $a$ secara sirkular/memutar.

Contohnya,

int[] arr = {3, 1, 4, 2};
int idx = 0;

// infinitely iterate array
while(true){
    System.out.print(arr[idx % arr.length] + " ");
}

akan memberikan output berupa

3 1 4 2 3 1 4 2 3 1 4 2 3 1 ...

### Konversi urutan menjadi indeks (dan sebaliknya)
Pada 2D array $a$ dengan size $n \times m$ ($n$ baris, $m$ kolom), urutan elemen ke-$x$ dapat diubah menjadi indeks baris $i$ dan kolom $j$ menggunakan rumus:
$i = \lfloor \frac xm \rfloor$
$j = x \bmod m$

Sebaliknya, $x$ dapat diperoleh dari $i$ dan $j$ menggunakan rumus:
$x = i \times m + j$

Contohnya,

int n = 4;
int m = 3;

// elemen array sekaligus menunjukkan urutan
int[][] arr = {{0, 1, 2},
               {3, 4, 5},
               {6, 7, 8},
               {9, 10, 11}};

// indeks pada urutan ke-7
System.out.println("Indeks pada urutan ke-7:");
System.out.println("i: " + (7 / m));
System.out.println("j: " + (7 % m));

System.out.println()

// indeks pada urutan ke-11
System.out.println("Indeks pada urutan ke-11:");
System.out.println("i: " + (11 / m));
System.out.println("j: " + (11 % m));

System.out.println()

// urutan pada indeks 3,2
System.out.println("Urutan pada indeks 3,2: " + (3 * m + 2));

System.out.println()

// urutan pada indeks 0,1
System.out.println("Urutan pada indeks 0,1: " + (0 * m + 1));

akan memberikan output berupa

Indeks pada urutan ke-7:
i: 2
j: 1

Indeks pada urutan ke-11:
i: 3
j: 2

Urutan pada indeks 3,2: 11

Urutan pada indeks 0,1: 1

### Frequency Array
Frequency Array adalah salah satu bentuk array untuk menyimpan kemunculan suatu elemen. Untuk kemudahan, elemen yang dibahas adalah sebuah angka.

Kemunculan sebuah angka $i$ disimpan di $a_i$. Perhatikan bahwa yang disimpan ($a_i$) adalah kemunculan dari angka tersebut ($i$), angka tersebut sendiri menjadi indeks yang digunakan untuk mengakses kemunculannya.

Misalnya,
$a_2 = 3$ berarti angka $2$ muncul sebanyak $3$ kali.
$a_1 = 4$ berarti angka $1$ muncul sebanyak $4$ kali.

Code

int[] nums = {2, 3, 1, 2, 3, 3, 1, 3, 2, 4};
int[] freq = new int[5];

// iterate nums
for(int i = 0; i < nums.length; i++){
    // increment frequency
    freq[nums[i]]++;
}

// print nums
System.out.println(Arrays.toString(nums));

// iterate freq
for(int i = 0; i < freq.length; i++){
    // print frequency
    System.out.println(i + " muncul sebanyak " + freq[i] + " kali");
}

akan memberikan output berupa

[2, 3, 1, 2, 3, 3, 1, 3, 2, 4]
0 muncul sebanyak 0 kali
1 muncul sebanyak 2 kali
2 muncul sebanyak 3 kali
3 muncul sebanyak 4 kali
4 muncul sebanyak 1 kali

### Menentukan ada tidaknya elemen di array
Cara mudahnya adalah menggunakan linear search, yaitu mengiterasi seluruh elemen di array. Untuk tiap iterasi, cek apakah elemen tersebut adalah elemen yang dicari. Perhatikan bahwa jika elemen pada suatu iterasi bukan elemen yang dicari, **belum tentu** elemen yang dicari tidak ada di array. Bisa saja elemen yang dicari ada di indeks-indeks selanjutnya. Kita baru bisa mengambil kesimpulan bahwa sebuah elemen tidak ada di array **setelah** mengiterasi array.

## Examples
Berikut beberapa contoh problem yang dapat diselesaikan menggunakan array.

### Input Output Array
Diberikan input berupa ukuran array dan elemen-elemennya, simpan elemen-elemen tersebut ke sebuah array kemudian outputkan kembali elemen-elemen array tersebut.

Pertama, ambil input ukuran array dan buat inisialisasi arraynya.

Scanner in = new Scanner(System.in);

int n = in.nextInt();
int[] arr = new int[n];

Kemudian ambil input elemen-elemennya dan dimasukkan ke array yang telah dibuat.

for(int i = 0; i < n; i++){
    arr[i] = in.nextInt();
}

Outputkan kembali elemen-elemen array tersebut.

for(int i = 0; i < n; i++){
    System.out.println(arr[i] + " ");
}

### Sum of Elements
Diberikan input berupa ukuran array dan elemen-elemennya, outputkan jumlah dari semua elemen tersebut.

Ambil input.

Scanner in = new Scanner(System.in);

int n = in.nextInt();
int[] arr = new int[n];

for(int i = 0; i < n; i++){
    arr[i] = in.nextInt();
}

Iterasi di array untuk menjumlahkan elemen-elemennya. Gunakan sebuah variable untuk mengakumulasi jumlah elemen, dalam contoh ini variable `sum`.

int sum = 0;

for(int i = 0; i < arr.length; i++){
    sum += arr[i];
}

System.out.println(sum);

### Factorial
Diberikan input sebuah angka $n$, outputkan $0!$ hingga $n!$

Ambil input dan inisialisasi array untuk menyimpan nilai faktorial.

Scanner in = new Scanner(System.in);

int n = in.nextInt();
int[] fact = new int[n];

Nilai $n!$ dapat diperoleh dengan rumus $n! = n * (n-1)!$, dengan $0! = 1$

fact[0] = 1;

for(int i = 1; i < 8; i++){
    // n! = n * (n - 1)!
    fact[i] = i * fact[i - 1];
}

for(int i = 0; i <= n; i++){
    System.out.println(fact[i]);
}

### Modus Terbesar
Diberikan input berupa ukuran array dan elemen-elemennya, outputkan modus terbesar dari array tersebut, yaitu elemen terbesar dengan kemunculan terbanyak.

Ambil input.

Scanner in = new Scanner(System.in);

int n = in.nextInt();
int[] arr = new int[n];

for(int i = 0; i < n; i++){
    arr[i] = in.nextInt();
}

Buat sebuah frequency array untuk menyimpan kemunculan sebuah elemen. Untuk kemudahan, asumsikan semua elemen berada pada rentang `[0, 100]`[^1].

[^1]: Untuk rentang elemen secara umum atau tipe elemen selain integer dapat menggunakan Hash Map.

int[] freq = new int[101];

Iterasi di array input untuk menghitung kemunculan tiap elemen.

for(int i = 0; i < n; i++){
    freq[arr[i]]++;
}

Iterasi di frequency array untuk mencari berapa kemunculan terbanyak. Gunakan sebuah variabel untuk menyimpan kemunculan terbanyak, pada contoh ini variable `modus`

int modus = 0;
for(int i = 0; i < freq.length; i++){
    if(freq[i] > modus) modus = freq[i];
    
    // dapat pula menggunakan Math.max()
    // modus = Math.max(freq[i], modus);
}

Kita telah mendapatkan kemunculan terbanyak yang disimpan di variable `modus`, tetapi yang diminta adalah elemen terbesar dengan kemunculan sebanyak `modus`. Kita dapat mengiterasi sekali lagi untuk mencari elemen tersebut. Iterasi dapat dilakukan di array input maupun frequency array. Gunakan sebuah variable untuk menyimpan elemen terbesar, dalam contoh ini variable `modusTerbesar`.

Iterasi di array input

int modusTerbesar = 0;
for(int i = 0; i < n; i++){
    // cek apakah arr[i] memiliki kemunculan yang paling banyak
    if(freq[arr[i]] == modus){
        // simpan elemen yang terbesar antara arr[i] dan modusTerbesar
        if(arr[i] > modusTerbesar){
            modusTerbesar = arr[i];
        }
        
        // dapat pula menggunakan Math.max()
        // modusTerbesar = Math.max(arr[i], modusTerbesar);
    }
}

Iterasi di frequency array. Ingat kembali bahwa pada frequency array, indeks `i` merepresentasikan elemen dan `freq[i]` merepresentasikan kemunculan elemen `i` tersebut.

int modusTerbesar = 0;
for(int i = 0; i < freq.length; i++){
    // cek apakah i memiliki kemunculan yang paling banyak
    if(freq[i] == modus){
        
        // simpan elemen yang terbesar antara i dan modusTerbesar
        if(i > modusTerbesar){
            modusTerbesar = i
        }
    }
}

Iterasi manapun yang dipilih akan memberikan hasil yang sama, yaitu modus terbesar yang disimpan pada variable `modusTerbesar`.

Pada contoh ini terdapat 4 kali penggunaan `for` loop, yaitu:
1. Input array
2. Menghitung frekuensi
3. Mencari frekuensi terbanyak
4. Mencari elemen terbesar dengan frekuensi terbanyak

Setelah Anda semakin familiar dengan array, cobalah untuk menyelesaikan kembali contoh problem ini dengan menggunakan 1 (satu) buah `for` loop!

### Matriks Simetris
Diberikan sebuah matriks berukuran $n \times n$, tentukan apakah matriks tersebut simetris atau tidak.

Ambil input. Kita dapat menggunakan 2D array untuk merepresentasikan sebuah matriks.

Scanner in = new Scanner(System.in);

int n = in.nextInt();
int[][] arr = new int[n][n];

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        arr[i][j] = in.nextInt();
    }
}

Iterasi di array untuk menentukan simetris atau tidak. Sebuah matriks $A$ dikatakan simetris jika elemen $A_{ij}$ sama dengan elemen $A_{ji}$. Gunakan sebuah variable untuk menyimpan apakah matriks ini simetris, pada contoh ini variable `simetris`[^2].

// asumsi awal: matriksnya simetris
boolean simetris = true;

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        // asumsi awal salah: matriks tidak simetris
        if(arr[i][j] != arr[j][i]) simetris = false;
    }
}

if(simetris) System.out.println("Matriks simetris");
else System.out.println("Matriks tidak simetris");

[^2]: Variable boolean yang digunakan sebagai penanda valid/tidaknya sesuatu seringkali disebut sebagai 'flag'.