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.

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

Primitive Array

/*
* 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

/*
* 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.

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));

Subsequence 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.

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.

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]$

[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:

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:

/*
*   [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)?

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

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

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.
• 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.

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