Array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. So accessing any element by its index or key is constant time as O(1), and looping the array is linear time as O(n).
This doc will introduce the data structure of the array in Java and techniques for interviews.
- Array in Java
- Things to be clarified in an interview
- Techniques
- References
An array can contain primitive data types as well as objects of a class depending on the definition of array. In the case of primitive data types, the actual values are stored in contiguous memory locations. In the case of objects of a class, the actual objects are stored in a heap segment.
- In Java, all arrays are dynamically allocated.
- Since arrays are objects in Java, we can find their length using member length.
- A Java array variable can also be declared like other variables with [] after the data type.
- The variables in the array are ordered and each has an index beginning from 0.
- Java array can also be used as a static field, a local variable, or a method parameter.
- The size of an array must be specified by an int value and not long or short.
- The direct superclass of an array type is Object.
- Every array type implements the interfaces Cloneable and java.io.Serializable.
The general form of an array declaration is
Type variableName[]; OR Type[] variableName; // One-dimensional array
Type variableName[][]; OR Type[][] variableName; // Two-dimensional arrayAn array declaration has two components: the type and the name. Type declares the element type of the array. The element type determines the data type of each element that comprises the array. Examples:
int intArray[]; // Array of primitive integers
float[][] floatArray; // Array of primitive floats
String[] strArray; // Array of strings (string is not primitive in Java)
Object[] ao; // Array of base objects
Collection[] ca; // Array of collectionsThe array declaration as int intArray[]; does not create any of them in memory. So no array actually exists. It simply tells the compiler that this (intArray) variable will hold an array of the integer type. To link intArray with an actual, physical array of integers, you must allocate one using new and assign it to intArray.
The general form of new as it applies to one-dimensional arrays appears as follows:
variableName = new type [size];Here, type specifies the type of data being allocated, size specifies the number of elements in the array, and var-name is the name of array variable that is linked to the array. That is, to use new to allocate an array, you must specify the type and number of elements to allocate.
Examples:
int[] intArray = new int[20];
int[] intArray2;
intArray2 = new int[20];
System.out.println(Arrays.toString(new int[]{1, 2})); // Array literal, introduced laterThe elements in the array allocated by the new will automatically be initialized as
- boolean :
false - int :
0 - double :
0.0 - String :
null - User defined type :
null
Array length cannot be changed once it has been created.
In a situation, where the size and variables of the array are already known, array literals can be used.
int[] intArray = new int[]{ 1,2,3,4,5,6,7,8,9,10 };
int[] intArray = { 1,2,3,4,5,6,7,8,9,10 };The length of this array determines the length of the created array. There is no need to write the new int[] part in the latest versions of Java
Each element in the array is accessed via its index. The index begins with 0 and ends at (total array size)-1. All the elements of an array can be accessed using Java for Loop.
for (int i = 0; i < arr.length; i++)
System.out.println("Element at index " + i + " : "+ arr[i]);Multidimensional arrays are arrays of arrays with each element of the array holding the reference of another array. These are also known as Jagged Arrays. A multidimensional array is created by appending one set of square brackets ([]) per dimension. Examples:
int[][] intArray = new int[10][20]; //a 2D array or matrix
int[][][] intArray2 = new int[10][20][10]; //a 3D array
int[][]c;
c = new int[2][]; // creates 2 rows
c[0] = new int[5]; // 5 columns for row 0
c[1] = new int[3]; // create 3 columns for row 1Like variables, we can pass and return arrays in a function.
public static String[] toString(int[] arr) {
String[] strArray = new String[arr.length];
for (int i = 0; i < arr.length; i++)
strArray[i] = String.valueOf(arr[i]);
return strArray;
}Java contains a special utility class that makes it easier for you to perform many often-used array operations like copying and sorting arrays, filling in data, searching in arrays etc. The utility class is called Arrays and is located in the standard Java package java.util.
int[] source = new int[10]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] dest = Arrays.copyOf(source, source.length); // the length of new array is 10int[] source = new int[10]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int[] dest = Arrays.copyOf(source, 1, 5); // the length of new array is 5int[] nums = new int[10]{10, 3, 4, 9, 6, 1};
Arrays.sort(nums);int[] intArray = new int[10];
Arrays.fill(intArray, 123);int[] ints = {0,2,4,6,8,10};
int index = Arrays.binarySearch(ints, 6);
System.out.println(index);int[] ints1 = {0,2,4,6,8,10};
int[] ints2 = {0,2,4,6,8,10};
int[] ints3 = {10,8,6,4,2,0};
boolean ints1EqualsInts2 = Arrays.equals(ints1, ints2);
boolean ints1EqualsInts3 = Arrays.equals(ints1, ints3);
System.out.println(ints1EqualsInts2); // true
System.out.println(ints1EqualsInts3); // false-
Is the array sorted or partially sorted? If so, it means you can use binary search, in which time complexity is O(lgn).
-
Can you manipulate the array in place? The reference of an array is a pointer. So any change will be preserved.
-
Can you sort the array? Sometimes sorting the array first may significantly simplify the problem. Make sure that the order of array elements does not need to be preserved before attempting a sort.
-
Are there duplicates in the array? Would it affect the answer? Make sure the result is unique or not.
Two-pointers are really an easy and effective technique that is typically used for searching pairs in a sorted array, or one slow-runner and the other fast-runner.
Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.
boolean isSum(int[] nums, int target) {
int i = 0, j = nums.length;
while(i < j) {
int sum = nums[i] + nums[j];
if (sum == target) return true;
else if (sum < target) i++;
else j--;
}
return false;
}This technique shows how a nested for loop in a few problems can be converted to a single for loop and hence reducing the time complexity. It can be best understood with the window pane in bus, consider a window of length n and the pane which is fixed in it of length k.
Applying the sliding window technique :
- We compute the sum of the first k elements out of n terms using a linear loop and store the sum in variable window_sum.
- Then we will graze linearly over the array till it reaches the end and simultaneously keep track of the maximum sum.
- To get the current sum of the block of k elements just subtract the first element from the previous block and add the last element of the current block.
For example, given an array as {5, 2, -1, 0, 3} and fixed window size is 3.
The size of the sliding window is, sometimes, not fixed. In that case, we need to move the pointers inconsistently, but make sure the size should not be 0.
For questions where summation or multiplication of a sub-array is involved, pre-computation using hashing or a prefix/suffix sum/product might be useful.
int[] left = new int[nums.length];
for (int i=1; i<nums.length; i++) {
left[i] = nums[i-1] + left[i-1];
}DP is introduced in its own doc.