1. Arrays

Arrays are important data structures that also appear indirectly in Java, for example in the extended for loop or variable arguments lists. This chapter includes exercises on creating arrays, traversing arrays, and questions about algorithms, such as how to search for elements in an array.

Prerequisites

  • be able to create, access and fill arrays

  • be able to traverse arrays with an extended for loop

  • be able to use one and multidimensional arrays

  • be able to build variable argument lists

  • know utility methods of the class Arrays

Data types used in this chapter:

1.1. Everything has a type

Before we look at accessing elements, let’s take a closer look at types. It is important to know the difference between object type and reference type.

1.1.1. Quiz: Array types ⭐

Arrays are covariant in Java, which means, for example, that String[] is a subtype of Object[]. This sounds a bit academic, it probably is, so the following task is intended to sharpen your understanding of array covariance.

Consider whether all statements compile or work at runtime:

/* 1 */ String[] strings1 = new String[ 100 ];
/* 2 */ Object[] a1 = (String[]) strings1;
/* 3 */ Object[] a2 = strings1;
/* 4 */ Object[] strings2 = new String[]{ "1", "2", "3" };
/* 5 */ String[] a3 = (String[]) strings2;
/* 6 */ String[] strings3 = { "1", "2", "3" };
/* 7 */ Object[] a4 = strings3;
/* 8 */ Object[] strings4 = { "1", "2", "3" };
/* 9 */ String[] a5 = (String[]) strings4;

/* A */ int[] ints1 = new int[ 100 ];
/* B */ Object[] a6 = (int[]) ints1;
/* C */ Object[] ints2 = new int[ 100 ];
/* D */ int[] a7 = (int[]) ints2;

1.2. One-dimensional arrays

An array is a collection of homogeneous elements. One-dimensional arrays contain the elements directly and no other sub-arrays.

1.2.1. Loop arrays and output wind speed, wind direction. ⭐

Captain CiaoCiao is sailing across the sea, the wind is blowing from all sides. He must always keep the wind speed and direction in mind.

Task:

  1. Declare two arrays int[] windSpeed and int[] windDirection.

  2. Initialize both arrays each with three integer random numbers (in principle the number should be arbitrary), where the wind speed can be between 0 and (less than) 200 km/h and the wind direction between 0 and (less than) 360 degrees.

  3. Run a loop over the array and output all pairs comma separated.

Example:

  • For example, if the array windSpeed contains the values {82, 70, 12} and the array windDirection contains the values {12, 266, 92}, the output to the screen should be:

    Wind speed 82 km/h and wind direction 12°, Wind speed 70 km/h and wind direction 266°, Wind speed 12 km/h and wind direction 92°.

Note: Remember that the segments are separated by a comma and there is no comma at the end.

1.2.2. Detect constant revenue increase ⭐

At the end of a month, Captain CiaoCiao receives a report of the sales he and his crew have generated. The monthly list records the profit on any given day. It has this format:

//                Day    1,    2,   3,    4,    5 ... up to a maximum of 31
int[] dailyGains  = { 1000, 2000, 500, 9000, 9010 };

Captain CiaoCiao is happy with the numbers, and he wants to pay a reward when gains have increased over 5%. From 1000 to 2000 is a whopping 100% jump, from 500 to 9000 is as well, but definitely not from 2000 to 500, nor from 9000 to 9010.

Task:

  • Write a method int count5PercentJumps(int[]) that returns the number of sales jumps. A sales jump is given if the sales were 5% higher than the previous day.

  • The passed array must not be null, otherwise an exception follows.

1.2.3. Search consecutive strings and determine if Salty Snook is coming ⭐

Bonny Brain watches the flags of passing ships because she is waiting for Salty Snook. She looks at each flag and knows that Salty Snook never comes alone, but moves in a convoy of four ships. She doesn’t know the flags themselves, only that they all have the same inscription.

Task:

  • Write a new method isProbablyApproaching(String[] signs) that returns true if there are four of the same abbreviation in the array in a row. Keep in mind that strings are compared with equals(…​).

  • The array passed must not be null, and no element in the array must be null.

Example:

String[] signs1 = { "F", "DO", "MOS", "MOS", "MOS", "WES" };
isProbablyApproaching( signs1 ); // true

String[] signs2 = { "F", "DO", "MOS", "MOS", "WES", "MOS", "MOS" };
isProbablyApproaching( signs2 ); // false

1.2.4. Reverse an array ⭐

Charlie Creevey does the finances for Captain CiaoCiao. But instead of sorting the income in ascending order, he sorted it in descending order. Therefore, the list needs to be flipped.

To flip an array means to swap the first element with the last element, the second with the second to last, and so on.

Task:

  • Write a new static method reverse(…​) that flips a given array:

    public static void reverse( double[] numbers ) {
      // TODO
    }
  • The operation should be in place, that is, it should change the array passed. We do not want to create a new array.

  • Passing null will result in an exception.

Example:

  • { } → { }

  • { 1 } → { 1 }

  • { 1, 2 } → { 2, 1 }

  • { 1, 2, 3 } → { 3, 2, 1 }

The representation in the curly braces is symbolic only.

1.2.5. Find the nearest cinema ⭐⭐

The class java.awt.Point represents points with x/y coordinates. These can be used for positions very well.

In the cinema the new movie "Under the flag of the buccaneers" is shown, which Captain CiaoCiao absolutely has to see. But where is the nearest cinema?

Task:

  • Given a set of Point objects in an array points for the cinema positions.

    Point[] points = { new Point(10, 20), new Point(12, 2), new Point(44, 4) };
  • Write a method double minDistance(Point[] points, int size) that returns the distance of the point that has the smallest distance to the zero point. With size we can determine how many elements of the array should be considered, so that the array can be larger in principle.

  • A passed null is not allowed, also the points itself must not be null; an exception must be raised.

  • What do we have to change if the return type is Point, i.e. the point itself should be returned with the smallest distance?

Study the Javadoc to java.awt.Point to find out if the point itself can calculate distances to other coordinates.

1.2.6. Raid candy store and share fairly ⭐⭐

Captain CiaoCiao is robbing a candy store with his kids Junior and Jackie. The candy is on a long shelf, and each product has a weight. The data is available as an array:

int[] values = { 10, 20, 30, 40, 50 };

Junior and Jackie line up on opposite ends of the shelf on the left and right, and since Captain CiaoCiao loves both kids equally, they should end up taking home the same amount. Captain CiaoCiao points to a candy on the shelf, so all the products to the left of it go to Junior and all the products to the right of the position (including the one shown) are for Jackie.

Captain knows what is on the shelf, but does not know at what position to the left and to the right the same total will occur. Deviations of 10% are fine for the children. For the difference we want to use the following formula for the relative difference:

private static int relativeDifference( int a, int b ) {
  if ( a == b ) return 0;
  int absoluteDifference = Math.abs( a - b );
  return (int) (100. * absoluteDifference / Math.max( a, b ));
}

Task:

  • Write a method int findSplitPoint(int[]) that finds the index in the array where left and right can be fairly split. Any solution will do, not all solutions are necessary.

  • If there is no fair split, a method shall return -1.

Examples:

  • 10 + 20 + 30 + 40 ≈ 40 + 50, because 100 ≈ 90, and the index for the return is 4.

  • 10 20 30 40 100 results in -1, because there is no valid partitioning.

1.3. Extended for loop

If arrays are to be run from the first element, an extended for loop with an invisible loop counter can be used for this purpose. This saves code.

1.3.1. Draw mountains ⭐⭐

For the next treasure hunt, Bonny Brain and the crew have to go over mountains and hills. She is told the elevation beforehand and wants to get an impression of the profile beforehand.

Task:

  • Write a program with a method printMountain(int[] altitudes) that converts an array of altitude meters into an ASCII representation.

  • The altitude is to be represented by a multiplication sign * at exactly this altitude from a baseline. The heights can be arbitrary, but not negative.

Example:

  • The array { 0, 1, 1, 2, 2, 3, 3, 4, 5, 4, 3, 2, 2, 1, 0 } shall be represented as:

    5          *
    4         * *
    3      ***   *
    2    **       **
    1  **           *
    0 *              *

    The first column is for clarification and does not need to be implemented.

Optional extension:

  • Instead of *, use the symbols /, \, -, and ^ to indicate whether we are ascending, descending, on a plateau, or at the top.

    5          ^
    4         / \
    3      --/   \
    2    -/       -\
    1  -/           \
    0 /              \

1.4. Two- and multidimensional arrays

An array in Java can contain references to other arrays, and this is how you define multidimensional arrays in Java. In Java, there are no true two-dimensional arrays; two-dimensional arrays are nothing more than arrays that reference sub-arrays, and the sub-arrays could be of different lengths.

1.4.1. Check mini-sudoku for valid solution ⭐⭐

Since mugging is quite exhausting, Bonny Brain needs a balance and engages in Sudoku. A Sudoku game consists of 81 squares in a 9×9 grid. The grid can be divided into nine blocks, each block is a two-dimensional array of size 3 × 3. In each of these blocks, each number from 1 to 9 must occur exactly once — none may be missing.

Task:

  • Write a program that tests a two-dimensional array of nine elements to see if all numbers from 1 to 9 occur.

  • Missing elements are to be reported.

Example:

  • The following array is a valid Sudoku assignment:

    int[][] array = {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }
    };
  • The following array is not a valid Sudoku assignment:

    int[][] array = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 8 } };

    The error could be reported something like: Missing 9.

1.4.2. Enlarge image ⭐⭐

Images are often stored in memory as triples of red-green-blue values, where the individual values can range from 0 to 255. Since there are no colors in grayscale images, only one value is needed instead of three.

Task:

  • Given a two-dimensional integer array with values from 0 to 255; the array mentally represents a grayscale image.

  • Write a method int[][] magnify(int[][] array, int factor) that returns a new array and scales the image by the given factor. So an image of size 2 × 3 and factor 2 becomes an image of size 4 × 6. Image pixels are simply doubled, no interpolation of values is desired.

Example:

  • Assume the following array:

    { {1, 2, 3},
      {4, 5, 6} }

    Then, after doubling, it follows:

    { {1, 1, 2, 2, 3, 3},
      {1, 1, 2, 2, 3, 3},
      {4, 4, 5, 5, 6, 6},
      {4, 4, 5, 5, 6, 6} }

1.5. Variable argument lists

Java allows methods to which you can pass any number of arguments. They are called vararg methods. A vararg parameter may only be at the end of a parameter list and is an array. When called with variable arguments, the compiler automatically creates a new anonymous array and passes it to the method.

1.5.1. Create SVG polygons with variable number of coordinates ⭐

Bonny Brain wants to draw a map for her next place of work, and it should always look good printed and on any resolution, because every detail matters. The best technology for this is SVG.

In SVG there are different primitives, for example for lines, circles or rectangles. There is also an XML element for polylines. Example:

<polygon points="200,10 250,190 160,210" />

Task:

  • Declare a Java method printSvgPolygon(…​) to which we can pass any number of coordinate pairs. What errors could occur when passing them?

  • The method should print a matching SVG output to the screen for the passed pairs.

Example:

  • In printSvgPolygon( 200, 10, 250, 190, 160, 210 ), 200,10 is a coordinate pair, 250,190 is as well, as is 160, 210. The screen output should be: <polygon points="200,10 250,190 160,210" />.

Optional: study the example at https://www.w3schools.com/graphics/tryit.asp?filename=trysvg_polygon. Copy the self-generated SVG into the web interface.

1.5.2. Check for approval ⭐

Captain CiaoCiao gets feedback from his crew members about an order. All members can vote yes or no.

Task:

  • We are looking for a vararg method allTrue(…​) that can acccept any number of boolean values, but must be called at least with one argument.

  • If all arguments are true, the return is also true; if one of the boolean values is false, the method shall return false.

  • Since a vararg is internally an array, null may be passed — this must lead to an exception.

Example:

  • allTrue(true, true, true) returns true.

  • allTrue(true) returns true.

  • allTrue(true, false) returns false.

  • allTrue(true, null) returns an exception.

  • allTrue() cannot be compiled and must give a compiler error.

1.5.3. Help, tetraphobia! Put all fours last ⭐⭐

Bonny Brain meets befriended pirates in Hong Kong and finds that many suffer from tetraphobia and have a superstitious fear of the number 4. The accountant must now put all numbers with a 4 to the back.

Task:

  • Write a method fourLast(int... numbers) that places all numbers containing a 4 after the numbers that do not have a 4. The order of the numbers without 4 must not change, the numbers with a 4 can be anywhere at the end.

  • fourLast(…​) should return the passed array.

  • The argument null must lead to an exception.

Example:

  • int[] numbers = {1, 44, 2, 4, 43}; fourLast(numbers); modifies the array numbers so that 1 and 2 are before 44, 4 and 43 in the array. The 2 must not come before the 1 later.

  • fourLast( 4, 4, 44, 1234 ) returns the array automatically generated by the compiler with the entries for example in the order 4, 4, 44, 1234.

1.6. The utility class Arrays

Arrays "can`t" do much in Java, interesting methods are externalized in classes, for example java.util.Arrays. A method for copying arrays is in the class System.

1.6.1. Quiz: Copy arrays ⭐

What do these nonsensical variable names stand for and what is the effect of the following lines?

int[] hooey = { 1, 2, 3, 4 };
int[] shuck = new int[ hooey.length - 1 ];
int bushwa = 2;
int kelter = 0;
int piddle = 0;
System.arraycopy( hooey, kelter, shuck, piddle, bushwa );
System.arraycopy( hooey, bushwa + 1, shuck, bushwa, hooey.length - bushwa - 1 );
System.out.println( Arrays.toString( shuck ) );

1.6.2. Quiz: Compare arrays ⭐

What are the outputs?

Object[] array1 = { "Anne Bonny", "Fortune", "Sir Francis Drake", new int[]{ 1, 2, 3 } };
Object[] array2 = { "Anne Bonny", "Fortune", "Sir Francis Drake", new int[]{ 1, 2, 3 } };
System.out.println( array1 == array2 );
System.out.println( array1.equals( array2 ) );
System.out.println( arrays.equals( array1, array2 ) );
System.out.println( Arrays.deepEquals( array1, array2 ) );

1.7. Suggested solutions

1.7.1. Quiz: Array types

The variable declarations and assignments from strings1 to strings4 and int1 and int2 are less interesting; we know the syntax: An array is preinitialized with either a fixed size or elements.

The following type conversions, which are performed explicitly or implicitly, are interesting. We must distinguish between type conversions that are fine for the compiler and type conversions that cause trouble only at runtime. This is an important distinction, which also becomes clear in the terms object type and reference type. For the compiler there are reference variables and a reference type, the compiler does not know what is going on at runtime. The runtime environment, on the other hand, basically does not know under which variable type a variable was declared, but it does know what kind of object it has in front of it: We therefore speak of the object type.

The first statement is the most honest one. For the compiler it is a string array and for the runtime environment as well.

The type conversions in the second line is irrelevant because String[] is a subtype of Object[]. This is very important, because exactly this is covariant: A String array is a subtype of an Object array, also a Point[] is a special Object[]. This is also evident in the third line, where the explicit type conversion is missing because it is implicit.

In the fourth statement runtime environment and compiler know different things. For the runtime environment there is still a String array in memory, but the compiler knows the String array only as an Object array. This notation is valid in principle, and again an implicit type conversion takes place.

In the fifth statement we upgrade the Object array to a String array. This works at compile time and also at runtime.

In the sixth statement we again directly build a String array and note it as a String array. This is the usual notation. In the seventh statement we find an implicit type conversion from String array to Object array. This statement is fine.

The eighth and ninth statements are tricky: the compiler does not build a String array but an Object array and puts String references into this Object array. As a result, there is no String array, only an Object array that references strings. In the ninth line, the compiler trusts our decision to cast the Object array to a String array. The compiler accepts this, and there is no compiler error. However, a problem occurs at runtime. Since the runtime environment knows, of course, that the variable strings4 holds only an Object array and not a better String array, the exception java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.lang.String; follows.

The last four examples are easier for the compiler to identify as false. While the declaration of ints1 is still correct, B and C and D will lead to a compiler error. An int array cannot be converted to an Object array, either explicitly as in line B or implicitly as in line C. There is no type matching here, just as Object o = 1 is also wrong. Since we already cannot compile line C, line D also leads to a compiler error: there is no type matching from an Object array to an int array.

1.7.2. Loop arrays and output wind speed, wind direction.

com/tutego/exercise/array/Windy.java
final int MAX_WIND_SPEED = 200;
final int MAX_DEGREE     = 360;

final int LENGTH = 5;
int[] windSpeed     = new int[ LENGTH ];
int[] windDirection = new int[ LENGTH ];

for ( int i = 0; i < LENGTH; i++ ) {
  windSpeed[ i ]     = (int) (Math.random() * MAX_WIND_SPEED);
  windDirection[ i ] = (int) (Math.random() * MAX_DEGREE);
}

for ( int i = 0; i < LENGTH; i++ ) {
  System.out.printf( "Wind speed %d km/h and wind direction %d°",
                     windSpeed[ i ], windDirection[ i ] );
  if ( i != LENGTH - 1 )
    System.out.print( ", " );
}

The solution consists of four steps. First we want to define three constants: for the maximum wind speed and wind force and for the number of elements. We initialize LENGTH with 5, so that we don’t have to write the literal 5 as a magic number in the code again later when building the arrays windSpeed and windDirection; we can simply change the variable later if we want larger arrays.

In the second step we run with a loop variable from 0 to the last element of the array. The array has five elements, so we may run from 0 to 4. In the body of the loop, we create two random numbers and initialize the array elements. Calculating an integer random number from 0 to 200 looks like this: Using Math.random() we get a random number as a floating point number between 0 and true less than 1. Multiplying by 200 gives a random number between 0 and true less than 200. If (int) converts the expression to an integer, all decimal places are truncated, so the result is an integer between 0 and 199. Usually, for range specifications, the start is inclusive and the end is exclusive.

The two arrays are now initialized, and we can output the pairs. We loop through the array; we access the arrays windSpeed and windDirection at the same position i. The output is supported by printf(…​) and the format specifier %d for decimal numbers. But we do not put a comma in the format string, because there must not be a comma at the end of the string. That there is a comma only at the end can be solved in different ways. The approach here queries the loop counter whether it stands for the last element. If i is not equal to the last element, then a separator is set, otherwise not.

1.7.3. Reverse an array

com/tutego/exercise/array/BigProfits.java
private static int count5PercentJumps( int[] dailyGains ) {

  if ( dailyGains.length < 2 )
    return 0;

  final double MIN_PERCENT = 5;

  int result = 0;

  // Index variable i starting at 1, second element
  for ( int i = 1; i < dailyGains.length; i++ ) {
    double yesterday = dailyGains[ i - 1 ];
    double today     = dailyGains[ i ];

    double percent = today / yesterday * 100 - 100;

    if ( percent >= MIN_PERCENT )
      result++;
  }

  return result;
}

The count5PercentJumps(…​) method is passed an array containing, in the best case, a set of integers. It may happen that null is passed, which should not be a valid input for the program. If we fall back to length, there will be a NullPointerException in case of null — this is intended.

If the array object exists but contains no element or only one, we consider that an error and return 0.

If we get further, we know that there are at least two elements in the array. We run a for loop over the array, starting with index i at 1 and asking for two elements at a time: the current element at position i and the element at the position before that, at position i - 1. These elements stand for today and yesterday. In principle, we could have started at 0 and run to < dailyGains.length - 1.

Once we have read the amount for today and yesterday, we need to calculate the relative percentage increase. We do this with a simple formula. However, we make sure that the division is not done on integers, but on floating point numbers. After all, if two integers are divided, the result is again an integer. If we take the numbers out of the array beforehand and convert them to a double, we will have a more accurate ratio later by dividing two floating point numbers. This way we avoid problems with rounding, because if we want to change the constant at some point, e.g. to a much smaller value, small jumps might not be detected correctly. Special case: days where no sales were generated work because the increase on the following day is Double.Infinity and "Infinity" is greater than MIN_PERCENT.

After calculating the relative increment, we check to see if we get above our constant of 5% and increment the variable result, where we remember all the increments. At the end of the loop, we return result to report how many total increases we found.

1.7.4. Search consecutive strings and determine if Salty Snook is coming

com/tutego/exercise/array/SaltySnook.java
public static boolean isProbablyApproaching( String[] signs ) {

  final int MIN_OCCURRENCES = 4;

  if ( signs.length < MIN_OCCURRENCES )
    return false;

  for ( int i = 0, count = 1; i < signs.length - 1; i++ ) {
    String currentSign = Objects.requireNonNull( signs[ i ] );
    String nextSign    = Objects.requireNonNull( signs[ i + 1 ] );
    if ( currentSign.equals( nextSign ) ) {
      count++;
      if ( count == MIN_OCCURRENCES )
        return true;
    }
    else // ! currentSign.equals( nextSign )
      count = 1;
  }
  return false;
}

We note the number of ships we want in a constant MIN_OCCURRENCES so we can easily change the number later.

First we check if the array has at least MIN_OCCURRENCES many elements. If not, the method returns false to the caller. If null was passed, a NullPointerException follows by accessing the length attribute, which clearly reports the incorrect parameter.

If we do not get out of the method, there are at least four elements. When comparing subsequent elements in the array, there are usually two approaches:

  • generate an index from 0 to the second last element and then access two elements via the index and index + 1.

  • generate an index from 1 to the last element and then access two elements via index - 1 and index

This solution uses the first variant.

The for loop declares two local variables: i for the index, and in the variable count we note the number of successively equivalent strings; since a string occurs at least once, the variable is initialized with 1.

We start in the loop at index 0 and store the element in an intermediate variable currentSign. At the position 1 we have the second element to start with, and this assignment is also saved in a talking variable nextSign. Objects.requireNonNull(…​) will throw an exception at this point if one of the array elements is null.

Strings have an equals(…​) method that is used to determine equivalence. There are two outputs for the comparison:

  1. When we find two equal consecutive strings, we increment the counter counter and test if it is equal to MIN_OCCURRENCES. In that case, there are four equal consecutive strings, and we can exit the method with return true.

  2. If currentSign and nextSign are not equal, we must reset the counter to 1.

If at the end of the loop no string has been detected that occurs four times in a row, the method is exited with return false.

The whole if-else block can be shortened if you are willing to always test, even if the counter has been reset:

count = currentSign.equals( nextSign ) ? count + 1 : 1;
if ( count == MIN_OCCURRENCES ) return true;

1.7.5. Reverse an array

com/tutego/exercise/array/ArrayReverser.java
public static void reverse( double[] numbers ) {
  final int middle = numbers.length / 2;

  for ( int left = 0; left < middle; left++ ) {
    int right = numbers.length - left - 1;
    swap( numbers, left, right );
  }
}

private static void swap( double[] numbers, int i, int j ) {
  double swap  = numbers[ i ];
  numbers[ i ] = numbers[ j ];
  numbers[ j ] = swap;
}

The reverse(…​) method gets an array as parameter. So we get a reference to an object from another place. So changes do not take place on a copy, but we operate on exactly the array passed by the caller. Since arrays are objects that are accessed by references, it is possible that the caller passed null. In that case, the coming numbers.length will lead to a NullPointerException, and that is fine.

The algorithm itself is not difficult. We need to swap the first element with the last, then the second with the second last, and so on. We move the swapping of the elements to a separate method swap(…​).

In order to avoid overwriting the elements in reverse(…​), we must only run halfway. The variable middle represents the half. Although the variable is used only once in the loop, a variable of this kind helps to document the meaning of this expression more precisely. Our loop starts with the loop counter left at 0 and runs to the middle. The variable right runs in the opposite direction.

1.7.6. Find the nearest cinema

com/tutego/exercise/array/MinDistance.java
static double minDistance( Point[] points, int size ) {

  if ( points.length == 0 || size > points.length )
    throw new IllegalArgumentException(
        "Array is either empty or size out of bounds" );

  double minDistance = points[ 0 ].distance( 0, 0 );

  // Index variable i starting at 1, second element
  for ( int i = 1; i < size; i++ ) {
    double distance = points[ i ].distance( 0, 0 );
    if ( distance < minDistance )
      minDistance = distance;
  }

  return minDistance;
}

First, we check in the method if the parameters points and size are correct. We expect at least one element, and the number of elements to be considered must not be greater than the number of elements in the array. If the passing was null, a NullPointerException follows automatically by accessing length.

When asking for the largest or smallest element of a list, the algorithms always look the same. We start with a candidate and then check if this candidate needs to be corrected. Our candidate is minDistance. We initialize it with the distance of the first point to the zero point. We don`t have to calculate the distance to the zero point ourselves, here the Point method distance(x,y) conveniently helps us. We pass the coordinates 0, 0, relative to which the point should calculate its distance.

So that all points are considered, we run through the array and use size as length constraint. From the new point we also calculate the distance to the zero point, and if we found a point closer to the zero point, we have to correct our choice.

At the end of the method we return the minimum distance to the origin. If the method should now return a Point rather than the distance itself, we rewrite the method to remember Point nearest in addition to double minDistance; if we were to omit minDistance, the distance would have to be recalculated each time, which would waste performance unnecessarily.

com/tutego/exercise/array/MinDistance.java
static Point minDistance2( Point[] points, int size ) {
  Point  nearest = points[ 0 ];
  double minDistance = nearest.distance( 0, 0 );

  for ( int i = 1; i < size; i++ ) {
    double distance = points[ i ].distance( 0, 0 );
    if ( distance < minDistance ) {
      minDistance = distance;
      nearest = points[ i ];
    }
  }
  return nearest;
}

1.7.7. Raid candy store and share fairly

com/tutego/exercise/array/FairSharing.java
public static int findSplitPoint( int[] values ) {

  if ( values.length < 2 )
    return -1;

  int sumLeft = values[ 0 ];

  int sumRight = 0;
  for ( int i = 1; i < values.length; i++ )
    sumRight += values[ i ];

  for ( int splitIndex = 1; splitIndex < values.length; splitIndex++ ) {
    int relativeDifference = relativeDifference( sumLeft, sumRight );

    Logger.getLogger( "MuggingFairly" )
          .info( "splitIndex=" + splitIndex
                     + ", sum left/right=" + sumLeft + "/" + sumRight
                     + ", difference=" + relativeDifference );

    if ( relativeDifference <= 10 )
      return splitIndex;

    int element = values[ splitIndex ];
    sumLeft  += element;
    sumRight -= element;
  }
  return -1;
}

// https://en.wikipedia.org/wiki/Relative_change_and_difference
private static int relativeDifference( int a, int b ) {
  if ( a == b ) return 0;
  int absoluteDifference = Math.abs( a - b );
  return (int) (100. * absoluteDifference / Math.max( a, b ));
}

We can implement the algorithm for the solution well iteratively or recursively. Here, the decision has been made to use the iterative variant, which is easy to understand.

Let’s start with a simple consideration of how to solve the problem. We could

  1. take an index that divides the array into two halves,

  2. calculate the sum of the right and left parts,

  3. compare them, and if the two sides are approximately equal, end the program with a result.

The index moves from front to back, and the sums are always recalculated. This algorithm is simple, but we have to go over the array several times, so eventually the runtime is quadratic. This works better.

If we split the array in two and the cursor moves one position to the right, the sum changes according to a very simple pattern: what is added to the sum on the left is subtracted on the right. This is the core idea of the solution.

At the beginning of the method we check if one or no element was passed. If so, there can be no fair division, and we return -1. If the null reference is passed, the program throws a NullPointerException, which is a good reaction.

In the next step, we declare two variables that store the sums of the left and right halves. The left sum consists at the beginning only of the first element of the array, the right sum is formed from the second (index 1) to the last element.

We will adjust these two variables, sumLeft and sumRight, in the following. The loop runs from the first to the last element. Since we have already completely formed the left and right sum before the loop run, we can now already calculate the relative difference, and if it is <= 10, then we actually already have a result. If the distance between the values was greater, we add to the left element and subtract from the right element. Finally, we go further into the loop, and if at any time the relative difference becomes less than or equal to 10, we jump out with splitIndex, otherwise the method is terminated with -1.

1.7.8. Draw mountains

com/tutego/exercise/array/MountainVisualizer.java
private static String mountainChar() { return "*"; }

public static void printMountain( int[] altitudes ) {

  int maxAltitude = altitudes[ 0 ];

  for ( int currentAltitude : altitudes )
    if ( currentAltitude > maxAltitude )
      maxAltitude = currentAltitude;

  // include height 0, so it’s >= 0
  for ( int height = maxAltitude; height >= 0; height-- ) {
    System.out.print( height + " " );
    for ( int altitude : altitudes )
      System.out.print( altitude == height ? mountainChar() : ' ' );
    System.out.println();
  }
}

The printMountain(int[] altitudes) method takes a whole array of altitude information, and for the graphical representation we need to find the highest value in the first step. This is the task of the first loop, but it must not run until the array has any entries at all. maxAltitude stores the maximum.

The next step is to draw lines. Each line represents a height. The writing of all lines is done by a for loop with a loop counter height. Since it starts with the maximum height, the loop starts with maxAltitude and goes down to 0. The task states that it does not go below zero, which means we do not need to complete a second search for the smallest number.

In the body of the height loop, we first output the height followed by a space. (We write height + " " and not height + ' ', why?) An inner for loop takes care of the line. It runs repeatedly over the height information altitudes passed to the method. For each element in altitudes we query whether it matches the height height, and if so we draw the symbol over mountainChar(), otherwise we draw a blank. A blank line is written at the end of the line.

The drawing of the mountain symbol is done by the mountainChar() method; it returns a *. We could have drawn the character directly or referenced it using a constant, but the method is a preparation for the next task …​

Optional extension

In the first proposed solution, the mountainChar() method always returns *; if the method is to return other symbols, it needs a bit more context, because it must be able to look back and forward. So let’s extend the signature: mountainChar(int[] altitudes, int index). The method gets access to the array and to the current position. The call looks like this:

com/tutego/exercise/array/MoreMountainVisualizer.java
for ( int height = maxAltitude; height >= 0; height-- ) {
  System.out.print( height + " " );
  for ( int x = 0; x < altitudes.length; x++ )
    System.out.print( altitudes[ x ] == height ?
                      mountainChar( altitudes, x ) : ' ' );
  System.out.println();
}

This way mountainChar(…​) can decide for itself what the correct symbol is.

com/tutego/exercise/array/MoreMountainVisualizer.java
private static char mountainChar( int[] altitudes, int index ) {
  int previous = index == 0 ? 0 : altitudes[ index - 1 ];
  int current  = altitudes[ index ];
  int next     = index < altitudes.length - 1 ? altitudes[ index + 1 ] : -1;

  if ( previous < current && current > next )
    return '^';
  if ( current < next )
    return '/';
  if ( current > next )
    return '\\';
  // current == next )
  return '-';
}

In the first step the variables previous, current and next are initialized with the heights from the array; this way it is possible to look at the height of the current element, but also at the height of the predecessor and successor. Before the first element of the array the height should be 0, as well as after the last element.

Depending on the relations, a choice can be made for the character at the height current:

  • If previous and next are lower than current, we have a peak and draw a ^.

  • If we are lower than the right neighbor, we are going uphill and draw /.

  • If we are higher than the right neighbor, it is going downhill, the symbol is \.

  • Otherwise, the right neighbor is at the same height as we are, and this is indicated by -.

1.7.9. Check mini-sudoku for valid solution

com/tutego/exercise/array/Sudoku3x3Checker.java
final int DIMENSION = 3;
for ( int i = 1; i <= DIMENSION * DIMENSION; i++ ) {
  boolean found = false;
  matrixLoop:
  for ( int row = 0; row < DIMENSION; row++ ) {
    for ( int column = 0; column < DIMENSION; column++ ) {
      int element = array[ row ][ column ];
      if ( element == i ) {
        found = true;
        break matrixLoop;
      }
    }
  }
  if ( ! found )
    System.out.printf( "Missing %d%n", i );
}

We declare the array for the task with elements in advance, also we create a variable DIMENSION, for the dimensions of the array. We assume that the 3-×-3 array has exactly nine elements.

We want to look at two different solutions. If it is necessary to test whether the numbers 1 to 9 occur in the two-dimensional array, a loop can produce the values from 1 to 9, and then it is possible to test whether each of these numbers occurs in the two-dimensional array. To do this, we create a boolean variable found, which we initialize with false at the beginning and set to true whenever the element occurs in the array; in that case, we can also cancel the loops. In principle, we could of course continue searching, but this is unnecessary. To break the loop we have to resort to a special construction in Java, the jump labels. If we simply use break in the condition statement, it will terminate the innermost loop, but not the outer loop. With a jump label, we can also exit the outer loop with break. At the end of the loops, we query the found flag, and if the flag is still false because it was not set to true in the condition statement, the number is missing. We print it out.

The disadvantage of the solution is the relatively high execution time, moreover a break with label makes the code unreadable and harder to understand. We have to run the 3 × 3 array nine times. This works better. However, we have to remember whether we have seen a number before or not.

com/tutego/exercise/array/Sudoku3x3Checker.java
boolean[] numberExisted = new boolean[ DIMENSION * DIMENSION ];

for ( int row = 0; row < DIMENSION; row++ ) {
  for ( int column = 0; column < DIMENSION; column++ ) {
    int element = array[ row ][ column ];
    if ( element >= 1 && element <= 9 )
      numberExisted[ element - 1 ] = true;
  }
}

for ( int i = 0; i < numberExisted.length; i++ ) {
  boolean found = numberExisted[ i ];
  if ( ! found )
    System.out.printf( "Missing %d%n", i + 1 );
}

The second solution declares a boolean array numberExisted as memory. The handy thing about Sudoku numbers is that they range from 1 to 9, so we can easily map that to index 0 to 8. When we get a number from the array and compute an index for the array from it, we need to guard against getting an ArrayIndexOutOfBoundsException. Therefore we check before, if the number element is in the right range. If it is, then we set the value true on the position element - 1.

After the single pass, we examine the array, and if we find a position that has never been written to, we know that the number is missing. Whether a position in the array has been written to more than once does not matter.

1.7.10. Enlarge image

com/tutego/exercise/array/ArrayMagnifier.java
public static int[][] magnify( int[][] array, int factor ) {
  int width = array[ 0 ].length;
  int height = array.length;
  int[][] result = new int[ height * factor ][ width * factor ];

  for ( int row = 0; row < result.length; row++ ) {
    int[] cols = result[ row ];
    for ( int col = 0; col < cols.length; col++ )
      cols[ col ] = array[ row / factor ][ col / factor ];
  }
  return result;
}

private static void printValues( int[][] array ) {
  for ( int[] rows : array ) {
    for ( int col = 0; col < rows.length; col++ )
      System.out.printf( "%03d%s",
                         rows[ col ], col == rows.length - 1 ? "" : ", " );
    System.out.println();
  }
}

private static void fillWithRandomValues( int[][] array ) {
  for ( int row = 0; row < array.length; row++ ) {
    int[] cols = array[ row ];
    for ( int col = 0; col < cols.length; col++ ) {
      array[ row ][ col ] = ThreadLocalRandom.current().nextInt( 256 );
    }
  }
}

public static void main( String[] args ) {
  int[][] testArray = new int[ 2 ][ 5 ];
  fillWithRandomValues( testArray );
  printValues( testArray );
  int[][] result = magnify( testArray, 2 );
  printValues( result );
}

Besides the central magnify(…​) method, we have a few more methods that create an array of random numbers and output the information in a matrix.

For clarity, two new variables are declared at the start of the method, representing the width and height of the two-dimensional array. The next task is to build a new two-dimensional array, which is larger in height and width by the factor than the old array.

The main task is performed by the two nested loops. In the first outer loop we use row to run over all new rows. Since two-dimensional arrays are nothing more than arrays within arrays, the outer array holds all the references to the inner arrays, the rows. The helper variable cols represents the columns of a row. We then let the inner loop counter col run from 0 to the width of that row.

The interesting part is in the inner loop. We have the variables row and col in the value ranges of the new enlarged two-dimensional array. We need to initialize the position result[row][col]. For this we get the values from the old small array. We calculate the position down with row / factor for the row and col / factor for the column. Remember: row goes from 0 to height * factor and col to width * factor. The row / factor and col / factor divisions divide integers, and the result is again an integer; this has the effect of getting the same number out of the small source array several times.

1.7.11. Create SVG polygons with variable number of coordinates

com/tutego/exercise/array/SvgVarargPolygon.java
/**
 * Prints an SVG polygon. Example output:
 * <pre>
 *  <polygon points="200,10 250,190 160,210 " />
 * </pre>
 * @param points of the SVG polygon.
 */
public static void printSvgPolygon( int... points ) {

  if ( points.length % 2 == 1 )
    throw new IllegalArgumentException(
        "Array has an odd number of arguments: " + points.length );

  System.out.print( "<polygon points=\"" );

  for ( int i = 0; i < points.length; i += 2 )
    System.out.printf( "%d,%d ", points[ i ], points[ i + 1 ] );

  System.out.println( "\" />" );
}

Two errors may occur:

  1. In a vararg, the compiler itself builds an array from the passed arguments, but we can also pass a reference to an array. Since references can be null, there could be a call to printSvgPolygon(null). Passing null.length will automatically lead to a NullPointerException.

  2. When printSvgPolygon() is called, the compiler builds an empty array; this contains no elements, which is fine in principle for our method. But there is another requirement for the length: the method itself always expects pairs of x and y coordinates. It would be an error to pass only one coordinate and not two. Unfortunately, the compiler can’t test something like that, you can’t make any requests on the number of varargs like: "at most 102 elements", "the number of elements must be divisible by 10" etc. We have no choice but to perform the test at runtime. We can easily detect the error by checking whether the number of elements in the array is even or odd. If the number is even, pairs were always passed, for x and y. If the number is odd, a coordinate is missing. We penalize erroneous calls with an IllegalArgumentException.It would still be worth considering making two condition statements out of the two checks, and then including the number of elements in the exception message in the case of the odd passing.

Generating the output consists of three parts:

  1. In the first part, the prologue, we set the start tag for the polygon.

  2. In the second part, a loop runs over all the elements of the array and always picks out two elements that come to the console separated by commas — there is a space after the pair. Since we always pick two elements from the array at a time, the index is incremented by 2 in the for loop’s increment expression. Since the number of elements in the array is even, there won`t be any ArrayIndexOutOfBoundsExcepion.

  3. The method ends with the epilogue, closing the tag.

1.7.12. Check for approval

com/tutego/exercise/array/AllTrue.java
private static boolean allTrue( boolean first, boolean... remaining ) {

  for ( boolean b : remaining )
    if ( b == false )
      return false;

  return first;
}

With variable argument lists, it is not possible to expect a minimum number of arguments. The solution to this problem is to introduce a minimum number of fixed parameters and then use a vararg for the rest at the end.

The method has two paths that return true or false:

  1. First, we traverse the array. If one of the noolean values in the array is false, we can exit the method directly with return false. If the array is empty, nothing happens. There are authors who do not test boolean values with == false but negate the expression, but I think that if ( b == false ) reads better than if ( ! b ); it also depends on the variable name. It may be that null was passed as an argument, in which case the extended for loop will throw a NullPointerException, which is intentional.

  2. If the loop does not terminate, all elements in the array must have been true, and the first parameter first decides the result.

1.7.13. Help, tetraphobia! Put all fours last

com/tutego/exercise/array/Tetraphobia.java
private static boolean containsFour( int number ) {
  return String.valueOf( number ).contains( "4" );
}

public static int[] fourLast( int... numbers ) {

  if ( numbers.length < 2 )
    return numbers;

  for ( int startIndex = 0; startIndex < numbers.length; startIndex++ ) {
    if ( ! containsFour( numbers[ startIndex ] ) )
      continue;

    // from right to left search the first number without a 4
    for ( int endIndex = numbers.length - 1;
          endIndex > startIndex; endIndex-- ) {
      if ( containsFour( numbers[ endIndex ] ) )
        continue;
      // swap number[i] (with 4) and number[j] no 4
      int swap = numbers[ startIndex ];
      numbers[ startIndex ] = numbers[ endIndex ];
      numbers[ endIndex ]   = swap;
    }
  }
  return numbers;
}

For our solution, in addition to the desired fourLast(…​) method, we write an additional private method boolean containsFour(int), which answers the question whether the number passed contains a 4. In the implementation, we make it simple and convert the number to a string, and contains(String) checks whether the string "4" is in the string representation. We could have done the check numerically, of course, but that would have been much more complicated. We would always have to divide that number by 10 and then look at the remainder and test if it is 4. That would require more code than just this one one-liner.

The method fourLast(…​) gets passed an array, which again could be null and in such a case lead to a NullPointerException by numbers.length. Also, the array could contain only one element, in which case we directly return the passed array to the caller.

Our algorithm is implemented in a simple way: We run in a loop from left to right, and when we find something containing a 4, we run in a second loop from right to left, looking for the first free space without a 4. Then we swap the contents of the array.

The proposed solution is not quite optimal and should be improved by the readers.

  1. The first thing that should be improved is the loop with startIndex that always runs to numbers.length. This is unnecessary, because if the inner loop should find a number with a 4, then this number will go to the back, and we can subtract one from the length, because we don`t have to look at the last element.

  2. Second, the inner loop is not optimal, because it always starts from right to left, looking for the first number without a 4. However, the block of fours only grows to the left, so we could remember in a second variable where we placed our last 4. If the inner loop runs again, we could continue at this position and do not have to find it again from the right.

  3. Third, we can combine the two improvements. In the case where there is no swap in the inner loop, we would be done.

1.7.14. Quiz: Copy arrays

The arraycopy(…​) method can be used to move ranges in an array or copy parts of an array to another array. Let’s look from the Javadoc at the parameter variables of arraycopy(…​), which are self-explanatory:

static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length).

In our case, we do not move something in an array, but copy parts of an array twice into a new array. hooey is the source and shuck the destination. If we set the constants and rename hooey and shuck, the following follows:

int[] src = { 1, 2, 3, 4 };
int[] dest = new int[ 3 ];
System.arraycopy( src, 0, dest, 0, 2 );
System.arraycopy( src, 3, dest, 2, 1 );

The result is [1, 2, 4], i.e. a new array with element 3 missing at index 2 (bushwa). The first copy operation transfers from the source starting at the first location 0 to the new array starting at location 0, a total of 2 elements. The second copy operation copies from location 3 (so skips location 2) everything to the end to the destination array starting from location 2. The number of copied elements is one.

With the nonsensical variable names it should also have become clear that clean code — here variable identifiers — saves human processing time and reduces errors.

1.7.15. Quiz: Compare arrays

The == operator checks whether the objects referenced by the two reference variables are identical. The two variables array1 and array2 do not, because they are two completely separate objects in memory. Therefore the output will be false.

Arrays are objects, and as objects they have all the methods that the base type java.lang.Object also provides. However, we can`t do anything with any of these methods, which we quickly notice when we call the toString() method on an array object. The equals(…​) method of an array comes from Object, and there we have an identity comparison, which, as explained in the first point, results in the output false.

To compare arrays we are quite right with the class java.util.Arrays and the method equals(…​). In general we can compare arrays with this method, but our two arrays have a little peculiarity: they contain strings and an inner array with integers. If this subreferenced array were not present, true would indeed appear in this output. However, Array.equals(…​) works flat, meaning that the referenced inner array would have to be identical, but since this integer array is also a new array in each case, the two references to the integer array are not equal and thus Array.equals(…​) returns false on our array.

Only with the method Array.deepEquals(…​) will true appear on the screen. deepEquals(…​) also keeps track of the referenced sub-arrays and looks to see if the values are equivalent. The identity of the sub-arrays is not important for deepEquals(…​). The two integer arrays are equivalent, and therefore the return value of deepEquals(…​) is true.