# Array Introduction

## What is

An array in Java is **an object containing a fixed number of values of the same type**.  We can have both primitive array and object arrays.

### Fixed Length 

Once an array is defined, the length will not be able to change.

```java
int[] arr = new int[]{1,2,3}// implicit length declaration of 3
int[] arr = new int[3]; // explicit length declaration
```

### Primitive Array

```java
/*
* Primitive array creation,
* the elements are of primitive datatype.
* so it does not have any methods,
* so arr[0].compareTo(arr[1]) is syntactically wrong
*
* */
int[] arr_primitive_types = new int[]{1, 2, 3};
//arr_primitive_types[0].compareTo(arr_primitive_types[1]);
// syntactically wrong
```

### Object Array

```java
/*
* Object type array,
* the elements are of object data type,
* thus they enjoy all the methods that come with them.
*  for example,
*    arr_object_type[0].compareTo(arr_object_type[1]); // no problem
*
* */
Integer[] arr_object_type = new Integer[]{1,2,3};
arr_object_type[0].compareTo(arr_object_type[1]); // no problem
```

## Arrays Utils Class

Java Standard library offers a convenient utility class *java.util.Arrays* to deal with arrays.

```java
int[] arr = new int[]{0, 1, 2, 3, 4, 5};

// 1d array to String
System.out.println(Arrays.toString(arr));

// copyOf (have to offer the length) and copyOfRange
int[] arr_copy = Arrays.copyOf(arr, arr.length);
int[] arr_copy_range = Arrays.copyOfRange(arr, 1, 3);

System.out.println("copy:\n" + Arrays.toString(arr_copy));
System.out.println("range copy:\n" + Arrays.toString(arr_copy_range));

// set same initial values
int[] arr1 = new int[5];
Arrays.fill(arr1, -1);
System.out.println("fill -1\n" + Arrays.toString(arr1));

// sort and sort with comparator
Integer[] arr2 = new Integer[]{3, 1, 2};
Arrays.sort(arr2);
Comparator<Integer> reverse = (a, b) -> b - a;
Arrays.sort(arr2, reverse);
System.out.println("Descending order:\n" + Arrays.toString(arr2));

// search and binary seach
System.out.println("Index is of 1 is:\n" + Arrays.binarySearch(arr, 1));

// 2d array
int[][] arr2d = new int[][]{
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9},
};
// deep to string
System.out.println("2d array to string:\n" + Arrays.toString(arr2d));
System.out.println("2d array deep to string:\n" + Arrays.deepToString(arr2d));

// 3d array
int[][][] arr3d = new int[][][]{
        {{1, 2}, {3, 4}},
        {{5, 6}, {7, 8}}
};
System.out.println("3d array deep to string:\n" + Arrays.deepToString(arr3d));

// array to fixed length list
List<Integer> list = Arrays.asList(arr2);
// list.add(10); // WRONG THIS LIST IS OF FIXED LENGTH CAN'T ADD
System.out.println("list to string" + list.toString());

// setAll with lambda
String[] strings = new String[]{"a", "b", "c"};
Arrays.setAll(strings,  i -> strings[i].toUpperCase());
System.out.println("lower to upper case:\n" + Arrays.toString(strings));
```

## Subs**equence of Array**

A **subsequence** is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, `[3,6,2,7]` is a subsequence of the array `[0,3,1,6,2,2,7]`.

### All Subsequences

Given an array A, suppose the length of this array is n, then there is a total $$2^n$$ number of subsequences.

{% hint style="warning" %}
Subsequences are kind of like subsets in terms of the total number of all subsequences and subsets, however ***unlike subset which does not have an intrinsic order, subsequence does.***
{% endhint %}

Use a binary digit for each element in the array to represent if it is present in a given subsequence, then apparently this binary number can represent all numbers within $$\[0, 2^n - 1]$$

```bash
[1, 2, 3]   subseq
 0, 0, 0  0  []
 0, 0, 1  1  [3]
 0, 1, 0  2  [2]
 0, 1, 1  3  [2, 3]
 1, 0, 0  4  [1]
 1, 0, 1  5  [1, 3]
 1, 1, 0  6  [1, 2]
 1, 1, 1  7  [1, 2, 3]
 
 total 2^3 = 8 different subsequence
 
```

Turn this thought into code:

```java
public static List<List<Integer>> all(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < Math.pow(2, nums.length); i++) {
            int num = i, j = nums.length - 1;
            List<Integer> l = new ArrayList<>();
            while (num > 0) {
                if (num % 2 == 1) l.add(nums[j]);
                num = num >> 1;
                j--;
            }
            res.add(l);
        }
        return res;
    }

public static void main(String[] args) {

        int[] arr = new int[]{1, 2, 3};
        
        System.out.println("Total number of subseqs is: " + all(arr).size());
        System.out.println(all(arr).toString());
    }

// Output
// Total number of subseqs is: 8
// [[], [3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]]    
    
```

**Cascading:**

```java
/*
*   [1, 2, 3]     []                                                       1
*   [2, 3]     1  [] | [1]                                                 1+1 = 2
*   [3]        2  [] | [1] | [2], [1, 2]                                   2+2 = 4
*   []         3  [] | [1] | [2], [1, 2] | [3], [1, 3], [2, 3], [1, 2, 3]  4+4 = 8
*
* */

public static List<List<Integer>> cascading(int[] nums) {
    List<List<Integer>> res = new ArrayList();
    res.add(new ArrayList<Integer>());
    for(int num : nums){
        List<List<Integer>> cur = new ArrayList();
        for (List<Integer> l : res)
            cur.add(new ArrayList<Integer>(l){{add(num);}});
        for (List<Integer> l : cur) res.add(l);
    }

    return res;

}

public static void main(String[] args) {

    int[] arr = new int[]{1, 2, 3};

    System.out.println("Total number of subseqs is: " + all(arr).size());
    System.out.println(all(arr).toString());

    System.out.println("Total number of subseqs is: " + cascading(arr).size());
    System.out.println(cascading(arr).toString());
}
```

### Calculate Running Time(Quiz)

```
Suppose a computer can calculate one billion subsequences of an array for one second
how long does it take to calculate all subsequences for an array with a length of 32?

how about an array of 64 length? 
what about 128?
```

## Is Subsequence

```
Given two array num1 and num2
Write a method to verify if num1 is a subsequency of num2.

Example 1:

Input: nums1 = [1, 2], nums2 = [2, 1, 3, 1]
Output: False
Explanation: nums1 is a subset of nums2 but not subsequence



Example 2:

Input: nums1 = [1, 2], nums2 = [2, 1, 3, 2]
Output: True
Explanation: 
```

### Brute Force

```
For all the subsequences of num2 verify if it is an equal string as num1.

What is the total number of such verifications (comparisons)?
```

### Two-Pointers

```
For each integer in num2, compare it to the next integer in num1, 
if they are equal we know that this integer in num1 is also in num2 in order 
then move to the next integer in num1. When all the integers in num1 find 
equal numbers in num2, then we know num1 is a subsequence of num2

What is the total number of such verifications (comparisons)?
```

```java
public static boolean isSubsequence(int[] num1, int[] num2) {

    int i = 0, j = 0;
    while (i < num1.length && j < num2.length) {
        if (num1[i] == num2[j]) i++;
        j++;
    }
    return i == num1.length ? true : false;
}

public static void main(String[] args) {
    int[] num1 = new int[] {1, 3, 2};
    int[] num2 = new int[] {1, 4};
    int[] num3 = new int[] {1, 2, 1, 2, 3, 1, 3, 2};
    System.out.println("num1 and num3: " + isSubsequence(num1, num3));
    System.out.println("num2 and num3: " + isSubsequence(num2, num3));
}
```

## Subarray

A subarray is a contiguous array of a given array. There are precisely n \* (n + 1) / 2 number of subarrays.

### All Subarray

```java
public static List<int[]> all(int[] nums){
    List<int[]> res = new ArrayList();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            res.add((Arrays.copyOfRange(nums, i, j+1)));
        }
    }
    return res;
}

public static void main(String[] args) {
    int[] nums = new int[]{1,2,3};
    System.out.println("number is: " + all(nums).size());
    for (int[] arr : all(nums))
        System.out.println(Arrays.toString(arr));
}
```

### Calculate Running Time(Quiz)

```
Suppose a computer can calculate one billion subarray of an array for one second
how long does it take to calculate all subsequences for an array with a length of 32?

how about an array of 64 length? 
what about 1,000,000,000?
```

## Longest Increasing Subarray

```
Example 1:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.
Example 2:

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.
```

### Brute Force

```
For all the subarray of nums verify if each is strictly increasing.

What is the total number of such verifications?
```

### (Sliding Window) Two-Pointers

```
Starting from the beginning and scan the rest of array, if there is a decreasing, 
then record the so far longest increasing array length, and moving the starting 
array index to the current index and scan the rest of the array
```

```java
public static int[] subarray(int[] nums) {
    int x=0, y=0, cur = 0;
    for (int i = 0, j = 1; j < nums.length; j++) {
        if (nums[j] <= nums[j - 1]) {
            if (j - i > y - x) {
                x = i;
                y = j;
            }
            i = j;
        }
    }
    return Arrays.copyOfRange(nums, x, y);
}

public static void main(String[] args) {
    int[] nums1 = new int[]{1,3,5,4,7};
    int[] nums2 = new int[]{2,2,2,2,2};
    System.out.println("nums1's longest increasing subarray is:" + Arrays.toString(subarray(nums1)));
    System.out.println("nums2's longest increasing subarray is:" + Arrays.toString(subarray(nums2)));
}
```

## A Summary

* Calculate all subsequences of a given array takes $$2^n$$subsequence findings, which is called an exponential running time.&#x20;
* Calculate all subarrays of a given array takes $$\frac{n\*(n+1)} {2} =\frac{1} {2}(n^2 + n)$$  subarray findings, which is called an quadratic running time.
* You can clearly see the drastically running time difference between these two when $$n$$ gets large.&#x20;

## Maximum Product of a Non-Empty Subset of an Array

```
Input: nums = [-1]
Output: -1
Explanation: -1 is the only element

Input: nums = [-1, 0]
Output: 0
Explanation: 

Input: nums = [-1, 0, 1]
Output: 1
Explanation: 

Input: nums = [-1, -2, 0, 1]
Output: 2
Explanation: -1 * (-2) * 1 = 2

```


---

# 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://haoyu2.gitbook.io/cs310/array-introduction.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.