# Array Exercises

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.

## Write a function that when input an array of integers returns the maximum integer in the array.

If this was a question asked in an interview the first thing to do would be to clarify the question asked:

• Is this array sorted?
• How to handle edge cases? (ie invalid input such as a null array or an array of

Here we will make the following assumptions:

• The array will not be sorted
• In the case of invalid input we will return the minimum value of an integer

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:

public int getMax(int[] arr) {

}

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.

if(arr == null)
return Integer.MIN_VALUE;

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:

for(int i = 0; i < size; i++) {
if(arr[i] > max)
max = arr[i];
}

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

• The time complexity of this algorithm is O(N) since to get the answer we have to iterate through each element in the array.
• 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.

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

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:

if(size > 0) {
Arrays.sort(arr);
max = arr[size-1];
}

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

## Write a function that when input an array of integers returns the sum of all integers in the array.

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.

public int getSum(int[] arr) {

}

Add code to handle a null array:

if(arr == null)
return 0;

Next add code to get the array size, intialize our sum to 0, and return our sum:

int size = arr.length;
int sum = 0;
//add code to calculate the sum here
return sum;

Lastly add the code to iterate through the array and add the value of each element to our sum:

for(int i = 0; i < size; i++)
sum += arr[i];

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

• The time complexity of this algorithm is O(n) since to get the answer we have to iterate through each element in the array.
• 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 and sum values.

## Write a function that when input an array of strings and a string s returns true if the array contains the string s and false elsewise.

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.

public boolean contains(String[] arr, String s) {

}

Add code to return false if a null string is passed in:

if(s == null)
return false;

Add code to iterate through the array and return true if the string s is found:

int size = arr.length;
for(int i = 0; i < size; i++)
if(arr[i].equals(s))
return true;

Finally return false if the string cannot be found:

return false;

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

• The time complexity of this algorithm is O(N) since to get the answer we have to iterate through each element in the array.
• The space complexity of this algorithm is O(1) since no storage is needed to be declared in the algorithm other then the integer to hold the size.

Data Structures