[Java - Array & ArrayList] #Java #Array #tutorial #interview #Array

0 - Introduction to Array.md

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.

An array can have one or more dimensions.

Here we start with the one-dimensional array, which is also called the linear array.

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
    
        // 1. Initialize
        int[] a0 = new int[5];
        int[] a1 = {1, 2, 3};
    
    	// 2. Get Length
        System.out.println("The size of a1 is: " + a1.length);
        
        // 3. Access Element
        System.out.println("The first element is: " + a1[0]);
        
        // 4. Iterate all Elements
        System.out.print("[Version 1] The contents of a1 are:");
        for (int i = 0; i < a1.length; ++i) {
            System.out.print(" " + a1[i]);
        }
        
        System.out.println();
        System.out.print("[Version 2] The contents of a1 are:");
        
        for (int item: a1) {
            System.out.print(" " + item);
        }
        System.out.println();
        
        // 5. Modify Element
        a1[0] = 4;
        
        // 6. Sort
        Arrays.sort(a1);
    }
}

1 - Introduction to Dynamic Array.md

an array has a fixed capacity and we need to specify the size of the array when we initialize it

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.

// "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);
    }
}

2 - Find Pivot Index.md

Given an array of integers nums, write a method that returns the "pivot" index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:

Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Note:

• The length of nums will be in the range [0, 10000].
• Each element nums[i] will be an integer in the range [-1000, 1000].

Java

class Solution {
    public int pivotIndex(int[] nums) {
        int total=0 , sum = 0;
        for(int i=0;i<nums.length;i++) {
            total += nums[i];
        }
        for(int i=0;i<nums.length;i++) {
            if(sum*2 == total - nums[i]) {
                return i;
            }else{
                sum += nums[i];
            }
        }
        return -1;
    }
}

Python 3

class Solution(object):
    def pivotIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        total = 0
        half_sum = 0
        
        for num in nums:
            total += num
            
        for i in range(0, len(nums)):
            if half_sum*2 == total - nums[i]:
                return i
            else:
                half_sum += nums[i]
        
        return -1

3 - Largest Number At Least Twice of Others.md

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:

Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Example 2:

Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

Note:

1. nums will have a length in the range [1, 50].
2. Every nums[i] will be an integer in the range [0, 99].

Java

class Solution {
    public int dominantIndex(int[] nums) {
        int max = 0;
        int second_max = 0;
        int index_max = 0;
        
        for (int i=0; i<nums.length; i++) {
            if(max < nums[i]) {
                second_max = max;
                max = nums[i];
                index_max = i;
            } else if (nums[i] != max && nums[i] > second_max) {
                second_max = nums[i];
            }
        }
        
        if (second_max*2 <= max) {
            return index_max;
        }
        
        return -1;
    }
}

Python 3

class Solution:
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        first_max = 0
        second_max = 0
        index_max = 0
        
        for i in range(0, len(nums)):
            if nums[i] > first_max:
                second_max = first_max
                first_max = nums[i]
                index_max = i
            elif nums[i] != first_max and nums[i] > second_max:
                second_max = nums[i]
                
        if second_max*2 <= first_max:
            return index_max
        
        return -1

4 - Plus One.md

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Java

class Solution {
    public int[] plusOne(int[] digits) {
        
        if(digits[digits.length - 1] < 9) {
            digits[digits.length - 1] += 1;
        } else {
            for (int i = digits.length - 1; i >= 0; i--) {
                if(digits[i] == 9) {
                    digits[i] = 0;
                    
                    if(i == 0) {
                        digits = Arrays.copyOf(digits, digits.length+1);
                        digits[digits.length - 1] = 0;
                        digits[0] = 1;
                    }
                } else {
                    digits[i] += 1;
                    break;
                }
            }
        }
        
        return digits;
    }
}