Test your knowledge of arrays with the following questions. It is recommended for one to attempt their best to solve each question before looking at the answer and explanation.
If this was a question asked in an interview the first thing to do would be to clarify the question asked:
Here we will make the following assumptions:
Our approach will be quite simple. We will declare an integer called max which will hold the maximum value. It will first be initialized to the minimum value of an integer. We will then iterate through our array and for each index we will check if the element at that index is greater then our current maximum value. If the element is greater then our current maximum then we will update our maximum value to the value of the element. After iterating through our array the maximum value will be stored in the integer max. We will then return the integer max.
To start this off we first declare our getMax method which takes an integer array as a parameter and returns an integer:
We will first add code to check for invalid input in the form of a null array. If the array is null we will return Integer.MIN_VALUE which is a special constant in Java which refers to the minimum value an integer can be.
Next we will add the code to get the array size, initialize our max integer, and return our max value:
int size = arr.length;
int max = Integer.MIN_VALUE;
//insert the code to iterate through the for loop here
return max;Lastly we will add the code to iterate through the array arr and update the max value as needed:
The full complete function should look as follows:
public int getMax(int[] arr) {
if(arr == null)
return Integer.MIN_VALUE;
int size = arr.length;
int max = Integer.MIN_VALUE;
for(int i = 0; i < size; i++) {
if(arr[i] > max)
max = arr[i];
}
return max;
}BUT WAIT A SECOND, our invalid input case of an array with a size of 0 hasn’t been handled yet has it? Look again. Our max integer is originally set to Integer.MIN_VALUE. If the size of the array is 0 then our array will never be entered and our max integer will still contain the value of Integer.MIN_VALUE when our return max statement is processed. This will effectively return the minimum value of an integer when an array of size 0 is passed in as a parameter.
Time/Space Complexity
An alternate approach to solving this problem is to first sort the array and then return the last element in the array. If the array is sorted from low to high then the last element is guaranteed to be the maximum element. We will handle invalid input the same as in the first answer (by returning Integer.MIN_VALUE).
Let’s start with the following code from our last example:
public int getMax(int[] arr) {
if(arr == null)
return Integer.MIN_VALUE;
int size = arr.length;
int max = Integer.MIN_VALUE;
//enter sorting/getting of max value here
return max;
}Sort the array and get the max value after sorting if size is greater than 0:
The finished method is as follows:
public int getMax(int[] arr) {
if(arr == null)
return Integer.MIN_VALUE;
int size = arr.length;
int max = Integer.MIN_VALUE;
if(size > 0) {
Arrays.sort(arr);
max = arr[size-1];
}
return max;
}It’s important to note that this method comes with the side effect of sorting the inputted array. If that effect is not desired then this answer would not be correct.
Time/Space Complexity * The time complexity of this algorithm is O(nlog(n)) since to get the answer we have to sort the array. Sorting takes O(nlog(n)) time. * The space complexity of this algorithm is O(1) since no storage is needed to be declared in the algorithm other then the integers to hold the size/max value.
This answer is not quite is good as the initial answer to the problem since it is slower O(n*log(n)) vs O(n) and also causes a side effect of sorting the array (which may not be wanted).
Here we will make a different assumption with how to handle invalid input then the previous question. In the case of invalid input we will return 0. Our approach with how to solve this problem is as follows. First we will declare an integer named sum that will hold the sum of all the elements. It will be initialized to the value 0. Then we will iterate through each element in the array and add the element to our sum variable. Afterwards we will return the value of sum. In the case of a null array or an array of size 0 we will return 0.
Let’s start with the following function definition:
Add code to handle a null array:
Next add code to get the array size, intialize our sum to 0, and return our sum:
Lastly add the code to iterate through the array and add the value of each element to our sum:
The finished function should look as follows:
public int getSum(int[] arr) {
if(arr == null)
return 0;
int size = arr.length;
int sum = 0;
for(int i = 0; i < size; i++)
sum += arr[i];
return sum;
}Time/Space Complexity
In this case we will make the following assumption. If the input is invalid we will return false. We will define invalid input to be a null string. To solve this problem we will iterate through each element in the array. If an element are any point in the array is equal to s we will return true. If we make it through the array without finding the string s, then we will return false. If the inputted string is null we will return false.
Let’s start with the following function definition:
Add code to return false if a null string is passed in:
Add code to iterate through the array and return true if the string s is found:
Finally return false if the string cannot be found:
The finished function is as follows:
public boolean contains(String[] arr, String s) {
if(s == null)
return false;
int size = arr.length;
for(int i = 0; i < size; i++)
if(arr[i].equals(s))
return true;
return false;
}Time/Space Complexity