# Array

## Array Concepts

### Array

> An `array` is a basic data structure to `store a collection of elements sequentially` . But elements can be `accessed randomly` since each element in the array can be identified by an array `index`.

### Dynamic Array

> ... an array has a fixed capacity and we need to specify the size of the array when we initialize it. Sometimes this will be somewhat inconvenient and wasteful. Most programming languages offer built-in **dynamic array** which is still a random access list data structure but with **variable size**. For example, we have **vector** in C++ and **ArrayList** in Java.

Operations in Dynamic Array

```java
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {

        // 1. initialize
        List<Integer> v0 = new ArrayList<>();
        List<Integer> v1;                           // v1 == null

        // 2. cast an array to a vector
        Integer[] a = {0, 1, 2, 3, 4};
        v1 = new ArrayList<>(Arrays.asList(a));

        // 3. make a copy
        List<Integer> v2 = v1;                      // another reference to v1
        List<Integer> v3 = new ArrayList<>(v1);     // make an actual copy of v1

        // 3. get length
        System.out.println("The size of v1 is: " + v1.size());

        // 4. access element
        System.out.println("The first element in v1 is: " + v1.get(0));

        // 5. iterate the vector
        System.out.print("[Version 1] The contents of v1 are:");
        for (int i = 0; i < v1.size(); ++i) {
            System.out.print(" " + v1.get(i));
        }
        System.out.println();
        System.out.print("[Version 2] The contents of v1 are:");
        for (int item : v1) {
            System.out.print(" " + item);
        }
        System.out.println();

        // 6. modify element
        v2.set(0, 5);       // modify v2 will actually modify v1
        System.out.println("The first element in v1 is: " + v1.get(0));
        v3.set(0, -1);
        System.out.println("The first element in v1 is: " + v1.get(0));

        // 7. sort
        Collections.sort(v1);

        // 8. add new element at the end of the vector
        v1.add(-1);
        v1.add(1, 6);

        // 9. delete the last element
        v1.remove(v1.size() - 1);
    }
}
```

## 2D Array - Matrix

Excepts from LeetCode: <https://leetcode.com/explore/learn/card/array-and-string/202/introduction-to-2d-array/1166/>

> In some languages, the multidimensional array is actually implemented internally as a one-dimensional array while in some other languages, there is actually no multidimensional array at all.

**1. C++ stores the two-dimensional array as a one-dimensional array.**

The picture below shows the actual structure of an `M * N` array A:![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/31/screen-shot-2018-03-31-at-161748.png)

So actually `A[i][j]` equals to `A[i * N + j]` if we defined\_A\_as a one-dimensional array which also contains `M * N` elements.

**2. In Java, the two-dimensional array is actually a one-dimensional array which contains M elements, each of which is an array of N integers.**

The picture below shows the actual structure of a two-dimensional array A in Java:

![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/31/screen-shot-2018-03-31-at-162857.png)

## Array Basic Operations

### Iterate Through Loop in Java

[Five ways to Iterate Through Loop in Java](http://crunchify.com/how-to-iterate-through-java-list-4-way-to-iterate-through-loop/)

```java
package crunchify.com.tutorial;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * @author Crunchify.com
 */

public class CrunchifyIterateThroughList {

    public static void main(String[] argv) {

        // create list
        List<String> crunchifyList = new ArrayList<String>();

        // add 4 different values to list
        crunchifyList.add("eBay");
        crunchifyList.add("Paypal");
        crunchifyList.add("Google");
        crunchifyList.add("Yahoo");

        // iterate via "for loop"
        System.out.println("==> For Loop Example.");
        for (int i = 0; i < crunchifyList.size(); i++) {
            System.out.println(crunchifyList.get(i));
        }

        // iterate via "New way to loop"
        System.out.println("\n==> Advance For Loop Example..");
        for (String temp : crunchifyList) {
            System.out.println(temp);
        }

        // iterate via "iterator loop"
        System.out.println("\n==> Iterator Example...");
        Iterator<String> crunchifyIterator = crunchifyList.iterator();
        while (crunchifyIterator.hasNext()) {
            System.out.println(crunchifyIterator.next());
        }

        // iterate via "while loop"
        System.out.println("\n==> While Loop Example....");
        int i = 0;
        while (i < crunchifyList.size()) {
            System.out.println(crunchifyList.get(i));
            i++;
        }

        // collection stream() util: Returns a sequential Stream with this collection as its source
        System.out.println("\n==> collection stream() util....");
        crunchifyList.forEach((temp) -> {
            System.out.println(temp);
        });
    }
}
```

### Conversion between Array and ArrayList in Java

#### From `Array` to `ArrayList`

<https://dzone.com/articles/how-convert-array-arraylist>

```java
// java.util.ArrayList

Element[] array = {new Element(1),new Element(2),new Element(3)};

// 1. Most popular and accepted answer
ArrayList<Element> arrayList = new ArrayList<Element>(Arrays.asList(array));

// Next popular answer
List<Element> list = Arrays.asList(array);
// Cons: It is not the best, because the size of the list returned from asList() is fixed
```

#### From `ArrayList` to `Array`:

<https://www.geeksforgeeks.org/arraylist-array-conversion-java-toarray-methods/>

<https://stackoverflow.com/questions/7969023/from-arraylist-to-array>

```java
// Method 1: Using Object[] toArray() method


// (Preferred) Method 2: Using T[] toArray(T[] a)
// a − This is the array into which the elements of the list are to be stored, 
// if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
// java.util.ArrayList.toArray(T[])

ArrayList<Integer> foo = new ArrayList<Integer>();
foo.add(1);
foo.add(1);
foo.add(2);
foo.add(3);
foo.add(5);

Integer[] bar = foo.toArray(new Integer[foo.size()]);

System.out.println("bar.length = " + bar.length);


// Method 3: Using get() in for loop manually
```

<https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html>

The following from source: <https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html>

For example, suppose that`c`is a`Collection`. The following snippet dumps the contents of`c`into a newly allocated array of`Object`whose length is identical to the number of elements in`c`.

```
Object[] a = c.toArray();
```

Suppose that`c`is known to contain only strings (perhaps because`c`is of type`Collection<String>`). The following snippet dumps the contents of`c`into a newly allocated array of`String`whose length is identical to the number of elements in`c`.

```
String[] a = c.toArray(new String[0]);
```

### Sliding Window

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. `[i,j)` (left-closed, right-open). A sliding window is a window "slides" its two boundaries to the certain direction. For example, if we slide `[i, j)`to the right by 11 element, then it becomes `[i+1, j+1)` (left-closed, right-open).

### **Prefix Sum**

Prefix sum 数组的 local / global 通用模板，求 min / max 皆可，使用时需要注意初始条件以及顺序:

```java
        int[] leftMax = new int[n];
        int prefixSum = 0;
        // 代表从起始位置开始，值最小的连续和数组
        int localMin = 0;
        int globalMax = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            prefixSum += nums[i];
            globalMax = Math.max(globalMax, prefixSum - localMin);
            localMin = Math.min(localMin, prefixSum);

            leftMax[i] = globalMax;
        }
```

### Kadane's Algorithm

Kadane's Algorithm 相比 prefix sum 的特点是，必须要以 nums\[0] 做初始化，从 index = 1 开始搜，优点是在处理 prefix product 的时候更容易处理好“-1” 和 “0” 的情况。

这类靠 prefix sum/product 的 subarray 问题，要注意好对于每一个子问题的 local / global 最优解结构，其中 local 解都是“以当前结尾 && 连续”，而 global 未必。

```java
public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;

        int localMax = nums[0];
        int globalMax = nums[0];
        for(int i = 1; i < nums.length; i++){
            localMax = Math.max(nums[i], localMax + nums[i]);
            globalMax = Math.max(globalMax, localMax);
        }

        return globalMax;
    }
}
```

\***Subarray Sum 系列问题参考：**

Source: <https://mnmunknown.gitbooks.io/algorithm-notes/626,_dong_tai_gui_hua_ff0c_subarray_lei.html>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.